Как я могу найти родитель курсора в виде двоичного дерева без использования родительских опорного узла

Question

Я пытаюсь переместить курсор в этом родительском узел в бинарном дереве. Я хочу сделать это рекурсивно, не используя сохранение узла для отслеживания родителя. Я думаю, что мой аргумент base/stoping правильный, но я считаю, что последние два, если утверждение неверно. Я не уверен, как это сделать. Любой совет будет полезен. Спасибо.

public void cursorToParent() 
{ 
    TreeNode parent = root; 
    if(cursor == root) 
     return; 
    if(parent.getLeft().equals(cursor) || parent.getRight().equals(cursor)) 
     cursor = parent; 
    else 
     if(parent.getLeft()!=null) 
     { 
      parent = parent.getLeft(); 
      cursorToParent(); 
     } 
     if(parent.getLeft()!=null) 
     { 
      parent = parent.getLeft(); 
      cursorToParent(); 
     } 

} 

Answer 1

Необходимо передать обрабатывающий узел current в метод. Таким образом, там должен быть метод cursorToParentImpl(), который будет вызываться с root от первого способа:

public boolean cursorToParentImpl(TreeNode current) 
{ 
    if(cursor == current) 
     return false; 
    if(current.getLeft() == cursor || current.getRight() == cursor) { 
     cursor = current; 
     return true; 
    } 
    else { // note the missing parenthesis too 
     if(current.getLeft()!=null) { 
      if (cursorToParentImpl(current.getLeft())) 
       return true; 
     } 
     if(current.getRight()!=null) { 
      if (cursorToParentImpl(current.getRight())) 
       return true; 
     } 
    } 
    return false; 
} 

И называют это:

public void cursorToParent() 
{ 
    if (cursor == root) 
     return; 
    cursorToParentImpl(root); 
} 

Кроме того, вы можете избежать вызова equals() и просто использовать == оператор как здесь следует скорее сравнить ссылку на узлы.