algorithm - 需要帮助理解二叉搜索树中的顺序后继

Question

我需要帮助来理解这个面试问题:

Q: Find an algorithm to find the next node (e.g., inorder successor) of a given node in a binary search tree where each node has a link to its parent.

父级是指有序的前任还是直接父级？如何创建一棵树，其中的节点链接到根节点或前导节点？任何有助于理解数据结构和下面的程序的帮助将不胜感激......

解决方案(以表格形式发布)如下所示:

 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

当节点存储指向它们父节点的指针时，它几乎总是表示它们的直接父节点而不是它们的后继节点。本次采访的问题是如何导航树以找到有序的继任者。

找到有序后继的方法是考虑如果您递归地对树进行有序遍历会发生什么，然后模仿接下来会发生什么。特别是，有序遍历的逻辑总是访问节点的所有左子树，然后是节点本身，最后是右子树。要找到有序的继任者，您需要查看您所处的情况。

如果您当前所在的节点有一个右子树，那么该树的有序后继节点必须是在有序遍历期间在该子树中访问的第一个节点，它是其中的最小元素树。您可以通过下降到右子树找到它，然后沿着树的左脊柱前进，直到找到最左边的节点。

如果节点没有右子树，那么它是某个子树中最大的节点。如果您考虑递归是如何工作的，则顺序遍历的下一步是让所有刚刚完成扩展其右子树的递归调用返回。一旦最后一帧返回，您将访问仅展开其左子树的第一棵树的节点。因此，可以通过沿着树向上走直到到达作为左子节点的节点来找到节点的顺序后继者。这个节点的父节点就是你的继任者。或者，作为一种边缘情况，如果您到达树的根部，那也将是您的继任者。

希望这对您有所帮助!