第三讲 树（上）
3.1 树与树的表示
1.查找
查找是指根据某个给定关键字K，从集合R中找出关键字与K相同的记录。它分为以下两类：
（1）静态查找：集合中记录是固定的，没有插入和删除操作。
（2）动态查找：集合中记录是动态变化的，除了查找，还可能发生插入和删除。
首先举一个顺序查找的例子。此例需要注意，其设置了一个哨兵，因此可以减少判断中的一个条件。这个例子要求是在Element[1]~Element[n]中查找关键字为K的数据元素，其结构体如下：
| 1 2 3 4 5 | typedef struct LNode *List; struct LNode{ ElementType Element[MAXSIZE]; int Length; }; |
则查找算法代码如下：
| 1 2 3 4 5 6 7 | int SequentialSearch(List Tb1, ElementType K) { int i; Tb1->Element[0]=K;/*建立哨兵*/ for(i-Tb1->Length;Tb1->Element[i]!=K;i--); return i;/*查找成功返回下标，不成功返回0*/ } |
时间复杂性O(n)。
再举一个二分查找的例子。二分查找遵循以下要求：假设n个数据元素的关键字满足有序，并且是连续存放。
例如，假设有13个数据元素，按照关键字由小到大顺序存放，二分查找关键字为444的数据。
5 | 16 | 39 | 45 | 51 | 98 | 100 | 202 | 226 | 321 | 368 | 444 | 501 |
理论步骤是如表1.1所示。
表1.1 二分法步骤
left | right | mid | value | comparsion |
1 | 13 | 7 | 100 | 100<444，右侧 |
8 | 13 | 10 | 321 | 321<444，右侧 |
11 | 13 | 12 | 444 | 444=444，结束 |
程序代码如下：
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | int BinarySearch(List Tbl, ElementType K) { int left, right, mid, NoFount = -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; } return NotFound; } |
时间复杂度是O(logN)。
2.树的定义和术语
树（Tree）：n（n≥0）个结点构成的有限集合。当n=0时，称为空树。
对于任一棵非空树（n>0），它具备以下性质：
（1）树种有一个称为根的特殊结点，用r表示；
（2）其余结点可分为m（m＞0）个互不相交的有限集T1，T2，…，Tm，其中每个集合本身又是一棵树，称为原来树的“子树”。
（3）子树是不相交的；
（4）除了根结点外，每个结点有且只有一个父节点；
（5）一棵N个结点的树有N-1条边。
树的一些基本术语：
（1）结点的度：结点子树个数。
（2）树的度：树的所有结点中最大的度数。
（3）叶结点：度为0的结点。
（4）父结点：有子树的结点是其子树的根结点的父结点。
（5）子结点：若A结点是B结点的父结点，则称B结点是A结点的子结点。
（6）兄弟结点：具有同一父结点的各结点彼此是兄弟结点。
（7）路径和路径长度：从结点n1到nk的路径为一个结点序列n1，n2，…nk，其中ni是ni+1的父结点。路径所包含边的个数为路径的长度。
（8）祖先结点：沿树根到某一结点路径上的所有结点都是这个结点的祖先结点。
（9）子孙节点：某一结点的子树中的所有结点是这个结点的子孙。
（10）结点的层次：规定根结点在1层，其它任一结点的层数是其父结点的层数加1。
（11）树的深度：树种所有结点总的最大层次是这棵树的深度。
3.树的表示
数组、链表都是很难表示树的，因为树的结构是多变的，无法统一规定。因此在这里用“儿子-兄弟表示法”，结构如下面所示。
Element | |
FirstChild | NextSibling |
如图1左所示的树结构可以表示为图1右所示的表示法。
图1
把这个树往右转向45°，可以看出，这是一个度为2的树。这种方法也被称为——二叉树。
3.2 二叉树
1.二叉树的定义
二叉树T：一个有穷的结点集合。这个集合可以为空。若不为空，则它是由根结点和称为其左子树TL和右子树TR的两个不相交的二叉树组成。
二叉树的五种基本形态如图2所示，几种特殊二叉树如图3所示。
图2
图3
对完全二叉树左一个说明。完全二叉树可以是满二叉树缺少最低一层最右侧几个，只要前面都对的起来即可，但是绝不能在中间缺几个（如图3右下角）。
2.二叉树的几个重要性质
（1）一个二叉树第i层的最大结点数为：2i-1，i≥1。
（2）深度为k的二叉树最大节点数是2k-1，k≥1。
（3）对任何非空二叉树T，若n0表示叶结点的个数，n2是度为2的非叶结点个数，那么两者满足n0=n2+1。
3.二叉树的抽象数据类型定义
类型名称：二叉树
数据对象集：一个有穷的结点集合。若不为空，则由根结点和其左、右二叉子树组成。
操作集：BT∈BinTree，Item∈ElementType，重要的操作有：
（1）Boolean IsEmpty(BinTree BT)：判断BT是否为空；
（2）void Traversal(BinTree BT)：遍历，按某顺序访问每个结点；
（3）BinTree CreatBinTree()：创建一个二叉树。
二叉树常用的便利方法有：
（1）void PreOrderTraversal(BinTree BT)：先序——根、左子树、右子树；
（2）void InOrderTraversal(BinTree BT)：中序——左子树、根、右子树；
（3）void PostOrderTraversal(BinTree BT)：后序：左子树、右子树、根；
（4）void LevelOrderTraversal(BinTree BT)：层次遍历：从上到下、从左到右。
4.二叉树的存储结构
（1）顺序存储结构
完全二叉树：按从上至下、从左到右顺序存储，n个结点的完全二叉树的结点父子关系，可以使用顺序存储结果。如图4所示。
图4
这个完全二叉树很有规律，很容易找到其父结点和子结点。我们可以发现：
①非根节点（序号i>1）的父结点的序号是[i/2]（在这里[]表示取整）；
②结点（序号为i）的左孩子结点序号为2i（若2i>=n，就没有左孩子）；
③结点（序号为i）的右孩子结点序号为2i+1（若2i+1>=n，就没有右孩子）。
推广来说，一般二叉树也可以采用这种结构，方法就是通过补空位使其变成完全二叉树。但这样的结果是会造成空间浪费。
（2）链表存储
一般二叉树的结点可以用下面的方式表示：
Left | Data | Right |
其代码表示如下：
| 1 2 3 4 5 6 7 | typedef struct TreeNode *BinTree; typedef BinTree Position: struct TreeNode{ ElementType Data; BinTree Left; BinTree Right; }; |
5.二叉树的递归遍历
（1）先序遍历
遍历过程为：
①访问根结点；②先序遍历其左子树，先序遍历其右子树。
程序如下所示：
| 1 2 3 4 5 6 7 8 | void PreOrderTraversal(BinTree BT) { if(BT){ printf("%d",BT->Data); PreOrderTraversal(BT->Left); PreOrderTraversal(BT->Right); } } |
（2）中序遍历
遍历过程为：
①中序遍历其左子树；②访问根结点；③中序遍历其右子树。
程序如下所示：
| 1 2 3 4 5 6 7 8 | void InOrderTraversal(BinTree BT) { if(BT){ PreOrderTraversal(BT->Left); printf("%d",BT->Data); PreOrderTraversal(BT->Right); } } |
（3）后序遍历
便利过程：
①后续遍历其左子树；②后续遍历其右子树；③访问根结点。
代码如下：
| 1 2 3 4 5 6 7 8 | void PostOrderTraversal(BinTree BT) { if(BT){ PreOrderTraversal(BT->Left); PreOrderTraversal(BT->Right) printf("%d",BT->Data);; } } |
6.二叉树的非递归遍历（以中序为例）
基本思路：使用堆栈。
如图5所示的二叉树，我们以此未来来介绍利用堆栈进行处理的方法，输出顺序为：DBEFAGHCI。处理的方法见表3.1所示。
图5
表3.1 使用堆栈算法的表格示意
序号 | 当前结点 | 堆栈（从左到右相当于从底到顶） | 步骤说明 |
1 | A | [A] | 首先把A压入堆栈 |
2 | B | [AB] | B为A的左孩子，压入堆栈 |
3 | D | [ABD] | D为B的左孩子，压入堆栈 |
4 | [AB] | D无孩子，将D推出堆栈 | |
5 | [A] | 将B推出堆栈 | |
6 | F | [AF] | 由于F为B右孩子，在B推出时将F压入堆栈 |
7 | E | [AFE] | E为F左孩子，压入堆栈 |
8 | [AF] | E无孩子，将E推出堆栈 | |
9 | [A] | 将F推出堆栈 | |
10 | [] | 将A推出堆栈 | |
11 | C | [C] | 将G压入堆栈 |
12 | G | [CG] | G为C的左孩子，压入堆栈 |
13 | [C] | G没有左孩子，G推出堆栈 | |
14 | H | [CH] | 将G的右孩子压入堆栈 |
15 | [C] | H无孩子，H推出堆栈 | |
16 | [] | 将C推出堆栈 | |
17 | I | [I] | 将I压入堆栈 |
18 | [] | 将I推出堆栈 |
具体执行代码如下：
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | void InOrderTraversal(BinTree BT) { BinTree T=BT; Stack S=CreatStack(MaxSize);/*创建并初始化堆栈S*/ while(T||!IsEmpty(S)){ while(T) {/*一致向左将沿途结点压入堆栈*/ Push(S,T); T=T->Left; } if(!IsEmpty(S)) { T= Pop(S);/*结点弹出堆栈*/ printf("%5d",,T->Data);/*打印结点*/ T=T->Right;/*转向右子树*/ } } } |
同理可得，中序遍历为：
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | void PreOrderTraversal(BinTree BT) { BinTree T=BT; Stack S=CreatStack(MaxSize);/*创建并初始化堆栈S*/ while(T||!IsEmpty(S)){ while(T) {/*一致向左将沿途结点压入堆栈*/ printf("%5d",,T->Data);/*打印结点*/ Push(S,T); T=T->Left; } if(!IsEmpty(S)) { T= Pop(S);/*结点弹出堆栈*/ T=T->Right;/*转向右子树*/ } } } |
7.层序遍历
层次遍历是利用队列的方式进行。遍历从根结点开始，首先将根结点指针入队，然后开始执行下面三个操作：
（1）从队列中取出一个元素；
（2）访问该元素所指结点；
（3）若钙元素所指结点的左、右孩子结点费控，则将其左、右孩子的指针顺序入队。
不断执行这三步操作，直到队列为空，再无元素可取，二叉树的层序遍历就完成了。其代码如下所示：
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | void LevelOrderTraversal(BinTree BT) { BinTree T; Queue Q; if(!BT) return;/*空树直接返回*/ Q = CreatQueue(MaxSize); AddQ(Q,BT); while(!IsEmptyQ(Q)){ T = DeleteQ(Q); printf("%d\n",T->Data); /*访问取出队列的结点*/ if(T->Left) AddQ(Q,T->Left); if(T->Right) AddQ(Q,T->Right); } } |
8.遍历应用的例子
【例1】遍历二叉树的应用：输出二叉树中的叶子结点。
| 1 2 3 4 5 6 7 8 9 | void PreOrderTraversal(BinTree BT) { if(BT){ if(!BT->Left &&!BT->Right) printf("%d",BT->Data); PreOrderTraversal(BT->Left); PreOrderTraversal(BT->Right); } } |
【例2】求二叉树的高度。
| 1 2 3 4 5 6 7 8 9 10 11 | int PostOrderGetHeight(BinTree BT) { int HL,HR,MaxH; if(BT){ HL = PostOrderGetHeight(BT->Left); HR = PostOrderGetHeight(BT->Right); MaxH = (HL>HR)?HL:HR; return MaxH+1; } else return 0; } |
【例3】二元运算表达式树及其遍历
如图6所示。
图6
三种遍历可以得到三种不同的访问结果：
（1）中序遍历得到中缀表达式：a + b * c + d * e + f * g
（2）先序遍历得到前缀表达式：+ + a * b c * + * d e f g
（3）后序遍历得到后缀表达式：a b c * + d e * f + g * +
由此直接将表达式存入链表就可以了。
【例4】由两种遍历序列确定二叉树：已知三种遍历中的任意两种遍历序列，能否唯一确定一棵二叉树呢？
只需要确保其中一个是中序遍历，就可以唯一确定。如果只有前序遍历、后序遍历，这就不可能找到唯一的。
下面以先序和中序遍历序列来确定一棵二叉树。
先序遍历序列的第一个结点就是根结点。这个根结点能够在中序遍历序列中将其余结点分割成两个子序列，根结点前面部分是左子树上的结点，而根结点后面的部分是右子树上的结点。
根据这两个子序列，在先序序列中找到对应的左子序列和右子序列，它们分别对应左子树和右子树。
然后对左子树和右子树分别递归使用相同的方法继续分解。
9.二叉树的创建
由于树是非线性结构，创建一棵二叉树必须首先确定树种结点的输入顺序，常用的方法是先序创建和层序创建两种。
