Нужна помощь в понимании преемника в бинарном дереве поиска

Question

Мне нужна помощь в понимании этого вопроса:

В: Найти алгоритм для поиска следующего узла (например, преемника по порядку) данного узла в двоичном дереве поиска, где каждый узел имеет ссылку на своего родителя.

Родитель означает предшественника по порядку или просто непосредственного родителя? Как создать дерево, в котором узлы имеют ссылку на корневой узел или предшественник inorder? Буду признателен за любую помощь в понимании структуры данных и программы ниже ...

решение (как указано в форме) показано ниже:

 public static TreeNode inorderSucc(TreeNode e) {
   if (e != null) {
     TreeNode p;

     // Found right children -> return 1st inorder node on right
     if (e.parent == null || e.right != null) {
       p = leftMostChild(e.right);
     } else {
       // Go up until we’re on left instead of right (case 2b)
       while ((p = e.parent) != null) {
         if (p.left == e) {
           break;
         }
         e = p;
       }
     }
     return p;
   }
   return null;
 }

 public static TreeNode leftMostChild(TreeNode e) {
   if (e == null) return null;
   while (e.left != null) e = e.left;
   return e;
 }

Answer 1

Когда узлы хранят указатели на своих родителей, это почти всегда означает их непосредственных родителей, а не их наследников.Тогда вопрос в этом интервью заключается в том, как перемещаться по дереву, чтобы найти преемника по порядку.

Способ найти преемника по порядку состоит в том, чтобы подумать о том, что произойдет, если вы рекурсивно выполните обход по порядку.дерево, чтобы имитировать, что будет дальше.В частности, логика обхода по порядку всегда посещает все левое поддерево узла, затем сам узел и затем правое поддерево.Чтобы найти преемника по порядку, вам нужно увидеть, в каком вы случае.

Если узел, в котором вы находитесь, имеет правильное поддерево, то преемник по порядку этого дерева должен быть самым первымузел, который будет посещаться в этом поддереве во время обхода по порядку, который является наименьшим элементом этого дерева.Вы можете найти это, спустившись в правое поддерево, а затем пройдя по левому корешку дерева, пока не найдете самый левый узел.

Если у узла нет правого поддерева, то это самый большой узел в некоторыхподдерево.Если вы подумаете о том, как работает рекурсия, то следующим шагом в обходе по порядку будет возвращение всех рекурсивных вызовов, которые только что завершили расширение своих правых поддеревьев.Как только этот последний кадр вернется, вы посетите узел первого дерева, которое расширило только его левое поддерево.Следовательно, преемника по порядку можно найти, пройдя вверх по дереву, пока вы не достигнете узла, который является левым потомком.Родитель этого узла будет вашим преемником.В качестве альтернативы, если вы дойдете до корня дерева, это также будет вашим преемником.

Надеюсь, это поможет!