如何使这种方法适用于寻找 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;
    }
}

节点class：

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

有两种情况：

如果节点有右 child，那么它的后继是右 child 的 left-most 后代，或者如果没有左 child 本身后代；
否则，该节点的后继是其右侧最近的祖先。如果你沿着从根到节点的路径，那么这是你向左走的最后一个。

如何使这种方法适用于寻找 BST 的继任者？

How to make this method work for finding the successor in BST?

java

binary-tree

binary-search-tree