// 二分查找
public class BST {
private TreeNode root;
public TreeNode getRoot() {return root;}
public void setRoot(TreeNode root) {this.root = root;}
// 每个树节点
static class TreeNode {
public int value;// 值
public TreeNode left;
public TreeNode right;
public TreeNode(int value){this.value = value;}
}
// 查找办法
public TreeNode get(int key){
TreeNode current = root;
while (current != null && current.value != key){if(key < current.value){current = current.left;} else if(key > current.value){current = current.right;}
}
return current == null ? null : current;
}
// insert 办法(插入)public void insert(int key){
// 如果根节点为 null,就把 key 插入到根节点
if(root == null){root = new TreeNode(key);
return;
}
TreeNode current = root;
TreeNode parent = null;// 要插入的地位的父亲
while(true) {
parent = current;
// 如果要插入的 key 小于 根节点,则到右边查找
if(key < parent.value){
current = parent.left;
// 如果根节点的左子树的 节点为 null,直接插入
if(current == null){parent.left = new TreeNode(key);
return;
}
}
// 如果要插入的 key 大于 根节点,则到左边查找
else if(key > parent.value){
current = parent.right;
if(current == null){parent.right = new TreeNode(key);
return;
}
}
// 阐明以后存在的值曾经存在了
else{return;}
}
}
// 删除办法
public boolean delete(int key){
TreeNode parent = root; // 要删除节点的父节点
TreeNode current = root;
boolean isLeftChild = false; // 是不是左节点
// 删除之前先找 这个节点
while(current != null && current.value != key){
parent = current;
if(current.value > key){
isLeftChild = true;
current = current.left;
} else {
isLeftChild = false;
current = current.right;
}
}
// 没有找到对应的数据
if(current == null){return false;}
// Case1 1:if node to be delete has no Children
if(current.left == null && current.right == null){if(current == root){root = null;} else if(isLeftChild) {parent.left = null;} else {parent.right = null;}
}
// Case1 2:if node to be delete has one Children
else if(current.right == null){if(current == root){root = current.left;} else if(isLeftChild){parent.left = current.left;} else {parent.right = current.left;}
}
else if(current.left == null){if(current ==root){root = current.right;} else if(isLeftChild){parent.left = current.right;} else {parent.right = current.right;}
}
// Case1 3:if node to be delete has two Children; current.left != null && current.right != null
else {TreeNode successor = getSuccessor(current);
if(current == root){root = successor;} else if(isLeftChild){parent.left = successor;}else{parent.right = successor;}
successor.left = current.left;
}
return true;
}
// 这个是用来找右子树上面最小的节点.
private TreeNode getSuccessor(TreeNode node){
TreeNode successor = null;
TreeNode successorParent = null;
TreeNode current = node.right;
// 找到最小的节点,终止条件是:节点为 null
while(current != null){
successorParent = successor;
successor = current;
current = current.left;
}
if(successor != node.right){
successorParent.left = successor.right;
successor.right = node.right;
}
return successor;
}
// 遍历办法
/**
* Pre-order Traversal:先拜访节点本人,然年后拜访左子树,最初在拜访右子树
*/
public static void preOrderTraversal(TreeNode root){if(root == null){return;}
System.out.println(root.value);
preOrderTraversal(root.left);
preOrderTraversal(root.right);
}
/**
* In-order Traversal:先拜访左子树上的节点,在拜访本人,最初再拜访右子树上的节点
*
* 遍历进去饿的数据,是排好程序的
*/
public static void inOrderTraversal(TreeNode root){if(root == null){return;}
inOrderTraversal(root.left);
System.out.println(root.value);
inOrderTraversal(root.right);
}
/**
* Post-order Traversal:先拜访左右子树,最初在拜访本人
*/
public static void postOrderTraversal(TreeNode root){if(root == null){return;}
postOrderTraversal(root.left);
postOrderTraversal(root.right);
System.out.println(root.value);
}
public static void main(String[] args) {
// Test
BST bst = new BST();
bst.insert(50);
bst.insert(36);
bst.insert(88);
bst.insert(77);
BST.inOrderTraversal(bst.getRoot());
System.out.println();
BST.preOrderTraversal(bst.getRoot());
System.out.println();
BST.postOrderTraversal(bst.getRoot());
}