// 二分查找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()); }