如何使此方法适用于在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;
}
}

和节点类：

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. 否则，节点的后继节点是其右侧最接近的祖先。 如果您遵循从根到节点的路径，那么这是您向左走的最后一个路径。