事物跟事物之间都存在层次关系。

比如，硬盘中有很多很多的文件，这也是在设计操作系统时考虑到的。在C盘中分成了若干个目录，在这些目录中有存在若干子目录，这也形成了一种层次关系。

这种关系就是”树”。

什么在数据结构中要提到”树”？为了更高的查找效率！

对数据管理中经常涉及三个典型的操作:插入、删除、查找。

3.1.1 引子(顺序查找-效率低)

静态查找:查字典。一般就是把某个集合放在数组或链表里，在数组中去找某个元素，最简单的一种方法就是顺序查找。

动态查找:比静态查找的难度要大。

顺序查找算法的时间复杂度为O(n)，平均为n/2，这样的一种查询效率显然不高，比如100万个数，要比较50万次。

/*
静态查找
方法1:顺序查找
用此结构来指向数组
*/
typedef struct LNode *List;
struct LNode{
	//此分量是指针指向数组的头
	ElementType Element[MAXSIZE];
	//此分量是代表这个数组中放多少个元素
	int Length;
}

方法一:静态查找(顺序查找- ”无哨兵” )

/*
静态查找
方法1:顺序查找
顺序查找的一种实现(无"哨兵")
*/
int SequentialSearch(List Tbl, ElementType K){
	int i;
	/*
	在Element[1]~Element[n]中查找关键字为K的数据元素
	*/
	/*
	何时会退出循环的条件:
	Tbl->Element[i] != K	元素是否相等
	i>0						每一轮循环都要对边界进行判断,通过下标来判断是否到边界/最后
从下标大的地方往前循环。
	*/
	for(i = Tbl->Length; i>0 && Tbl->Element[i] != K; i--);
	/*
	查找成功返回所在单元下标,不成功返回0.
	*/
	return i;
}

方法一:静态查找(顺序查找- ”有哨兵” )

/*
静态查找
方法1:顺序查找
顺序查找的一种实现(有"哨兵")
*/
int SequentialSearch(List Tbl, ElementType K){
	int i;
	/*
	在Element[1]~Element[n]中查找关键字为K的数据元素
	*/
	Tbl->Element[0] = K;//建立哨兵
	/*
	何时会退出循环的条件:
	Tbl->Element[i] != K	元素是否相等
	i>0(注意这里是和无"哨兵"最大的区别,是没有这个判断)
	从下标大的地方往前循环。
	*/
	for(i = Tbl->Length; Tbl->Element[i] != K; i--);
	/*
	查找成功返回所在单元下标,不成功返回0.
	*/
	return i;
}

方法二:静态查找( 二分查找 -案例 )

A地到B地有100公里，每50米一根电线，如果某根断了，那么如何查找？

比如有100万个电线杆，一根根去爬，平均要爬50万次。

如果每次一半半的查找，要爬次数:log2的1000000，即20次。

这就是二分查找的效率。

要求数组存放于数组中，且先决条件为有序排放，比如从小到大排放。

发现100比444小，那么444肯定在100之后。注意挪动的位置是取整。

下标4-6中间，取中间值51。

再跟43比较，51比43大，修改right，再求中间值。

发现left和right都等于4，中间位置依然是4，45再次去和43比较，45大于43，再次修改right。

现在right指针跑到了left的左边，查找方位不存在，所以43不在此区间中。

方法二:静态查找( 二分查找 -实现 )

/*
静态查找
方法2:二分查找
1)二分查找算法具有对数的时间复杂度O(logN),
每次都把查找范围减掉了一半,不断的减掉一半,循环次数肯定是除以2,除多少次就达到1,
那么通过事先进行的排序,可以把查找效率得到很大的提升,
当查找数等于100万的时候,原来平均要找50万次,现在只要平均查找20次。
2)为什么二分查找会产生那么好的效率呢?
基本前提:对查找的集合进行有序化的处理。
*/
int BinarySearch(StaticTable *Tbl, ElementType K){
	/*
	在Tbl中查找关键字为K的数据元素
	*/
	int left, right, mid, NoFound = -1;
	//初始左边界
	left = 1;
	//初始右边界
	right = Tbl->Length;
	while(left <= right){
		//计算中间元素坐标
		mid = (left + right)/2;
		//调整右边界
		if(K < Tbl->Element[mid]){
			right = mid - 1;
		}
		//调整左边界
		else if(K > Tbl->Element[mid]){
			left = mid + 1;
		}
		//查找成功,返回数据元素的下标
		else{
			return mid;
		}
	}

}

方法二:静态查找(11个元素的二分查找判定树 )

比较的数，先跟6比较，前半段还是后半段，前半段是3位置，否则在9位置，往下同理，这个比较的顺序，形成了一个层次结构，一棵树。

如果要找的元素，正好位于4这个位置，那么比较的次数，正好就是它所在的层次。

整个树的总层次是[log以2为底N的对数]+1，而[log以2为底N的对数]是取整，比如等于11，那么[log以2为底N的对数]应该是3点多，取整是3加1等于4，可以说，其总层次代表了查找最坏情况的一种效率。

那么平均查找次数，比如找1号位置，要找几次，这个叫做ASL平均查找次数。此时一共有11个元素，这里第4层需要查找4次的有4个结点，第3层需要查找3次的有4个结点，第2层需要查找2次的有2个结点，第1层需要查找1次的有1个结点，这些加起来再除以11就等于3。

数据存储:数组OR树

此时，在数组中，是一种有序化的数据组织形式，而这个顺序是形成类似像树这样的一种结构。

那么，数据能否不放在数组中，而按照层次化的结构来存储数据，也能达到二分查找一样的效果？

可以用树这种形式来存储需要的数据，使得查找过程更加方便，效率差不多也能达到[log以2为底N的对数]，最大的一个优点，在树中插入和删除结点时，比在数组中方便，这里通过动态查找的形式可以很好的解决，也就是动态查找问题。

3.1.4 树的定义和术语

树其实采用了一种递归的方法。

A是由下面的四颗子树构成的，分别是以BCDE为根的子树bcde构成。

G也是一颗子树，结点只有一个L，其根就是G。

这些子树中:D与C相交，C与E相交，D与G相交，所以这些不是树。

除了根，每个结点网上的一条边只有一条。

树，实际上把所有的结点都连接在了一起，随便拿掉树中的一条边，就不会连接在一起了，也可以说，树是保证结点联通的最小的一种连接方式。

每个结点都有一个边连接到上面或下面去，连接到下面边的个数，称为结点的度。

比如A结点的度是3，下面有BCD。

所谓路径是指一个结点到另一个结点的路径，它是一个结点的序列，在这个序列中，前后结点之间都有边相连，或者说，前一个结点是下一个结点的父亲，那么这样就从上往下形成了一条路径，路径的长度就是在这个路径上面边的个数。

3.1.5 树的表示 (儿子-兄弟/二叉树)

树如果用数组表示，那么这些结点按顺序存储在数组中，实现难度比较大，因为很难判断一个结点的父子结点是谁。

树如果用链表表示，即，每个结点用同一个结构来表示，用此结构加链表的形式表示树，但每个结点的样子不同，不同结点的指针域个数不同，无法知道多少子结点。

另外，把每个结点设计成同样的结构，每个结点都设计成3个指针，即，结构都是统一的，

带来的问题就是，如果每个结点都有3个指针域，那么整个树就会有3N个指针域，实际上的边只有N-1条，也就是说只有N-1个指针是非零的，这样就会有2N+1个指针域是空的，会造成一种空间上的浪费。

比较好的方法是使用下述”儿子-兄弟表示法”。

采用的方法是，树上的每个结点的结构都是统一的，两个指针域，第一个指针域指向它的第一个儿子，右边的指针域指向它的下一个兄弟，所有的结点都以这种方式来指向儿子跟兄弟，这样就可以把整棵树的结点都串起来了。

比如B的兄弟有两个，C跟D，对于C来讲，下一个兄弟就是D，D左边这个指针指向第一个儿子H，右边指针指向它的下一个兄弟没有。

这样的优点，树中的每个结点结构都是统一的，都是两个指针域，同时其空间浪费也不大，N个结点，2N个指针域，其中N-1条边，所以意味着有N-1个指针域是非空的，真正空的指针域是N+1。

把这样的一个链表实现方法，旋转45°，此时看到的是一棵树，这棵树的特点是每一个结点都有两个指针域，一个指向左边，一个指向右边，每个结点最多两个儿子，这种树叫做二叉树。

二叉树就是度为2的这样一种树，就是每个结点的指针最多两个，一般的树都可以使用”儿子-兄弟表示法”这样的一种表示方法，用二叉树链表这种形式来实现。

搞懂二叉树最核心、最基础的操作实现，实际上就解决了一般树的很多问题，二叉树在树结构研究里是最重要的内容。