不使用父指针查找后继者

Question

BST 中元素的后继者是按中序遍历确定的排序顺序的元素后继者。 CLRS 的算法教科书（麻省理工学院出版社的算法简介）中介绍了当每个节点都有指向其父节点的指针时查找后继节点。

这里寻找后继的想法是 - 如果节点 x 的右子树非空，则 x 的后继是右子树中的最小元素。否则，后继者是 x 的最低祖先，其左子节点也是 x 的祖先（假设节点是其自身的祖先）。

我们可以不使用指向父节点的指针来找到后继节点吗？

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

Answer 1

受谢尔顿解决方案的启发，这是该解决方案的非递归版本。

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;

If candidate == NIL, x is the max in the tree and does not have a successor.

Answer 2

这应该可行：

TREE-SUCCESSOR(T, x)
  if right[x] != NIL
    return TREE-MINIMUM(right[x])
  else
    return FIND-TREE-SUCCESSOR(root[T], x, NIL)

FIND-TREE-SUCCESSOR(y, x, c)
  if y = x
    return c
  if key[x] < key[y]
    return FIND-TREE-SUCCESSOR(left[y], x, y)
  else
    return FIND-TREE-SUCCESSOR(right[y], x, c)

FIND-TREE-SUCCESSOR 将我们左转的最后一个节点保留在（候选者的）c 中。

Answer 3

我在这里找到了一个没有父指针的有序后继者的优雅解决方案 -> http://www.geeksforgeeks.org/archives/9999

想法是

1.如果节点有右子树，那么它的后继者就是右子树中最小的元素

1. 如果该节点的右子树为空，那么它的后继者就是它的祖先之一，可以在没有父指针的情况下自上而下找到，有以下算法：

设初始 current_node 为 root，succ_node = null；

case1: 如果搜索元素小于 current_node，则当前元素是潜在后继 - 将 succ_node 放在 current_node 处，并将 current_node 移动到其左节点（因为搜索元素位于左子树中）

case2: 如果搜索元素大于 current_node，它不是潜在的后继者（较小的元素如何成为后继者？）。所以不需要把succ_node放在这里，而是把current_node移到右边。

继续重复该过程，直到达到 null 或元素本身并返回 succ_node。

Answer 4

如果您无权访问指向父节点的指针，那么您需要知道父亲是谁。如果你不知道，你怎么能上树呢？

Answer 5

递归 Java 解决方案可能如下所示：

public Integer successor(Integer value) {
    Node n = succ(root, value, null);
    if (null != n) {
       return n.value;
    }
    return null;
}

private Node succ(Node n, Integer x, Node p) {
    if (null == n) {
        return null;
    }

    if (x < n.value) {
        return succ(n.left, x, n);
    } else if (x > n.value) {
        return succ(n.right, x, p);
    }
    if (null != n.right) {
        return min(n.right);
    }
    return p;
}

作为客户端，我们只需传入想要了解后继节点的值。然后我们开始从根开始搜索，直到找到我们要寻找的值。现在有两种情况：

1. 如果当前节点有右子节点，则后继节点是当前节点右子树中最小的元素
2. 否则，它是节点 p（父指针），仅当我们在树内向左移动时才更新