1

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

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

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

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

4

5 回答 5

7

受 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 是树中的最大值并且没有后继。

于 2010-09-26T17:17:31.657 回答
4

这应该有效：

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（候选）我们左转的最后一个节点。

于 2010-09-26T00:15:13.487 回答
2

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

想法是

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

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

最初让 current_node 为根，succ_node = null;

case1：如果搜索元素小于current_node，那么当前元素是一个潜在的后继者——将succ_node放在current_node并将current_node移动到它的左节点（因为搜索元素在左子树中）

case2：如果搜索元素大于 current_node，则它不是潜在的继任者（较小的元素如何成为继任者？）。所以这里不需要放置succ_node，而是将current_node向右移动。

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

于 2012-09-13T00:17:03.250 回答
0

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

于 2010-09-25T23:55:55.133 回答
0

递归 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（父指针），仅当我们在树中向左移动时才更新
于 2013-09-09T16:41:18.713 回答