算法导论上二叉查找树的实现java(一)

二叉查找树是一种应用十分广泛的数据结构，它在算法中应用十分广泛，二叉查找树支持多种动态集合的操作，这些操作主要包括：

1、查找某个特定值：

2、二叉查找树中最小值：

3、二叉查找树中最大值：

4、某个节点的前驱：

5、某个节点的后继：

6、插入特定值：

7、删除特定值：

一般情况下，我们为了保持查找和删除情况的唯一性，假设二叉查找树中各个元素的key值不想等。

下面一一剖析二叉查找树的结构与方法：

1、二叉查找树的数据结构：

// 构造二叉查找数的内部类,这就相当于C语言中的结构体
	private class TreeNode {
		private int key;
		private TreeNode lchild; // 定义二叉查找树的左孩子节点
		private TreeNode rchild;// 定义二叉查找树的右孩子节点
		private TreeNode parent;// 定义二叉查找树的父亲节点

		public TreeNode(int key, TreeNode lchild, TreeNode rchild,
				TreeNode parent) {
			this.key = key;
			this.lchild = lchild;
			this.rchild = rchild;
			this.parent = parent;
		}

		public int getKey() {
			return key;
		}
	}

public void treeInsert(int key) {// 实现二叉查找数的插入操作
		TreeNode parentNode = null;
		TreeNode newNode = new TreeNode(key, null, null, null);
		TreeNode tmpNode = root;
		if (root == null) {
			root = newNode;
			return;
		}
		while (tmpNode != null) { // 一般情况下，我们不会插入树中已经存在的节点
			parentNode = tmpNode;// 只是作为一个中间变量的节点
			if (key < tmpNode.key)
				tmpNode = tmpNode.lchild;
			else if (key > tmpNode.key)
				tmpNode = tmpNode.rchild;
			else
				return;
		}
		if (key < parentNode.key) {
			parentNode.lchild = newNode;
			newNode.parent = parentNode;
		} else {
			parentNode.rchild = newNode;
			newNode.parent = parentNode;
		}
	}

public void treeDelete(int key) {
		TreeNode tmpNode = treeSearch(key);
		if (tmpNode == null)
			System.out.println("此树中没有你要删除的节点!");
		delete(tmpNode); // 删除某一节点
	}

	public void delete(TreeNode node) { // 删除节点的关键的核心函数
		if (node == null)
			return;
		if (node.lchild == null && node.rchild == null) {// 如果被删除节点左右节点均为空
			TreeNode parentNode = node.parent;
			if (node == parentNode.lchild)
				parentNode.lchild = null;
			else
				parentNode.rchild = null;
			return;
		}
		if (node.lchild != null && node.rchild == null) {// 左孩子不为空，右孩子为空
			TreeNode parentNode = node.parent;
			if (node == parentNode.lchild) {
				parentNode.lchild = node.lchild;
				node.lchild.parent = parentNode;
			} else {
				parentNode.rchild = node.lchild;
				node.lchild.parent = parentNode;
			}
			return;
		}
		if (node.lchild == null && node.rchild != null) {// 左孩子为空，右孩子不为空
			TreeNode parentNode = node.parent;
			if (node == parentNode.lchild) {
				parentNode.lchild = node.rchild;
				node.rchild.parent = parentNode;
			} else {
				parentNode.rchild = node.rchild;
				node.rchild.parent = parentNode;
			}
			return;
		}
		// 该节点的左右孩子均非为空
		TreeNode tmpNode = treeSuccessor(node);
		node.key = tmpNode.key;
		delete(tmpNode);
	}

public TreeNode treeMinNode(TreeNode node) { // 获取此树中最小元素的节点
		if (node == null) {
			System.out.println("此树为空!");
			return null;
		}
		TreeNode tmpNode = node;
		while (tmpNode.lchild != null)
			tmpNode = tmpNode.lchild;
		return tmpNode;
	}

public TreeNode treeMaxNode(TreeNode node) { // 获取此树中最大元素的节点
		if (node == null) {
			System.out.println("此树为空!");
			return null;
		}
		TreeNode tmpNode = node;
		while (tmpNode.rchild != null)
			tmpNode = tmpNode.rchild;
		return tmpNode;
	}

public TreeNode treePrevious(TreeNode node) {// 找出中序条件下某节点的前续节点
		if (node == null)
			return null;
		if (node == treeMinNode(root))// 此时有一种特殊情况，就是节点是最小元素的节点，则没有前续节点
			return null;
		if (node.lchild != null)
			return treeMaxNode(node.lchild);
		else {
			TreeNode parentNode = node.parent;
			while (parentNode != null && node == parentNode.lchild) {
				node = parentNode;
				pare