树的预备知识，基本术语，顺序查找（哨兵）和二分查找

树
客观世界中许多食物存在层次关系：人类社会家谱、社会组织结构、文件路径
分层次组织在管理上具有更高的效率
查找：静态查找：集合中的记录是固定不变的
哨兵，第一个字符放长度，在第零号位置存放我们要查找的字符，从后往前查找
动态查找：集合中的记录是动态变化的
静态查找
方法一：顺序查找：（哨兵）

1 typedef struct LNode *List;
2 strut LNode {
3 ElementType Element[MAXSIZE];
4 int length;
5 };

1 //查找的函数实现
2 int SequentialSearch(List Tb1, ElementType K)
3 {//在Element[1]~Element[n]中查找关键字为K的数据元素
4 int i;
5 Tb1->Element[0] = K; /*建立哨兵**/
6 for（i= Tb1->length; Tb1->Element[i] != K; i--);
7 return i;    //查找成功返回所在单元下标；不成功返回0
8 }

方法二、二分查找（Binary Search）
假设n个数据元素的关键字满足有序且是连续存放（在数组中），那么可以进行二分查找
在链表中则不能二分查找，无序也不能二分查找
left mid right
当right > left 时，查找失败
二分查找判定树：判定树上每个结点需要的查找次数刚好为该结点所在的层数
查找成功时不会超过判定树的深度
n个结点的判定树的深度为[log2n]+1

数的定义： n(n>=0)个结点构成的有限集合
n = 0 时为空树
根r(root)
字树：字树之间是不想交的，
除根节点外，每个结点有且仅有一个父节点
一棵N个结点的数有N-1条边
数是保证结点连通的边最少的一种连接方式

树的一些基本概念：
结点的度：（degree）结点的字树个数
树的度：
叶节点（Leaf ）：度为0的结点，没有字树的结点
父结点：（parent)有字树的结点是其字树的根节点的父节点
子节点：（child):
兄弟结点（（Sibling ）：具有同一父节点的各结点彼此是兄弟结点
路径和路径长度：从结点n 1 到到n k 的路径为一个结点序列n 1 , n 2 ,… , n k , n i 是是 n i+1 的父结
点。路径上边的条数就是路径长度

祖先结点(Ancestor) ：沿树根到某一节点路径上的所有结点都是这个结点的祖先结点
子孙结点(Descendant) ：某一节点的子树中所有结点是这个结点的子孙
结点的层次（Level ）：规定根结点在1层，其他任意结点的层数是其父节点的层数加一
树的深度（（Depth）：树中所有结点中的最大层次是这棵树的深度
任意结点的深度：从根结点到该结点的唯一路径的长度（所以根节点的深度为0）
结点的高：从该结点到一片树叶的最长路径的长（所以树叶的高为0）
后裔：
真后裔：
ASL = (4*4 + 4*3 + 2*2 +1） = 3 //平均成功查找次数

二分查找代码：

 1 int BinarySearch(StaTalbe *Tbl, ElementType K)
 2 {//在表TB了中查找关键字为K的数据元素
 3 int left, right, mid, NotFound = -1;
 4 left = 1;    //初始左边界
 5 right = Tbl->length;    //初始右边界
 6 while(left <= right)
 7 {
 8 mid = (left + right) / 2;    //计算中间元素坐标
 9 if(K < Tbl->element[mid]) right = mid - 1;    //调整有边界
10 else if(K > Tbl->element[mid] left = mid +1;    //调整做边界
11 else    return mid;    //查找成功，返回数据元素的下标
12 }
13 return NotFound;    //查找不成功，返回-1；
14 }

祖先结点(Ancestor) ：沿树根到某一节点路径上的所有结点都是这个结点的祖先结点

子孙结点(Descendant) ：某一节点的子树中所有结点是这个结点的子孙
结点的层次（Level ）：规定根结点在1层，其他任意结点的层数是其父节点的层数加一
树的深度（（Depth）：树中所有结点中的最大层次是这棵树的深度
任意结点的深度：从根结点到该结点的唯一路径的长度（所以根节点的深度为0）
结点的高：从该结点到一片树叶的最长路径的长（所以树叶的高为0）
后裔：
真后裔：