在不使用父指针的情况下查找后继者

Question

BST中元素的后继元素是由顺序遍历确定的排序顺序中元素的后继元素.在CLRS的算法教科书(麻省理工学院出版社的算法导论)中介绍了当每个节点都有指向其父节点的指针时找到后继者.

在这里找到后继者的想法是 - 如果节点的右子树x是非空的,则后继子是右子树中x的最小元素.否则,后继者是x其左子女也是其祖先的最低祖先x(假设节点是其自身的祖先).

我们可以在不使用指向父节点的指针的情况下找到后继者吗？

有时我们的树节点没有这个指针.我挣扎了几个小时,但无法写出正确的代码.

Answer 1

受Sheldon解决方案的启发,这是该解决方案的非递归版本.

if (right[x]  != NIL)
    return min(right[x]);
else
{
    candidate = NIL;
    y = root; 
    while  (y!= x) // y is used as a probe

        if (key[x] < key[y])
            {
            candidate = y;
            y = y ->left;

             }
        else
            y = y->right;
}
return candidate;

如果候选者== NIL,则x是树中的最大值,并且没有后继者.