二叉查找树上执行基本操作的时间 与树的高度成正比。
二叉查找树中关键字的存储方式满足以下二叉查找树性质：
设x为二叉查找树中的一个节点。如果y是x的左子树中的一个节点，则key[y] <= key[x]。
如果y是x的右子树的一个节点，则key[x] <= key[]y.
用循环遍历的方式也可以用递归的 方式实现；节点删除也有更简单的方法（参见算法导论第二版第12章），
但这里的方法更易于理解。
/* * To change this template, choose Tools | Templates * and open the template in the editor. */package binarysearchtree;/** * * @author Administrator */public class BinarySearchTree { private TreeNode root = null; /** * @return the root */ public TreeNode getRoot() { return root; } private class TreeNode { private int key; private TreeNode leftChild; private TreeNode rightChild; private TreeNode parent; public TreeNode(int key, TreeNode leftChild, TreeNode rightChild, TreeNode parent) { this.key = key; this.leftChild = leftChild; this.rightChild = rightChild; this.parent = parent; } /** * @return the key */ public int getKey() { return key; } @Override public String toString() { String leftKey = (leftChild == null ? "" : String.valueOf(leftChild.key)); String rightKey = (rightChild == null ? "" : String.valueOf(rightChild.key)); return "(" + leftKey + "," + key + "," + rightKey + ")"; } } /** * 判断二叉查找树是否为空 * * @return */ public boolean isEmpty() { if (getRoot() == null) { return true; } else { return false; } } /** * 循环查找包含指定关键值key的节点 * * @param key * @return 指向包含该key值得节点或者null。 */ public TreeNode search(int key) { TreeNode node = getRoot(); while (node != null && node.key != key) { if (key < node.key) { node = node.leftChild; } else { node = node.rightChild; } } return node; } /** * 插入关键值为key的节点 * * @param key */ public void insert(int key) { TreeNode parentNode = null; TreeNode newNode = new TreeNode(key, null, null, null); TreeNode node = getRoot(); if (getRoot() == null) { root = newNode; return; } while (node != null) { parentNode = node; if (key < node.key) { node = node.leftChild; } else if (key > node.key) { node = node.rightChild; } else { return; } } if (key < parentNode.key) { parentNode.leftChild = newNode; newNode.parent = parentNode; } else { parentNode.rightChild = newNode; newNode.parent = parentNode; } } /** * 找到二叉查找树中包含最小关键值的节点 * * @param root * @return */ public TreeNode minNode(TreeNode root) throws Exception { if (root == null) { throw new Exception("树为空！"); } TreeNode node = root; while (node.leftChild != null) { node = node.leftChild; } return node; } /** * 找到二叉查找树中包含最大关键值的节点 * * @return */ public TreeNode maxNode(TreeNode root) throws Exception { if (root == null) { throw new Exception("树为空！"); } TreeNode node = root; while (node.rightChild != null) { node = node.rightChild; } return node; } /** * 查找后继节点 * * @param node * @return * @throws Exception */ public TreeNode successor(TreeNode node) throws Exception { if (node == null) { return null; } //第一种情况：右子树不为空。后继结点即为右子树中的最小关键值节点 if (node.rightChild != null) { return minNode(node.rightChild); } //第二种情况：右子树为空。后继结点y为最低祖先节点，且y的左子树也是祖先。 TreeNode parentNode = node.parent; while (parentNode != null && node == parentNode.rightChild) { node = parentNode; parentNode = parentNode.parent; } return parentNode; } /** * 查找前驱结点 * * @param node * @return * @throws Exception */ public TreeNode precessor(TreeNode node) throws Exception { if (node == null) { return null; } //第一种情况：左子树不为空。后继结点即为左子树中包含最大关键值的节点。 if (node.leftChild != null) { return maxNode(node.leftChild); } //第二种情况：左子树为空。后继结点y为最低祖先 TreeNode parentNode = node.parent; if (parentNode != null && node == parentNode.leftChild) { node = parentNode; parentNode = parentNode.parent; } return parentNode; } /** * 删除包含关键值key的节点 * * @param key * @throws Exception */ public void delete(int key) throws Exception { TreeNode node = search(key); if (node == null) { throw new Exception("树中不存在要删除的关键值！"); } delete(node); } /** * 删除指定节点 * * @param node */ private void delete(TreeNode node) throws Exception { if (node == null) { return; } //第一种情况：该节点没有子节点. if (node.leftChild == null && node.rightChild == null) { TreeNode parentNode = node.parent; if (node == parentNode.leftChild) { parentNode.leftChild = null; } else { parentNode.rightChild = null; } } //第二种情况：左子树为空，右子树不为空 if (node.leftChild == null && node.rightChild != null) { TreeNode parentNode = node.parent; if (node == parentNode.leftChild) { parentNode.leftChild = node.rightChild; node.rightChild.parent = parentNode; } else { parentNode.rightChild = node.rightChild; node.rightChild.parent = parentNode; } } //第三种情况：左子树不为空，右子树为空 if (node.leftChild != null && node.rightChild == null) { TreeNode parentNode = node.parent; if (node == parentNode.leftChild) { parentNode.leftChild = node.leftChild; node.leftChild.parent = parentNode; } else { parentNode.rightChild = node.leftChild; node.leftChild.parent = parentNode; } } //第四种情况：左右子树均不为空 if (node.leftChild != null && node.rightChild != null) { TreeNode sucessorNode = successor(node); delete(sucessorNode); node.key = sucessorNode.key; } } /** * 中序遍历 * * @param root */ public void inOrderTraverse(TreeNode root) { if (root != null) { inOrderTraverse(root.leftChild); System.out.print(" " + root.key + " "); inOrderTraverse(root.rightChild); } } /** * @param args the command line arguments */ public static void main(String[] args) throws Exception { // TODO code application logic here BinarySearchTree bst = new BinarySearchTree(); System.out.println("二叉查找树是否为空？ " + (bst.isEmpty() ? "是" : "否")); int[] keys = new int[]{15, 6, 18, 3, 7, 13, 20, 2, 9, 4}; for (int key : keys) { bst.insert(key); } System.out.println("二叉查找树是否为空？ " + (bst.isEmpty() ? "是" : "否")); System.out.println("最大关键值： " + bst.maxNode(bst.root).getKey() + " " + "最小关键值： " + bst.minNode(bst.getRoot()).getKey()); System.out.println("中序遍历： "); bst.inOrderTraverse(bst.getRoot()); System.out.println(""); System.out.println("根节点关键值： " + bst.getRoot().key); bst.delete(9); System.out.println("中序遍历： "); bst.inOrderTraverse(bst.getRoot()); }}
宁愿停歇在你门前的那棵树上，看着你，守护你。
