二叉搜索树

二叉搜索树/二叉排序树（Binary Search Tree）：

1. 根的左子树不空，则左子树上所有结点的值均小于它的根结点的值。
2. 根的右子树不空，则右子树上所有结点的值均大于它的根结点的值。
3. 根的左、右子树也分别为二叉搜索树。

模版

class BSTree {
	class Node {
		int key, value;
		Node leftChild, rightChild;

		Node(int key, int value) {
			this.key = key;
			this.value = value;
		}
	}

	Node root;

	/**
	 * 查找指定节点
	 * 
	 * @param key 键
	 * 
	 * @return 指定节点
	 */
	Node query(int key) {
		Node currentNode = root;
		while (currentNode != null && currentNode.key != key) {
			if (key < currentNode.key) {
				currentNode = currentNode.leftChild;
			} else {
				currentNode = currentNode.rightChild;
			}
		}
		return currentNode;
	}

	/**
	 * 插入节点
	 * 
	 * @param key 键
	 * @param value 值
	 */
	void insert(int key, int value) {
		if (root == null) {
			root = new Node(key, value);
			return;
		}
		Node currentNode = root;
		Node parentNode = root;
		boolean isLeftChild = true;
		// 待插入的节点需要从根节点开始进行比较
		// 小于根节点则与根节点左子树比较，反之则与右子树比较
		// 直到左子树为空或右子树为空，插入到相应为空的位置
		while (currentNode != null) {
			parentNode = currentNode;
			if (key < currentNode.key) {
				currentNode = currentNode.leftChild;
				isLeftChild = true;
			} else {
				currentNode = currentNode.rightChild;
				isLeftChild = false;
			}
		}
		Node newNode = new Node(key, value);
		if (isLeftChild) {
			parentNode.leftChild = newNode;
		} else {
			parentNode.rightChild = newNode;
		}
	}

	/**
	 * 删除指定节点
	 * 
	 * @param key 键
	 * 
	 * @return 是否删除成功
	 */
	boolean delete(int key) {
		Node currentNode = root;
		Node parentNode = root;
		boolean isLeftChild = true;
		while (currentNode != null && currentNode.key != key) {
			parentNode = currentNode;
			if (key < currentNode.key) {
				currentNode = currentNode.leftChild;
				isLeftChild = true;
			} else {
				currentNode = currentNode.rightChild;
				isLeftChild = false;
			}
		}
		if (currentNode == null) {
			return false;
		}
		if (currentNode.leftChild == null && currentNode.rightChild == null) {
			// 要删除的节点为叶子节点
			if (currentNode == root) {
				root = null;
			} else if (isLeftChild) {
				parentNode.leftChild = null;
			} else {
				parentNode.rightChild = null;
			}
		} else if (currentNode.rightChild == null) {// 要删除的节点只有左孩子
			if (currentNode == root) {
				root = currentNode.leftChild;
			} else if (isLeftChild) {
				parentNode.leftChild = currentNode.leftChild;
			} else {
				parentNode.rightChild = currentNode.leftChild;
			}
		} else if (currentNode.leftChild == null) {// 要删除的节点只有右孩子
			if (currentNode == root) {
				root = currentNode.rightChild;
			} else if (isLeftChild) {
				parentNode.leftChild = currentNode.rightChild;
			} else {
				parentNode.rightChild = currentNode.rightChild;
			}
		} else {
			// 要删除的节点既有左孩子又有右孩子
			// 思路：用待删除节点右子树中的key值最小节点的值来替代要删除的节点的值，然后删除右子树中key值最小的节点
			// 右子树key最小的节点一定不含左子树，所以删除这个key最小的节点一定是属于叶子节点或者只有右子树的节点
			Node directPostNode = getDirectPostNode(currentNode);
			currentNode.key = directPostNode.key;
			currentNode.value = directPostNode.value;
		}
		return true;
	}

	/**
	 * 得到待删除节点的直接后继节点
	 * 
	 * @param delNode 待删除节点
	 * 
	 * @return 直接后继节点
	 */
	Node getDirectPostNode(Node delNode) {
		Node parentNode = delNode;// 用来保存待删除节点的直接后继节点的父亲节点
		Node directPostNode = delNode;// 用来保存待删除节点的直接后继节点
		Node currentNode = delNode.rightChild;
		while (currentNode != null) {
			parentNode = directPostNode;
			directPostNode = currentNode;
			currentNode = currentNode.leftChild;
		}
		if (directPostNode != delNode.rightChild) {// 从树中删除此直接后继节点
			parentNode.leftChild = directPostNode.rightChild;
			directPostNode.rightChild = null;
		}
		return directPostNode;// 返回此直接后继节点

	}

	/**
	 * 先序遍历
	 * 
	 * @param rootNode 根节点
	 */
	void preOrder(Node rootNode) {
		if (rootNode != null) {
			System.out.println("key: " + rootNode.key + " " + "value: " + rootNode.value);
			preOrder(rootNode.leftChild);
			preOrder(rootNode.rightChild);
		}
	}

	/**
	 * 中序遍历
	 * 
	 * @param rootNode 根节点
	 */
	void inOrder(Node rootNode) {
		if (rootNode != null) {
			inOrder(rootNode.leftChild);
			System.out.println("key: " + rootNode.key + " " + "value: " + rootNode.value);
			inOrder(rootNode.rightChild);
		}
	}

	/**
	 * 后序遍历
	 * 
	 * @param rootNode 根节点
	 */
	void postOrder(Node rootNode) {
		if (rootNode != null) {
			postOrder(rootNode.leftChild);
			postOrder(rootNode.rightChild);
			System.out.println("key: " + rootNode.key + " " + "value: " + rootNode.value);
		}
	}
}