2

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

问：找到一种算法以在二叉搜索树中找到给定节点的下一个节点（例如，中序后继），其中每个节点都有到其父节点的链接。

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

解决方案（如表格中所示）如下所示：

 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;
 }
4

1 回答 1

8

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

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

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

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

希望这可以帮助！

于 2011-03-06T20:38:10.257 回答