在二叉搜索树中需要帮助理解inorder继承者

Question

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

问:找到一个算法,在二元搜索树中找到给定节点的下一个节点(例如,顺序后继节点),其中每个节点都有一个到其父节点的链接.

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

解决方案(如表格中所示)如下所示:

 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

当节点存储指向父母的指针时,它几乎总是颂扬他们的直接父母,而不是他们的继承者.在这次采访中的问题是如何导航树以找到顺序继承者.

找到顺序后继者的方法是考虑如果你以递归方式执行树的顺序,然后模仿下一步会发生什么会发生什么.特别是,顺序遍历的逻辑总是访问节点的所有左子树,然后访问节点本身,然后访问右子树.要查找顺序继承者,您需要查看您所处的情况.

如果您当前所在的节点具有正确的子树,那么该树的顺序后继必须是在顺序遍历期间在该子树中访问的第一个节点,这是该树的最小元素.您可以通过下降到右侧子树,然后沿树的左侧脊柱向下行进直到找到最左侧的节点来找到它.

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

希望这可以帮助!