数据结构第六章 树

1、第6章 树 本章中主要介绍下列内容：l 树的逻辑定义和存储结构l 二叉树的逻辑定义、存储结构l 二叉树的基本操作算法l 树和二叉树的转换l 哈夫曼树及其应用n6.1 树的概念与定义n6.2 二叉树n6.3 二叉树的遍历n6.5 树与森林n6.6 哈夫曼树及其应用章节安排：家谱结构：张源张源张明张亮张维张丽张平张群张林张华张晶张垒6.1 6.1 树的概念树的概念 6.1.1 6.1.1 树的定义树的定义 定义： 树是一种常用的非线性结构。我们可以这样定义：树是n（n0）个结点的有限集合。若n=0，则称为空树；1）否则，有且仅有一个特定的结点被称为根，2）当n1时，其余结点被分成m（m0）个互不相

2、交的子集T1，T2，.，Tm，每个子集又是一棵树。由此可以看出，树的定义是递归。图 6-1 E F G H I J B C DAA(a)(b)(c)树逻辑结构：n树中任一结点都可以有零个或多个后继（即孩子）结点，但至多只能有一个前驱（即双亲）结点。n只有根结点无前驱；n只有叶结点无后继；树的多种多种表示：A B E F I JCD G HIJECGHDBA( A(B(E, F(I, J), C, D(G, H) )F结点 数据元素的内容及其指向其子树根的分支统称为结点。结点的度 结点的分支数,也即子树的个数。树的度 树中所有结点度的最大值。终端结点（叶子） 度为0的结点。非终端结点（分支结点）

3、 度不为0的结点。内部结点 除根结点外的分支结点树的基本概念与术语（一）在树结构中，结点之间的关系又可以用家族关系描述，在树结构中，结点之间的关系又可以用家族关系描述，定义如下：定义如下： 孩子、双亲 结点子树的根称为这个结点的孩子，而这个结点又被称为孩子的双亲。 兄弟 同一个双亲的孩子之间互为兄弟。 堂兄弟 双亲在同一层的结点互为堂兄弟。 路径及其长度 若树中存在一个结点序列K1，K2Kj，使得Ki是Ki+1(1=i0时，有且仅有一个结点为二叉树的根，其余结点被分成两个互不相交的子集，一个作为左子集，另一个作为右子集，每个子集又是一个二叉树。G HD E FB CA二叉树的5种形态：图图 5

4、-7(a)(b)(c)(d)(e)6.2.2 6.2.2 二叉树的4个重要性质 【性质1】 在二叉树的第i层上最多有2i-1个结点（i1）。 二叉树的第1层只有一个根结点，所以，i=1时，2i-1=21-1 =20=1成立。 假设对所有的j，1ji成立，即第j层上最多有2j-1个结点成立。若j=i-1，则第j层上最多有2j-1=2i-2个结点。只要证明j=i时，命题成立。由于在二叉树中，每个结点的度最大为2，所以可以推导出第i层最多的结点个数就是第i-1层最多结点个数的2倍，即2i-2*2 =2i-1。【性质2】 深度为K的二叉树最多有2K-1个结点（K1）。qqaaSnn1*1 由性质1可以

5、得出，1至K层各层最多的结点个数分别为：20,21,22,23,.,2K-1。这是一个以2为比值的等比数列，前n项之和的计算公式为：12212*1202KK证明：假设度为1的结点个数为n1，结点总数为n，B为二叉树中的分支数。 因为在二叉树中，所有结点的度均小于或等于2，所以结点总数为：n=n0+n1+n2 （1） 再查看一下分支数。在二叉树中，除根结点之外，每个结点都有一个从上向下的分支指向，所以，总的结点个数n与分支数B之间的关系为： n=B+1。【性质3】 对于任意一棵二叉树，如果度为0的结点个数为n0，度为2的结点个数为n2，则n0=n2+1。 又因为在二叉树中，度为1的结点产生1个分

6、支，度为2的结点产生2个分支，所以分支数B可以表示为：B=n1+2n2。 将此式代入上式，得：n=n1+2n2+1 （2） 用（1）式减去（2）式，并经过调整后得到：n0=n2+1。 满二叉树： 如果一个深度为K的二叉树拥有2K-1个结点，则将它称为满二叉树。满二叉树满二叉树 8 9 10 11 12 13 14 154 5 6 72 31 完全二叉树完全二叉树：有一棵深度为h，具有n个结点的二叉树，若将它与一棵同深度的满二叉树中的所有结点按从上到下，从左到右的顺序分别进行编号，且该二叉树中的每个结点分别与满二叉树中编号为1n的结点位置一一对应，则称这棵二叉树为完全二叉树。或者若一颗二叉树至多

7、只有最下面的两层上结点的度数可以小于2，并且最下一层上的结点都集中在该层最左边的若干位置上。完全二叉树完全二叉树 8 9 10 11 12 13 144 5 6 72 31 证明：假设具有n个结点的完全二叉树的深度为K，则根据性质2可以得出： 2K-1-1 n 2K-1 将不等式两端加1得到： 2K-1 n 2K 将不等式中的三项同取以2为底的对数，并经过化简后得到： K-1 log2n K 由此可以得到：log2n =K-1。整理后得到：K= log2n+1。【性质4】 具有n个结点的完全二叉树的深度为 log2n+1。其中，log2n 的结果是不大于log2n的最大整数。6.2.3 二叉树

8、的抽象数据类型二叉树的抽象数据类型ADT BinaryTree 数据对象D: 数据关系R： 基本操作P： P121 - P122 二叉树也可以采用两种存储方式：顺序存储结构和链式存储结构。6.3.1 顺序存储结构 把二叉树所有的结点，按照一定的次序顺序，存储到一片连续的存储单元中。 问题：如何体现结点间的逻辑关系？6.3 二叉树的存储结构二叉树的存储结构完全二叉树结点间逻辑关系（1）84 5 6 72 31 N个结点 自上到下，从左往右编号完全二叉树结点间逻辑关系（2） 编号为i的结点是Ki（1= i 1, Ki的双亲就是 i/2 ；i=1, Ki是根，无双亲。n若2i=N, Ki的左孩子是编

9、号为2i；否则无左孩子，即Ki是叶结点。n若2i+1data = ch; s-lchild = NULL; s-rchild = NULL; rear +; Qrear = s; if ( rear = 1 ) root = s; else if (s & Qfront) if (rear % 2 = 0) Qfront-lchild = s; else Qfront-rchild = s; if (rear % 2 = 1) front +; Ch = getchar(); Return root; 二叉树是一种非线性的数据结构，在对它进行操作时，总是需要逐一对每个数据元素实施操作，

10、这样就存在一个操作顺序问题，由此提出了二叉树的遍历操作。所谓遍历二叉树就是按某种顺序访问二叉树中的每个结点一次且仅一次的过程。这里的访问可以是输出、比较、更新、查看元素内容等等各种操作。 二叉树的遍历方式分为两大类：二叉树的遍历方式分为两大类：一类按根、左子树和右子树三个部分进行访问；另一类按层次访问。下面我们将分别进行讨论。6.4 遍历二叉树遍历二叉树 1. 按根、左子树和右子树三部分进行遍历 遍历二叉树的顺序存在下面6种可能： TLR（根左右）, TRL（根右左） LTR（左根右）, RTL（右根左） LRT（左右根）, RLT（右左根） 其中，TRL、RTL和RLT三种顺序在左右子树之间

11、均是先右子树后左子树，这与人们先左后右的习惯不同，因此，往往不予采用。余下的三种顺序TLR、LTR和LRT根据根访问的位置不同分别被称为先序遍历、中序遍历和后序遍历。1 递归算法递归算法算法的递归定义是：算法的递归定义是：若二叉树为空，则遍历结束；否则若二叉树为空，则遍历结束；否则 访问根结点；访问根结点； 先序遍历左子树先序遍历左子树(递归调用本算法递归调用本算法)； 先序遍历右子树先序遍历右子树(递归调用本算法递归调用本算法)。6.3.1 先序遍历二叉树先序遍历二叉树void PreorderTraverse(BTNode *T) if (T!=NULL) visit(T-data) ;

12、/* 访问根结点访问根结点 */PreorderTraverse(T-Lchild) ;PreorderTraverse(T-Rchild) ; 说明：说明：visit()函数是访问结点的数据域，其要求视具体问题函数是访问结点的数据域，其要求视具体问题而定。树采用二叉链表的存储结构，用指针变量而定。树采用二叉链表的存储结构，用指针变量T T来指向。来指向。先序遍历的递归算法先序遍历的递归算法2 非递归算法非递归算法n设设T是指向二叉树根结点的指针变量，非递归算法是：是指向二叉树根结点的指针变量，非递归算法是：n若二叉树为空，则返回；否则，令若二叉树为空，则返回；否则，令p=T； 访问访问p所指

13、向的结点；所指向的结点； q=p-Rchild ，若，若q不为空，则不为空，则q进栈；进栈； p=p-Lchild ，若，若p不为空，转不为空，转(1)，否则转，否则转(4)； 退栈到退栈到p ，转，转(1)，直到栈空为止。，直到栈空为止。 算法实现算法实现：#define MAX_NODE 50void PreorderTraverse( BTNode *T) BTNode *StackMAX_NODE ,*p=T, *q ;int top=0 ;if (T=NULL) printf(“ Binary Tree is Empty!n”) ;else do visit( p- data ) ;

14、 q=p-Rchild ; if ( q!=NULL ) stack+top=q ; p=p-Lchild ; if (p=NULL) p=stacktop ; top- ; while (p!=NULL) ;1 递归算法递归算法算法的递归定义是：算法的递归定义是： 若二叉树为空，则遍历结束；否则若二叉树为空，则遍历结束；否则 中序遍历左子树中序遍历左子树(递归调用本算法递归调用本算法)； 访问根结点；访问根结点； 中序遍历右子树中序遍历右子树(递归调用本算法递归调用本算法)。6.3.2 中序遍历二叉树中序遍历二叉树void InorderTraverse(BTNode *T) if (T!=

15、NULL) InorderTraverse(T-Lchild) ;visit(T-data) ; /* 访问根结点访问根结点 */InorderTraverse(T-Rchild) ; /*图图6-8(a) 的二叉树，输出的次序是：的二叉树，输出的次序是： cbegdfa */中序遍历的递归算法中序遍历的递归算法2 非递归算法非递归算法设设T是指向二叉树根结点的指针变量，非递归算法是：是指向二叉树根结点的指针变量，非递归算法是：n若二叉树为空，则返回；否则，令若二叉树为空，则返回；否则，令p=T 若若p不为空，不为空，p进栈，进栈， p=p-Lchild ； p为空，退栈到为空，退栈到p，访问

16、，访问p所指向的结点；所指向的结点； p=p-Rchild ，转，转(1)；直到栈空为止。直到栈空为止。 算法实现算法实现：#define MAX_NODE 50void InorderTraverse( BTNode *T) BTNode *StackMAX_NODE ,*p=T ; int top=0 , bool=1 ; if (T=NULL) printf(“ Binary Tree is Empty!n”) ; else do while (p!=NULL) stack+top=p ; p=p-Lchild ; if (top=0) bool=0 ; else p=stacktop

17、; top- ; visit( p-data ) ; p=p-Rchild ; while (bool!=0) ; 1 递归算法递归算法算法的递归定义是：算法的递归定义是： 若二叉树为空，则遍历结束；否则若二叉树为空，则遍历结束；否则 后序遍历左子树后序遍历左子树(递归调用本算法递归调用本算法)； 后序遍历右子树后序遍历右子树(递归调用本算法递归调用本算法) ； 访问根结点访问根结点 。6.3.3 后序遍历二叉树后序遍历二叉树后序遍历的递归算法后序遍历的递归算法void PostorderTraverse(BTNode *T) if (T!=NULL) PostorderTraverse(T-

18、Lchild) ;PostorderTraverse(T-Rchild) ; visit(T-data) ; /* 访问根结点访问根结点 */ / /* *图图6-8(a) 的二叉树，输出的次序是：的二叉树，输出的次序是： cgefdbacgefdba * */ / 遍历二叉树的算法中基本操作是访问结点，因此，无论是哪遍历二叉树的算法中基本操作是访问结点，因此，无论是哪种次序的遍历，对有种次序的遍历，对有n个结点的二叉树，其时间复杂度均为个结点的二叉树，其时间复杂度均为O(n) 。 如图如图6-9所示的二叉树表示表达式：所示的二叉树表示表达式：(a+b*(c-d)-e/f)按不同的次序遍历此二

19、叉树，将访问的结点按先后次序按不同的次序遍历此二叉树，将访问的结点按先后次序排列起来的次序是：排列起来的次序是： 其先序序列为：其先序序列为： -+a*b-cd/ef 其中序序列为：其中序序列为： a+b*c-d-e/f 其后序序列为：其后序序列为： abcd-*+ef/-/fe-dcb*a+图图6-9 表达式表达式 (a+b*(c-d)-e/f)二叉树二叉树2 非递归算法非递归算法 在后序遍历中，根结点是最后被访问的。因此，在后序遍历中，根结点是最后被访问的。因此，在遍历过程中，当搜索指针指向某一根结点时，不在遍历过程中，当搜索指针指向某一根结点时，不能立即访问，而要先遍历其左子树，此时能立

20、即访问，而要先遍历其左子树，此时根结点进根结点进栈栈。当其左子树遍历完后再搜索到该根结点时，还。当其左子树遍历完后再搜索到该根结点时，还是不能访问，还需遍历其右子树。所以，此是不能访问，还需遍历其右子树。所以，此根结点根结点还需再次进栈还需再次进栈，当其右子树遍历完后再退栈到到该，当其右子树遍历完后再退栈到到该根结点时，才能被访问。因此，设立一个状态标志根结点时，才能被访问。因此，设立一个状态标志变量变量tag ：0 ： 结点暂不能访问结点暂不能访问1 ： 结点可以被访问结点可以被访问tag= 其次，设两个堆栈其次，设两个堆栈S1、S2 ，S1保存结点，保存结点，S2保存结保存结点的点的状态标

21、志变量状态标志变量tag 。S1和和S2共用一个栈顶共用一个栈顶指针。指针。 设设T是指向根结点的指针变量，非递归算法是：是指向根结点的指针变量，非递归算法是：若二叉树为空，则返回；否则，令若二叉树为空，则返回；否则，令p=T； 第一次经过根结点第一次经过根结点p，不访问：，不访问： p进栈进栈S1 ， tag 赋值赋值0，进栈，进栈S2，p=p-Lchild 。 若若p不为空，转不为空，转(1)，否则，取状态标志值，否则，取状态标志值tag ： 若若tag=0：对栈：对栈S1，不访问，不出栈；修改，不访问，不出栈；修改S2栈顶栈顶元素值元素值(tag赋值赋值1) ，取，取S1栈顶元素的右子树

22、，即栈顶元素的右子树，即p=S1top-Rchild ，转，转(1)； 若若tag=1：S1退栈，访问该结点；退栈，访问该结点；直到栈空为止。直到栈空为止。算法实现：算法实现：#define MAX_NODE 50void PostorderTraverse( BTNode *T) BTNode *S1MAX_NODE ,*p=T ;int S2MAX_NODE , top=0 , bool=1 ;if (T=NULL) printf(“Binary Tree is Empty!n”) ;else do while (p!=NULL) S1+top=p ; S2top=0 ; p=p-Lchi

23、ld ; if (top=0) bool=0 ; else if (S2top=0) p=S1top-Rchild ; S2top=1 ; else p=S1top ; top- ; visit( p-data ) ; p=NULL ; /* 使循环继续进行而不至于死循环使循环继续进行而不至于死循环 */ while (bool!=0) ;6.3.4 层次遍历二叉树层次遍历二叉树 层次遍历二叉树，是从根结点开始遍历，按层次次层次遍历二叉树，是从根结点开始遍历，按层次次序序“自上而下，从左至右自上而下，从左至右”访问树中的各结点。访问树中的各结点。 为保证是按层次遍历，必须设置一个队列，初始化为

24、保证是按层次遍历，必须设置一个队列，初始化时为空。时为空。 设设T是指向根结点的指针变量，层次遍历非递归算是指向根结点的指针变量，层次遍历非递归算法是：法是：若二叉树为空，则返回；否则，令若二叉树为空，则返回；否则，令p=T，p入队；入队； 队首元素出队到队首元素出队到p； 访问访问p所指向的结点；所指向的结点； 将将p所指向的结点的左、右子结点依次入队。直所指向的结点的左、右子结点依次入队。直到队空为止。到队空为止。#define MAX_NODE 50void LevelorderTraverse( BTNode *T) BTNode *QueueMAX_NODE ,*p=T ;int f

25、ront=0 , rear=0 ;if (p!=NULL) Queue+rear=p; /* 根结点入队根结点入队 */while (frontdata ); if (p-Lchild!=NULL) Queue+rear=p; /* 左结点入队左结点入队 */ if (p-Rchild!=NULL) Queue+rear=p; /* 左结点入队左结点入队 */ “遍历遍历”是二叉树最重要的基本操作，是各种是二叉树最重要的基本操作，是各种其它操作的基础，二叉树的许多其它操作都可以通其它操作的基础，二叉树的许多其它操作都可以通过遍历来实现。如建立二叉树的存储结构、求二叉过遍历来实现。如建立二叉树的

26、存储结构、求二叉树的结点数、求二叉树的深度等。树的结点数、求二叉树的深度等。6.3.5 二叉树遍历算法的应用二叉树遍历算法的应用按先序遍历方式建立按先序遍历方式建立 对一棵二叉树进行对一棵二叉树进行“扩充扩充”，就可以得到有该二叉，就可以得到有该二叉树所扩充的二叉树。有两棵二叉树树所扩充的二叉树。有两棵二叉树T1及其扩充的二叉树及其扩充的二叉树T2如图如图6-10所示。所示。图图6-10 二叉树二叉树T1及其扩充及其扩充二叉树二叉树T2ABCDEFG(a) 二叉树二叉树T1(b) T1的扩充的扩充二叉树二叉树T2ABCDEFG? 二叉树的扩充方法是：在二叉树中结点的每一个空二叉树的扩充方法是：

27、在二叉树中结点的每一个空链域处增加一个扩充的结点链域处增加一个扩充的结点(总是叶子结点，用方框总是叶子结点，用方框“”表示表示)。对于二叉树的结点值：。对于二叉树的结点值：u 是是char类型：扩充结点值为类型：扩充结点值为“？”；u 是是int类型：扩充结点值为类型：扩充结点值为0或或-1； 下面的算法是二叉树的前序创建的递归算法，读入下面的算法是二叉树的前序创建的递归算法，读入一棵二叉树对应的扩充二叉树的前序遍历的结点值序列。一棵二叉树对应的扩充二叉树的前序遍历的结点值序列。每读入一个结点值就进行分析：每读入一个结点值就进行分析：u 若是扩充结点值：令根指针为若是扩充结点值：令根指针为NU

28、LL；u 若是若是(正常正常)结点值：动态地为根指针分配一个结点，将该结点值：动态地为根指针分配一个结点，将该值赋给根结点，然后递归地创建根的左子树和右子树。值赋给根结点，然后递归地创建根的左子树和右子树。算法实现：算法实现：#define NULLKY ?#define MAX_NODE 50typedef struct BTNode char data ;struct BTNode *Lchild , *Rchild ;BTNode ;BTNode *Preorder_Create_BTree(BTNode *T) /* 建立链式二叉树，返回指向根结点的指针变量建立链式二叉树，返回指向根结

29、点的指针变量 */ char ch ; ch=getchar() ; getchar(); if (ch=NULLKY) T=NULL; return(T) ; else T=(BTNode *)malloc(sizeof(BTNode) ;Tdata=ch ;Preorder_Create_BTree(T-Lchild) ;Preorder_Create_BTree(T-Rchild) ;return(T) ; 当希望创建图当希望创建图6-10(a)所示的二叉树时，输入的字所示的二叉树时，输入的字符序列应当是：符序列应当是：ABD?E?G?CF? 遍历二叉树是按一定的规则将树中的结点排列成一

30、个线性序列，即是对非线性结构的线性化操作。如何找到遍历过程中动态得到的每个结点的直接前驱和直接后继(第一个和最后一个除外)? 如何保存这些信息? 设一棵二叉树有n个结点，则有n-1条边(指针连线) ， 而n个结点共有2n个指针域(Lchild和Rchild) ，显然有n+1个空闲指针域未用。则可以利用这些空闲的指针域来存放结点的直接前驱和直接后继信息。6.3.6 6.3.6 线索树线索树 （1）若结点有左孩子，则）若结点有左孩子，则Lchild指向其左孩子，指向其左孩子，否则，指向其直接前驱；否则，指向其直接前驱； （2） 若结点有右孩子若结点有右孩子，则则Rchild指向其右孩指向其右孩子子

31、，否则，指向其直接后继；，否则，指向其直接后继； 为避免混淆为避免混淆, ,对结点结构加以改进，增加两个标对结点结构加以改进，增加两个标志域。志域。 对结点的指针域做如下规定：对结点的指针域做如下规定： 用这种结点结构构成的二叉树的存储结构，用这种结点结构构成的二叉树的存储结构，叫做叫做线索链表线索链表；指向结点前驱和后继的指针叫做；指向结点前驱和后继的指针叫做线索线索；按照某种次序遍历，加上线索的二叉树称；按照某种次序遍历，加上线索的二叉树称之为之为线索二叉树线索二叉树。Lchild Ltag data Rchild Rtag图图6-10 线索二叉树的结点结构线索二叉树的结点结构0：Lchi

32、ld域指示结点的左孩子域指示结点的左孩子1 1：Lchild域指示结点的前驱域指示结点的前驱Ltag=0 0：Rchild域指示结点的右孩子域指示结点的右孩子1 1：Rchild域指示结点的后继域指示结点的后继Rtag=AFHIEGBDC(a) 二叉树二叉树 (b) 先序线索树的逻辑形式先序线索树的逻辑形式 结点序列：结点序列：ABDCEGFHIAFHIEGBDCNIL(d) 后序线索树的逻辑形式后序线索树的逻辑形式 结点序列：结点序列：DBGEHIFCA(c) 中序线索树的逻辑形式中序线索树的逻辑形式 结点序列：结点序列：DBAGECHFIAFHIEGBDCNILNILAFHIEGBDCNI

33、L 0 A 0 0 B 1 0 C 0 1 D 1 0 E 1 0 F 0 1 G 1 1 H 1 1 F 1 (e) 中序线索树的链表结构中序线索树的链表结构说明说明：画线索二叉树时，画线索二叉树时，实线实线表示指针，指向其左表示指针，指向其左、右孩子；右孩子；虚线虚线表示线索，指向其直接前驱或直接后继。表示线索，指向其直接前驱或直接后继。 在线索树上进行遍历，只要先找到序列中的第一个在线索树上进行遍历，只要先找到序列中的第一个结点，然后就可以依次找结点的直接后继结点直到后继结点，然后就可以依次找结点的直接后继结点直到后继为空为止。为空为止。6.3.3 6.3.3 线索化二叉树线索化二叉树

34、二叉树的线索化二叉树的线索化指的是依照某种遍历次序使二叉指的是依照某种遍历次序使二叉树成为线索二叉树的过程。树成为线索二叉树的过程。 线索化的过程就是线索化的过程就是在遍历过程中修改空指针使其指在遍历过程中修改空指针使其指向直接前驱或直接后继向直接前驱或直接后继的过程。的过程。 仿照线性表的存储结构，在二叉树的线索链表上也仿照线性表的存储结构，在二叉树的线索链表上也添加一个头结点添加一个头结点head，头结点的指针域的安排是：，头结点的指针域的安排是： Lchild域：指向二叉树的根结点；域：指向二叉树的根结点； Rchild域：指向中序遍历时的最后一个结点；域：指向中序遍历时的最后一个结点；

35、 二叉树中序序列中的二叉树中序序列中的第一个结点第一个结点Lchild指针域和指针域和最后一个结点最后一个结点Rchild指针域指针域均指向头结点均指向头结点head。(a) 二叉树二叉树(b) 中序线索树的逻辑形式中序线索树的逻辑形式AFHIEGBDCNILNILAFHIEGBDC图图6-12 中序线索二叉树及其存储结构中序线索二叉树及其存储结构(c) 中序线索二叉链表 0 A 0 0 B 1 0 C 0 1 D 1 0 E 1 0 F 0 1 G 1 1 H 1 1 F 1Thrt 0 | 1head结点类型定义结点类型定义typedef enmuLink , Thread Pointer

36、Tag ;/* Link=0表示指针，表示指针， Thread=1表示线索表示线索 */typedef struct BiThrNode ElemType data;struct BiTreeNode *Lchild , *Rchild ; PointerTag Ltag , Rtag ;BiThrNode, BiThrTree;线索二叉树中序遍历（线索二叉树中序遍历（P134），中序线索化（），中序线索化（P134）线索二叉树结构定义6.4 6.4 树与森林树与森林 本节将讨论树的存储结构、树及本节将讨论树的存储结构、树及森林与二叉树之间的相互转换、树的森林与二叉树之间的相互转换、树的遍历等

37、。遍历等。6.4.1 树的存储结构树的存储结构(一一) 双亲表示法双亲表示法(顺序存储结构顺序存储结构) 用一组连续的存储空间来存储树的结点用一组连续的存储空间来存储树的结点，同时在同时在每个结点中附加一个每个结点中附加一个指示器指示器(整数域整数域) ，用以指示双亲结用以指示双亲结点的位置点的位置(下标值下标值) 。数组元素及数组的类型定义如下。数组元素及数组的类型定义如下： #define MAX_SIZE 100 typedef struct PTNode ElemType data ; int parent ; PTNode ;typedef struct PTNode NodesMA

38、X_SIZE ;int root; /* 根结点位置根结点位置 */int num ; /* 结点数结点数 */ Ptree ; 图图6-13所示是一棵树及其双亲所示是一棵树及其双亲表示的存储结构表示的存储结构。这种存储结构利这种存储结构利用了任一结点的父结点唯一的性质用了任一结点的父结点唯一的性质。可以方便地直接找到可以方便地直接找到任一结点的父任一结点的父结点结点，但求结点的子结点时需要扫但求结点的子结点时需要扫描整个数组描整个数组。FGHIRABCDE图图6-13 树的双亲存储结构树的双亲存储结构R -10A 01B 02C 03D 14E 15F 36G 67H 68I 69 (二二)

39、 孩子链表表示法孩子链表表示法 树中每个结点有多个指针域，每个指针指向其树中每个结点有多个指针域，每个指针指向其一棵子树的根结点一棵子树的根结点。有。有两种结点结构两种结点结构。 定长结点结构定长结点结构 指针域的数目就是树的度指针域的数目就是树的度。 其特点是其特点是：链表结构简单，但指针域的浪费明显：链表结构简单，但指针域的浪费明显。结点。结点结构如图结构如图(a) 所示所示。在一棵有在一棵有n个结点，度为个结点，度为k的树中必有的树中必有n(k-1)+1空指针域空指针域。 不定长结点结构不定长结点结构 树中每个结点的指针域数量不同，是该结点的度，如图树中每个结点的指针域数量不同，是该结点

40、的度，如图(b) 所示。没有多余的指针域，但操作不便。所示。没有多余的指针域，但操作不便。图图 孩子表示法的结点结构孩子表示法的结点结构data child1 child2 childn(a) 定长结点结构定长结点结构(b) 不不定长结点结构定长结点结构data k child1 child2 childk复合链表结构复合链表结构 对于树中的每个结点，其孩子结点用带头结点的对于树中的每个结点，其孩子结点用带头结点的单链表表示，表结点和头结点的结构如图所示单链表表示，表结点和头结点的结构如图所示。 n个结点的树有个结点的树有n个个(孩子孩子)单链表单链表(叶子结点的孩子链叶子结点的孩子链表为空表

41、为空)，而，而n个头结点又组成一个线性表且以顺序存储个头结点又组成一个线性表且以顺序存储结构表示结构表示。data firstchild(a) 头结点头结点childno next(b) 表结点表结点图图 孩子链表结点结构孩子链表结点结构nodes789 35 012 6 0123456789MAX_NODE-1rootnumA B C D E F G H I R 49图图6-14 图图6-13的树的树T的孩子链表存储结构的孩子链表存储结构 （三）（三）孩子兄弟表示法孩子兄弟表示法(二叉树表示法二叉树表示法) 两个指针域：分别指向结点的第一个子结点和下两个指针域：分别指向结点的第一个子结点和下

42、一个兄弟结点。结点类型定义如下：一个兄弟结点。结点类型定义如下：typedef struct CSnode ElemType data ;struct CSnode *firstchild, *nextsibing ;CSNode; 图图6-15 树及孩子兄弟存储结构树及孩子兄弟存储结构(b) 树树 FGRABCDE(c) 孩子兄弟存储结构孩子兄弟存储结构 R A D C G B F E 孩子结点孩子结点兄弟结点兄弟结点firstchild data nextsibing(a) 结点结构结点结构6.4.2 森林与二叉树的转换森林与二叉树的转换 由于二叉树和树都可用二叉链表作为存储结构，由于二叉

43、树和树都可用二叉链表作为存储结构，对比各自的结点结构可以看出，以二叉链表作为媒介对比各自的结点结构可以看出，以二叉链表作为媒介可以导出树和二叉树之间的一个对应关系。可以导出树和二叉树之间的一个对应关系。 从物理结构来看，树和二叉树的二叉链表是相从物理结构来看，树和二叉树的二叉链表是相同的，只是对指针的逻辑解释不同而已。同的，只是对指针的逻辑解释不同而已。 从树的二叉链表表示的定义可知，任何一棵和从树的二叉链表表示的定义可知，任何一棵和树对应的二叉树，其右子树一定为空。树对应的二叉树，其右子树一定为空。 图图6-16直观地展示了树和二叉树之间的对应关系。直观地展示了树和二叉树之间的对应关系。图图

44、6-16 树与二叉树的对应关系树与二叉树的对应关系二叉树二叉树 CERADB R A D C B E 树树 RABCDE对应关系对应关系 R A D C B E C B E R A D 存储存储解释解释存储存储解释解释 （一）（一）树转换成二叉树树转换成二叉树 对于一般的树，可以方便地转换成一棵唯一的二叉树与对于一般的树，可以方便地转换成一棵唯一的二叉树与之对应。将树转换成二叉树在之对应。将树转换成二叉树在“孩子兄弟表示法孩子兄弟表示法”中已给出，中已给出，其详细步骤是：其详细步骤是： 加虚线加虚线。在树的每层按从。在树的每层按从“左至右左至右”的顺序在兄弟结的顺序在兄弟结点之间加虚线相连。点

45、之间加虚线相连。 去连线去连线。除最左的第一个子结点外，父结点与所有其。除最左的第一个子结点外，父结点与所有其它子结点的连线都去掉。它子结点的连线都去掉。 旋转旋转。将树顺时针旋转。将树顺时针旋转450，原有的实线左斜。，原有的实线左斜。 整型整型。将旋转后树中的所有虚线改为实线，并向右斜。将旋转后树中的所有虚线改为实线，并向右斜。 这样转换后的二叉树的特点是这样转换后的二叉树的特点是： 二叉树的二叉树的根结点没有右子树根结点没有右子树，只有左子树；，只有左子树； 左子结点仍然是原来树中相应结点的左子结左子结点仍然是原来树中相应结点的左子结点，而所有沿右链往下的右子结点均是原来树中点，而所有沿

46、右链往下的右子结点均是原来树中该结点的兄弟结点。该结点的兄弟结点。图图6-17 树向二叉树的转换过程树向二叉树的转换过程(a) 一般的树一般的树 FGRABCDEFGRABCDE(b) 加虚线加虚线，去连线后去连线后 (C) 转换后的二叉树转换后的二叉树FGRACDBE （二）（二）二叉树转换成树二叉树转换成树 对于一棵转换后的二叉树，如何还原成原来的树对于一棵转换后的二叉树，如何还原成原来的树? 加虚线加虚线。若某结点。若某结点i是其父结点的左子树的根结点，是其父结点的左子树的根结点，则将该结点则将该结点i的右子结点以及沿右子链不断地搜索所有的右的右子结点以及沿右子链不断地搜索所有的右子结点

47、，将所有这些右子结点与子结点，将所有这些右子结点与i结点的父结点之间加虚线结点的父结点之间加虚线相连，相连，如图如图6-20(a)所示所示。 去连线去连线。去掉二叉树中所有父结点与其右子结点之。去掉二叉树中所有父结点与其右子结点之间的连线，间的连线，如图如图6-20(b)所示所示。 规整化规整化。将图中各结点按层次排列且将所有的虚线。将图中各结点按层次排列且将所有的虚线变成实线，变成实线，如图如图6-20(c)所示。所示。图图6-20 二叉树向树的转换过程二叉树向树的转换过程(C) 还原后的树还原后的树FGRABCDE(b) 去连线后去连线后 (a) 加虚线后加虚线后 FGRACDBECFGR

48、ADBE二叉树向树的转换过程二叉树向树的转换过程（三）（三）森林转换成二叉树森林转换成二叉树 当一般的树转换成二叉树后，二叉树的右子树必当一般的树转换成二叉树后，二叉树的右子树必为空为空。若把森林中的第二棵树。若把森林中的第二棵树( (转换成二叉树后转换成二叉树后) )的根的根结点作为第一棵树结点作为第一棵树(二叉树二叉树)的根结点的兄弟结点，则可的根结点的兄弟结点，则可导出森林转换成二叉树的转换算法如下：导出森林转换成二叉树的转换算法如下： 设设F=T1, T2, ,Tn是森林，则按以下规则可转换是森林，则按以下规则可转换成一棵二叉树成一棵二叉树B=(root，LB，RB) 若若n=0，则，

49、则B是空树是空树。 若若n0，则二叉树，则二叉树B的根是森林的根是森林T1的根的根root(T1)，B的左子树的左子树LB是是B(T11,T12, ,T1m) ，其中，其中T11,T12, ,T1m是是T1的子树的子树(转换后转换后)，而其右子树，而其右子树RB是从森是从森林林F=T2, T3, ,Tn转换而成的二叉树转换而成的二叉树。转换步骤：转换步骤： 将将F=T1, T2, ,Tn 中的每棵树转换成二叉树中的每棵树转换成二叉树。 按给出的森林中树的次序，从最后一棵二叉树开按给出的森林中树的次序，从最后一棵二叉树开始，每棵二叉树作为前一棵二叉树的根结点的右子始，每棵二叉树作为前一棵二叉树的

50、根结点的右子树，依次类推，则第一棵树的根结点就是转换后生树，依次类推，则第一棵树的根结点就是转换后生成的二叉树的根结点，成的二叉树的根结点，如图如图6-21所示所示。ACBDGMLHK(a) 森林森林图图6-21 森林转换成二叉树的过程森林转换成二叉树的过程(b) 森林中每棵树森林中每棵树 对应的二叉树对应的二叉树ABCDGLKHM(c) 森林对应的二叉树森林对应的二叉树ABCDGLKHM（四）（四）二叉树转换成森林二叉树转换成森林 若若B=(root，LB，RB)是一棵二叉树，则可以将其是一棵二叉树，则可以将其转换成由若干棵树构成的森林：转换成由若干棵树构成的森林：F=T1, T2, ,Tn

51、 。转换算法：转换算法： 若若B是空树，则是空树，则F为空为空。 若若B非空，则非空，则F中第一棵树中第一棵树T1的根的根root(T1)就是二就是二叉树的根叉树的根root， T1中根结点的子森林中根结点的子森林F1是由树是由树B的左的左子树子树LB转换而成的森林转换而成的森林；F中除中除T1外其余树组成的外其余树组成的的森林的森林F=T2, T3, ,Tn 是由是由B右子树右子树RB转换得到的转换得到的森林森林。 上述转换规则是递归的上述转换规则是递归的，可以写出其递归算法。以可以写出其递归算法。以下给出具体的还原步骤。下给出具体的还原步骤。 去连线。去连线。将二叉树将二叉树B的根结点与其

52、右子结点以及的根结点与其右子结点以及沿右子结点链方向的所有右子结点的连线全部去掉，沿右子结点链方向的所有右子结点的连线全部去掉，得到若干棵孤立的二叉树，每一棵就是原来森林得到若干棵孤立的二叉树，每一棵就是原来森林F中的树依次对应的二叉树，中的树依次对应的二叉树，如图如图6-22(b)所示所示。 二叉树的还原。二叉树的还原。将各棵孤立的二叉树按二叉树将各棵孤立的二叉树按二叉树还原为树的方法还原成一般的树，还原为树的方法还原成一般的树，如图如图6- 22(c)所示所示。图图6-22 二叉树还原成森林的过程二叉树还原成森林的过程ACBDMGLHK(c) 还原成森林还原成森林(a) 二叉树二叉树ABC

53、DGLKHM(b) 去连线后去连线后ABCDMGLKH6.4.3 树和森林的遍历树和森林的遍历（一）（一） 树的遍历树的遍历 由树结构的定义可知，树的遍历有二种方法。由树结构的定义可知，树的遍历有二种方法。 先序遍历先序遍历：先访问根结点，然后：先访问根结点，然后依次先序遍历依次先序遍历完完每棵子树。每棵子树。如图如图6-23的树，先序遍历的次序是：的树，先序遍历的次序是：ABCDEFGIJHK 后序遍历后序遍历：先：先依次后序遍历完依次后序遍历完每棵子树，然后每棵子树，然后访问根结点。访问根结点。如图如图6-23的树，后序遍历的次序是：的树，后序遍历的次序是：CDBFIJGHEKA说明说明：

54、 树的树的先序遍历先序遍历实质上与将树转换成二叉实质上与将树转换成二叉树后对二叉树的树后对二叉树的先序遍历先序遍历相同。相同。 树的树的后序遍历后序遍历实质上与将树转换成二叉实质上与将树转换成二叉树后对二叉树的树后对二叉树的中序遍历中序遍历相同。相同。ABDCKGJIFHE图图6-23 树树 （二）（二）森林的遍历森林的遍历 设设F=T1, T2, ,Tn是森林，对是森林，对F的遍历有二种方法。的遍历有二种方法。 先序遍历先序遍历：按：按先序遍历先序遍历树的方式树的方式依次依次遍历遍历F中的每棵树。中的每棵树。 中序遍历中序遍历：按：按后序遍历后序遍历树的方式树的方式依次依次遍历遍历F中的每棵

55、树。中的每棵树。6.5 哈夫曼树及其应用6.5.1 哈夫曼树的定义n 在二叉树中，一个结点到另一个结点之间的分支构成这两个结点之间的路径路径。n 在路径上的分支数目被称为路径长度路径长度。G HD E FB CA权和带权路径长度权和带权路径长度nkkklwWPL1权：权：树种结点赋予一个有意义的实数。结点的带权长度：结点的带权长度：该结点到根的路径长度与结点上权的乘积。树的带权路径长度：树的带权路径长度：树种所有叶子结点的带权长度之和。 带权的路径长度最小的二叉树称为哈夫曼二叉树或最优二叉树。548图5-27 叶子结点带权值的二叉树 下面我们讨论一下权值、树形与带权的路径长度之间的关系。假设有

56、6个权值分别为3，6，9，10，7，11，以这6个权值作为叶子结点的权值可以构造出下面三棵二叉树。 3 6 7 910 11(a)1110976311103679(b)(c)这三棵二叉树的带权路径长度分别为：nWPL1=10*2+11*2+3*3+6*3+7*3+9*3=117nWPL2=3*1+6*2+7*3+9*4+10*5+11*5=177nWPL3=9*1+7*2+6*3+3*4+10*5+11*5=158一般情况下，最优二叉树，权值越大离根越近。一般情况下，最优二叉树，权值越大离根越近。 构造哈夫曼树的过程：构造哈夫曼树的过程： （1）将给定的n个权值w1,w2,.,wn作为n个根结

57、点的权值构造一个具有n棵二叉树的森林T1,T2, .,Tn，其中每棵二叉树只有一个根结点； （2）在森林中选取两棵根结点权值最小的二叉树作为左右子树构造一棵新二叉树，新二叉树的根结点权值为这两棵树根的权值之和； （3）在森林中，将上面选择的这两棵根权值最小的二叉树从森林中删除，并将刚刚新构造的二叉树加入到森林中； （4）重复上面（2）和（3），直到森林中只有一棵二叉树为止。这棵二叉树就是哈夫曼树。7 5 2 4举例（举例（P114 图图6.29） ：abcd构造哈夫曼树的过程构造哈夫曼树的过程(续续)：哈夫曼树算法实现(P114115)： # define n 7 # define m 2*n

58、-1 Typedef struct float weight; int lchirld, rchirld, parent; hufmtree Hufmtree tree m HUFFMAN (tree) Int i, j, p1, p2; Float small1, small2, f; For (i=0; im; i+) treei.parent = 0; treei.lchirld = 0; treei.rchirld = 0; treei.weight = 0 For(i=0; im; i+) scanf ( “%f”, &f ) ; treei.weight = f ; Cod

59、e(2) For(i=n; im; i+) p1=0; p2=0; Small1=small2=maxval; For(j=0; ji-1; j+) If (treej.parent=0) If (treej.weight small1) small2 = small1; small1=treej.weight; p2=p1; p1=j; else if ( treej.weight small2) small2 = treej.weight ; p2=j ; Treep1.parent = i+1; Treep2.parent = i+1; Treei.lchirld = p1+1; Tre

60、ei.rchirld = p2+1; Treei.weight = treep1.weight + treep2.weight ; 6.5.2 哈夫曼树与编码 在电文传输中，需要将电文中出现的每个字符进行二进制编码。在设计编码时需要遵守两个原则： （1）发送方传输的二进制编码，到接收方解码后必须具有唯一性，即解码结果与发送方发送的电文完全一样； （2）发送的二进制编码尽可能地短。下面我们介绍两种编码的方式。 1. 等长编码 这种编码方式的特点是每个字符的编码长度相同（编码长度就是每个编码所含的二进制位数）。假设字符集只含有4个字符A，B，C，D，用二进制两位表示的编码分别为00，01，10，11。若现在有一段