前言

树是数据结构中的重中之重，二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树。数据结构中跟树有关的除了二叉树还有：完全二叉树、满二叉树、线索二叉树、霍夫曼树、二叉排序树、平衡二叉树、红黑树、B树，B+树等，后续也会陆续有相关内容的讲解。对于二叉树，它在保留数组和链表的优点的同时也改善了它们的缺点。

树和二叉树

树是一种数据结构,因为它数据的保存形式很像一个树,所以得名为树。

而二叉树是一种特殊的树,它的每个节点最多含有两个子树,现实世界中的二叉树：

当然，数据结构中的树结构是需要倒过来的。

二叉树名词解释：

深度与高度的区别在于：深度为根到节点的距离，而高度是节点到叶的距离(记住根深叶高)。

二叉搜索树以及它是通过什么方式改善的数组、链表的问题

首先看一下数组和链表的特点

数组的优点

• 简单易用.
• 无序数组的插入速度很快,效率为O(1)
• 有序数组的查找速度较快(较无序数组),效率为O(logN)

数组的缺点

• 数组的查找、删除很慢
• 数组一旦确定长度,无法改变

链表的优点

• 可以无限扩容(只要内存够大)
• 在链表头的新增、删除很快,效率为O(1)

链表的缺点

• 查找很慢
• 在非链表头的位置新增、删除很慢,效率为O(N)

二叉树特点

二叉搜索树是一种特殊的二叉树,除了它的子节点不能超过两个以外,它还拥有如下特点:

• 一个节点的左子节点的关键字的值永远小于该节点的值
• 一个节点的右子节点的关键字的值永远大于等于该节点的值

从图中还可以看出,二叉搜索树的最小值就是它的最左节点的关键字的值,而最大值则是它的最右节点的值.

二叉搜索树的查找、新增、删除的效率为O(logN)(这是理想状态下,如果树是不平衡的效率会降到O(N),后面会介绍).

二叉搜索树之所以效率高就在于:

• 它的数据是按照上述的有序的方式排列的.
• 进行新增、查找、删除的时候使用了二分查找法.

二叉树的实现
二叉树中数据是保存在一个个的节点中的,下面是保存数据的节点类:

public class Node {
	// 用来进行排序的关键字数组    
	int sortData ;
	// 其他类型的数据    
	int other;
	// 该节点的左子节点    
	Node leftNode;
	// 该节点的右子节点    
	Node rightNode;
	
	public static void main(String[] args) { 
		//初始化树
		Node topNodeBean_30 = new Node();
		//顶层节点为 30
		topNodeBean_30.sortData = 30;
		//顶层30的左侧树
		Node nodeBean_15 = new Node();
		nodeBean_15.sortData = 15;
		topNodeBean_30.leftNode = nodeBean_15;
		
		Node nodeBean_7 = new Node();
		nodeBean_7.sortData = 7;
		nodeBean_15.leftNode = nodeBean_7;
		
		Node nodeBean_21 = new Node();
		nodeBean_21.sortData = 21;
		nodeBean_15.rightNode = nodeBean_21;
		//顶层30的右侧树结构
		Node nodeBean_40 = new Node();
		nodeBean_40.sortData = 40;
		topNodeBean_30.rightNode = nodeBean_40;
		
		Node nodeBean_35 = new Node();
		nodeBean_35.sortData = 35;
		nodeBean_40.leftNode = nodeBean_35;
	
		//初始化树
		Tree tree = new Tree(topNodeBean_30);
		//添加节点
		Node node = new Node();
		node.sortData = 19;
		tree.insertData(node);
		
		System.out.println("**操作完成**");
		
	}
	
}

在二叉搜索树这个类中新增、修改、删除数据:

public class Tree {
	// 根节点    
	Node root;
	public Tree(Node root) {        
		this.root = root;    
	}// 新增、查找、删除 暂时省略,下面会一一介绍}
}

新增数据

在二叉树中插入数据的流程如下:

Java代码:

public void insertData(Node node) {
		int currentSortData = root.sortData;
		Node currentNode = root;
		Node currentLeftNode = root.leftNode;
		Node currentRightNode = root.rightNode;
		int insertSortData = node.sortData;
		while (true) {
			if (insertSortData < currentSortData) {
				if (currentLeftNode == null) {
					currentNode.leftNode = node;
					break;
				} else {
					currentNode = currentNode.leftNode;
					currentLeftNode = currentNode.leftNode;
					currentRightNode = currentNode.rightNode;
					currentSortData = currentNode.sortData;
				}
			} else {
				if (currentRightNode == null) {
					currentNode.rightNode = node;
					break;
				} else {
					currentNode = currentNode.rightNode;
					currentSortData = currentNode.sortData;
					currentLeftNode = currentNode.leftNode;
					currentRightNode = currentNode.rightNode;
				}
			}
		}
		System.out.println("root = " + root);
	}

查找方法

流程与插入方法类似。

Java代码:

public void query(int sortData) {
		Node currentNode = root;
		while (true) {
			if (sortData != currentNode.sortData) {
				if (sortData < currentNode.sortData) {
					if (currentNode.leftNode != null) {
						currentNode = currentNode.leftNode;
					} else {
						System.out.println("对不起没有查询到数据");
					}
				} else {
					if (currentNode.rightNode != null) {
						currentNode = currentNode.rightNode;
					} else {
						System.out.println("对不起没有查询到数据");
					}
				}
			} else {
				System.out.println("二叉树中有该数据");
			}
		}
	}
	

删除方法

删除节点要分三种情况.

• 删除节点无子节点的情况
• 删除节点有一个子节点的情况
• 删除节点有两个子节点的情况

1.删除节点无子节点的情况是最简单的,直接将该节点置为null就可以了:

2.删除节点有一个子节点的情况:

删除后结构为：

另一种只有一个删除节点的情况：

只有一个左子节点和只有一个右子节点

3.最复杂的删除节点有两个子节点的情况:

这种情况比较复杂是因为，需要寻找后继节点，即比要删除的节点的关键值次高的节点是它的后继节点。说得简单一些，后继节点就是比要删除的节点的关键值要大的节点集合中的最小值。

得到后继节点的代码如下:

public Node getSuccessor(Node delNode) {
		Node curr = delNode.rightNode;
		Node successor = curr;
		Node sucParent = null;
		while (curr != null) {
			sucParent = successor;
			successor = curr;
			curr = curr.leftNode;
		}
		if (successor != delNode.rightNode) {
			sucParent.leftNode = successor.rightNode;
			successor.rightNode = delNode.rightNode;
		}
		return successor;
	}

a)如果后继节点是刚好是要删除节点的右子节点

整理之后的结构为：

b)如果后继节点为要删除节点的右子节点的左后代：

整理之后的结构为：

	//删除节点：
	public boolean delete(int deleteData) {
		Node curr = root;
		Node parent = root;
		boolean isLeft = true;
		while (deleteData != curr.sortData) {
			if (deleteData <= curr.sortData) {
				isLeft = true;
				if (curr.leftNode != null) {
					parent = curr;
					curr = curr.leftNode;
				}
			} else {
				isLeft = false;
				if (curr.rightNode != null) {
					parent = curr;
					curr = curr.rightNode;
				}
			}
			if (curr == null) {
				return false;
			}
		} // 删除节点没有子节点的情况
		if (curr.leftNode == null && curr.rightNode == null) {
			if (curr == root) {
				root = null;
			} else if (isLeft) {
				parent.leftNode = null;
			} else {
				parent.rightNode = null;
			} // 删除节点只有左节点
		} else if (curr.rightNode == null) {
			if (curr == root) {
				root = root.leftNode;
			} else if (isLeft) {
				parent.leftNode = curr.leftNode;
			} else {
				parent.rightNode = curr.leftNode;
			} // 如果被删除节点只有右节点
		} else if (curr.leftNode == null) {
			if (curr == root) {
				root = root.rightNode;
			} else if (isLeft) {
				parent.leftNode = curr.rightNode;
			} else {
				parent.rightNode = curr.rightNode;
			}
		} else {
			Node successor = getSuccessor(curr);
			if (curr == root) {
				root = successor;
			} else if (curr == parent.leftNode) {
				parent.leftNode = successor;
			} else {
				parent.rightNode = successor;
			}
			successor.leftNode = curr.leftNode;
		}
		return true;
	}

为什么要以这种方式删除节点呢? 再次回顾一下二叉搜索树的特点:

• 一个节点的左子节点的关键字的值永远小于该节点的值
• 一个节点的右子节点的关键字的值永远大于等于该节点的值

之所以要找删除节点的右子节点的最后一个左节点,是因为这个值是删除节点的子节点中最小的值,为了满足上面的这两个特点,所以删除要以这种算法去实现。

遍历

遍历二叉树中的数据,有三种遍历方式:

• 前序
• 中序(最常用)
• 后续

前序、中序和后序三种遍历方式的步骤是相同的,只是顺序不同.

前序遍历顺序:

• 先输出当前节点
• 再遍历左子节点
• 再遍历右子节点

中序遍历顺序:

• 先遍历左子节点
• 再输出当前节点
• 再遍历右子节点

后序遍历顺序:

• 先遍历左子节点
• 再遍历又子节点
• 再输出当前节点

上述内容详细介绍：

前序遍历输出顺序图:

中序遍历输出顺序图:

后序遍历输出顺序图:

可以看出所谓的前中后序是输出当前节点的顺序,前序是在第一个输出当前节点,中序是第二个输出当前节点,后序是第三个当前节点.

又因为中序遍历是按照关键值由小到大的顺序输出的,所以中序遍历最为常用.

二叉树效率
我们用二叉树与数组和链表进行对比,在有100w个数据项的无序数组或链表中,查找数据项平均会比较50w次,但在有100w个节点的树中,只需要20(或更少)次的比较.

有序数组可以很快的找到数据项,但插入数据项平均需要移动50w个数据项,在100w个节点的树中插入数据项需要比较20或更少次的比较,再加上很短的时间来连接数据项.

同样,从有100w个数据项的数组中删除一个数据项需要平均移动50w个数据项,而在100w个节点的树中删除节点只需要20次或更少的比较来找到它,再加上(可能的话)一点比较的时间来找到它的后继,一点时间来断开这个节点的链接,以及连接它的后继.

结论: 树对所有常用的数据存储操作都有很高的效率

遍历不如其他操作快. 但是,遍历在大型数据库中不是常用的操作.它更长用于程序中的辅助方法来解析算术或其他的表达式,而且表达式一般都不会很长.

如果二叉树是平衡的,它的效率为: O(logN),如果二叉树是不平衡的(最极端的情况,存入树中的数据是升序或降序排列的,那么二叉树就是链表),效率为: O(N)

所以二叉搜索树在保存随机数值的时候,效率才是最高的

二叉树的缺点

如果二叉树是极端不平衡的(此时的二叉树就是一个链表),它的效率为O(N),即使数值是随机的,如果数据的量够大,也有可能有一部分的数值是有序的(就像你抛硬币的时间足够长,会有一段时间出现一直抛正面或反面),造成二叉树会变成是局部不平衡的,这样它的效率会介于O(logN)到O(N)。

以上为全部内容。