1

正如标题所暗示的，如果我们在二叉搜索树 (BST) 中有节点 x，并且我们知道 x.successor 的信息而不是x.parent，我们也知道 x.left 和 x.right。如何根据以上信息计算 x.parent。

我决定在两种情况下对其进行分析：（根高度为 0）

  1. 如果 x 没有右孩子，则 x.successor的高度必须小于 x。换句话说，x.successor 位于 x 的“上层”。
  2. 如果 x 有右孩子，则 x.successor的高度必须大于 x。这意味着 x.successor 位于 x 的“较低级别”。

对于第一种情况，我们可以有以下伪代码。

y = x.succ
if x.right == NIL
     z = y.left
     while x != z
         y = z;
         z = z.right
return z

第二种情况如何处理？如果发生了什么x.right != NIL？

                        15

             6                       18
         3       7              17        19
       2   4       13                         20
                 9

如何检索节点 18 和 19 的父节点，因为最右边的节点 20 没有后继节点，所以它会返回 NIL。

4

1 回答 1

1

我们无法始终根据您的信息获得父母。例如，2 个节点，nodeOne.right = x 我们只知道 x left = null，right = null，successor = null 我们无法检索 nodeOne

当 x 不在最右边的分支时，我们可以获得父级（这意味着它有一些祖先，其左分支包含 x）。

该算法可以是：

继续找到合适的儿子，合适的孙子，...，直到没有后继者，然后进入您的代码（您的代码有点错误？）

function getParent(Node node){
   Node right = node;
   for(;right.right != null; right = right.right){
   }
   Node successor = right.successor;
   if (successor == null)
     return null;

   if (successor.left == node)
     return successor;

   for(Node p = successor.left; p!= null; p=p.right){ 
     if (p.right == node){
       return p;
     }
   }
   return null;  
}
于 2013-10-15T07:16:14.537 回答