第三讲 树（上）

3.1 树与树的表示

1.查找

查找是指根据某个给定关键字K，从集合R中找出关键字与K相同的记录。它分为以下两类：

（1）静态查找：集合中记录是固定的，没有插入和删除操作。

（2）动态查找：集合中记录是动态变化的，除了查找，还可能发生插入和删除。

首先举一个顺序查找的例子。此例需要注意，其设置了一个哨兵，因此可以减少判断中的一个条件。这个例子要求是在Element[1]~Element[n]中查找关键字为K的数据元素，其结构体如下：

typedef struct LNode *List;
struct LNode{
       ElementType Element[MAXSIZE];
       int Length;
};

则查找算法代码如下：

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，结束

程序代码如下：

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层的最大结点数为：2^i-1，i≥1。

（2）深度为k的二叉树最大节点数是2^k-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

其代码表示如下：

typedef struct TreeNode *BinTree;
typedef BinTree Position:
struct TreeNode{
       ElementType Data;
       BinTree Left;
       BinTree Right;
};

5.二叉树的递归遍历

（1）先序遍历

遍历过程为：

①访问根结点；②先序遍历其左子树，先序遍历其右子树。

程序如下所示：

void PreOrderTraversal(BinTree BT)
{
       if(BT){
              printf("%d",BT->Data);
              PreOrderTraversal(BT->Left);
              PreOrderTraversal(BT->Right);
       }
}

（2）中序遍历

遍历过程为：

①中序遍历其左子树；②访问根结点；③中序遍历其右子树。

程序如下所示：

void InOrderTraversal(BinTree BT)
{
       if(BT){
              PreOrderTraversal(BT->Left);
              printf("%d",BT->Data);
PreOrderTraversal(BT->Right);
       }
}

（3）后序遍历

便利过程：

①后续遍历其左子树；②后续遍历其右子树；③访问根结点。

代码如下：

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推出堆栈

具体执行代码如下：

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;/*转向右子树*/
              }
       }
}

同理可得，中序遍历为：

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）若钙元素所指结点的左、右孩子结点费控，则将其左、右孩子的指针顺序入队。

不断执行这三步操作，直到队列为空，再无元素可取，二叉树的层序遍历就完成了。其代码如下所示：

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】遍历二叉树的应用：输出二叉树中的叶子结点。

void PreOrderTraversal(BinTree BT)
{
       if(BT){
              if(!BT->Left &&!BT->Right)
                     printf("%d",BT->Data);
              PreOrderTraversal(BT->Left);
              PreOrderTraversal(BT->Right);
       }
}

【例2】求二叉树的高度。

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.二叉树的创建

    由于树是非线性结构，创建一棵二叉树必须首先确定树种结点的输入顺序，常用的方法是先序创建和层序创建两种。