http://www.geeksforgeeks.org/inorder-successor-in-binary-search-tree/
Inorder Successor in Binary Search Tree BST中找中序遍历的后继节点(二)
// 继续找更小的
succ = root; // 后继节点必然比node要大，所以只能在这里保存
root = root.left;
}
else if(root.data < node.data){ // 继续找更大的
root = root.right;
}
else{ // root节点和node节点重复，停止
break;
}
}
return succ;
}
/*
* Given a non-empty binary search tree, return the minimum data value found
* in that tree. Note that the entire tree does not need to be searched.
*/
public static Node minValue(Node node) {
Node cur = node;
// 最小节点必定在最左下角
while (cur.left != null) {
cur = cur.left;
}
return cur;
}
/*
* Give a binary search tree and a number, inserts a new node with the given
* number in the correct place in the tree. Returns the new root pointer
* which the caller should then use (the standard trick to avoid using
* reference parameters).
*
* 返回插入后节点的引用
*/
public static Node insert(Node node, int data) {
if (node == null) {
return new Node(data);
} else { // node 存在
Node temp;
if (data <= node.data) {
temp = insert(node.left, data);
node.left = temp;
temp.parent = node;
} else {
temp = insert(node.right, data);
node.right = temp;
temp.parent = node;
}
return node;
}
}
static class Node {
int data;
Node left;
Node right;
Node parent;
public Node(int data) {
this.data = data;
}
}
}