如何使这种方法在BST中找到后继者？

Question

我用Java为BST中的给定节点的后继者编写了一个方法，但是它不起作用

public Node successor(Node selectedNode) {
    Node current = root;
    while (current.element != selectedNode.element) {
        if (selectedNode.element > current.element) {
            current = current.right;
        } else {
            current = current.left;
        }
    }

    if (current.right != null) {
        return min(current.right);
    } else if (current == max(root)) {
        return new Node(Integer.MAX_VALUE);
    } else {
        Node tmp = current;
        if (current.element < root.element) {
            current = root;
            while (current.left.element > tmp.element) {
                current = current.left;
            }
        } else {
            current = root;
            while (current.right.element < tmp.element) {
                current = current.left;
            }
        }

        return current;
    }
}

和Node类：

public class Node {
public int element;
public Node left;
public Node right;

public Node(int element) {
    this.element = element;
    this.left = null;
    this.right = null;
}

}

我的第一个想法是在检查current.right != null之后在else if块上写这样的东西：

Node p = t.parent
while(p != null and t == p:right)
    t = p
    p = p:parent
return p

但不起作用。

Answer 1

有两种情况：

1. 如果节点有一个右子代，则其后继者是右子代的最左后代，如果子代本身没有左子代，则其本身是子代；
2. 否则，节点的后继者是它右边最接近的祖先。如果您遵循从根到节点的路径，那么这是您最后离开的路径。