1、1数据结构数据结构(中中)2第第6章章 树与二叉树树与二叉树第第7章章 图图3第六章第六章 树与二叉树树与二叉树4学习重点：树的定义及其基本术语 二叉树的定义及性质 二叉树的存储方法 二叉树的遍历 树的存储方法 树的遍历 二叉树与树、森林的转换 二叉树的应用 56.1 树的概念及术语树的概念及术语6.2二叉树二叉树6.3二叉树的遍历二叉树的遍历6.4 二叉树与树、森林的转换二叉树与树、森林的转换6.5 树的存储结构树的存储结构6.6 树的遍历树的遍历6.7 二叉树的应用二叉树的应用6 所谓所谓“树（树（TreeTree）”是指由是指由n n（n0n0）个结点构成的有限数据元素的集合个结点构成的
2、有限数据元素的集合T T。当。当n=0n=0时，称其为时，称其为“空树空树”。当。当n0n0时，树中诸结时，树中诸结点应该满足下面的两个条件：点应该满足下面的两个条件：6.1.16.1.1 树的定义树的定义7（1）有且仅有一个特定的结点，它没有前 驱，是该树的根，称为树的根结点；（2）除根结点外的其余结点，可分为m （m0）个互不相交的有限集合：T1，T2，Tm，每一个集合Ti（0im）又是一棵树，被称为是根的子树。8有关树的术语（有关树的术语（1）结点结点：它不仅有数据本身，还有指向其孩子的若干分支 孩子结点孩子结点：某结点的各子树的根，称为这个结点的孩子结点孩子结点 双亲结点双亲结点 兄弟
3、结点兄弟结点：有相同双亲的孩子称为兄弟结点 祖先结点祖先结点：从根结点到该结点的双亲结点，都是此结点的祖先结点 9有关树的术语（有关树的术语（2）结点的度：结点的度：指该结点的子树的个数 叶子结点：叶子结点：度为0的结点，也称为终端结点 分支结点分支结点：度不为0的结点，也称为非终端结点 树的层数树的层数：树的根所在结点的层数为1，其他结点的层数等于它的双亲结点的层数加1 10有关树的术语（有关树的术语（3）树的深度：树的深度：树中结点的最大层数称为树的深度（也称高度）森林：森林：零棵或有限棵互不相交的树的集合称为森林 有序树和无序树：有序树和无序树：如果树中结点的各子树从左到右是有次序的（即
4、位置不能互换），那么这样的树称为有序树；否则是无序树。116.1.2 6.1.2 树的基本操作树的基本操作1初始化一棵空树；2销毁一棵已存在的树；3求树的根结点；4求结点的的双亲结点；5求树的深度；6前序遍历树；7中序遍历树；8后序遍历树；9层序遍历树。126.1.3 6.1.3 树的表示方式树的表示方式（A（B（E，F），C（G），D（H，I（K），J）（c）树形表示法 (d)广义表表法法图6.4 二叉树的表示136.26.2二叉树二叉树 二叉树二叉树，它是一种非常重要的非线性数据结构，它是一种非常重要的非线性数据结构，有着广泛的用途。有着广泛的用途。主要介绍以下几个方面的内容：主要介绍以下
5、几个方面的内容：二叉树的定义及性质；二叉树的定义及性质；二叉树的存储实现（顺序和链式存储）；二叉树的存储实现（顺序和链式存储）；遍历二叉树（即对二叉树存储结点访问的各种遍历二叉树（即对二叉树存储结点访问的各种形式）；形式）；哈夫曼树及编码。哈夫曼树及编码。146.2.1 6.2.1 二叉树的定义二叉树的定义 所谓所谓“二叉树二叉树”，是一个由结点组成的，是一个由结点组成的有限集合。这个集合或为空，或由一个有限集合。这个集合或为空，或由一个称为根的结点以及两棵不相交的二叉树称为根的结点以及两棵不相交的二叉树组成，这两棵二叉树分别称为根结点的组成，这两棵二叉树分别称为根结点的左子树左子树和和右子树
6、。右子树。15 二叉树有如下的特征：二叉树有如下的特征：二叉树可以是空的，空二叉树没有任何结点；二叉树可以是空的，空二叉树没有任何结点；二叉树上的每个结点最多可以有两棵子树，二叉树上的每个结点最多可以有两棵子树，这两棵子树是不相交的；这两棵子树是不相交的；二叉树上一个结点的两棵子树有左、右之二叉树上一个结点的两棵子树有左、右之分，次序是不能颠倒的。分，次序是不能颠倒的。16图6.6 二叉树的五种基本形态(a)(b)(c)(d)(e)176.2.2 6.2.2 二叉树的重要性质二叉树的重要性质 性质性质1:在任何一棵二叉树的第在任何一棵二叉树的第i（i1）层）层上，最多有上，最多有2i-1个结点
7、个结点【证明证明】二叉树的第二叉树的第1层只有一个结点。层只有一个结点。所以，当所以，当i=1时，时，2i-1=20=1成立。成立。假设结论对第假设结论对第i层成立，即第层成立，即第i层最多层最多有有2i-1个结点。由于二叉树每个结点的度个结点。由于二叉树每个结点的度最多为最多为2，因此第，因此第i+1层结点的个数，最层结点的个数，最多应该是第多应该是第i层结点个数的层结点个数的2倍，即倍，即2 2i-1=2i，命题得证。命题得证。18 性质性质2:树高为树高为k（k1）的二叉树，最多）的二叉树，最多有有2k1个结点。个结点。【证明证明】由性质由性质6-1可知，在树高为可知，在树高为k的的二叉
8、树里，第二叉树里，第1层有层有20个结点，第个结点，第2层有层有21个结点，第个结点，第3层有层有22个结点，个结点，第，第k层有层有2k-1个结点。因此，要求出树高为个结点。因此，要求出树高为k的二叉树的结点个数，就是求和：的二叉树的结点个数，就是求和：2 20 0+2+21 1+2+22 2+2+2k-1k-1=2 2k k-1.-1.证毕证毕19 性质性质3:如果一棵二叉树中，度为如果一棵二叉树中，度为0的结点的结点个数为个数为n0，度为，度为2的结点个数为的结点个数为n2，则有，则有关系：关系：n0=n2+1。【证明证明】设二叉树中度为设二叉树中度为1的结点个数的结点个数为为n1，那么
9、二叉树总的结点个数，那么二叉树总的结点个数n应该是：应该是：n=n0+n1+n2（1）20 另一方面，二叉树中除根结点外，另一方面，二叉树中除根结点外，其余每个结点都有一个向上的分支指向其余每个结点都有一个向上的分支指向其父结点。如设二叉树种分支边数为其父结点。如设二叉树种分支边数为m，那么二叉树总的结点个数那么二叉树总的结点个数n应该是分支边应该是分支边数数m加上加上1（这个（这个1是根结点），即：是根结点），即：n=m+1 （2）21 注意到每一条分支边或是由度为注意到每一条分支边或是由度为1的结点发的结点发出，或是由度为出，或是由度为2的结点发出，度为的结点发出，度为1的结点发的结点发出
10、一条边，度为出一条边，度为2的结点发出两条边。因此，的结点发出两条边。因此，又有关系：又有关系：m=n1+2n2 （3）把式（把式（3）代入式（）代入式（2），得：），得：n=n1+2n2+1 （4）综合式（综合式（1）和式（）和式（4），立即可以得出所需要），立即可以得出所需要的结论。的结论。22两种特殊形态的二叉树两种特殊形态的二叉树 满二叉树：满二叉树：深度为深度为k并且含有并且含有2k-1个结点的二个结点的二叉树称，如图叉树称，如图6.7所示。对满二叉树的结点可以所示。对满二叉树的结点可以从根结点开始自上向下，自左至右顺序编号，从根结点开始自上向下，自左至右顺序编号，图图6.7中每个结
11、点上的数字即是该结点的编号。中每个结点上的数字即是该结点的编号。完全二叉树：完全二叉树：深度为深度为k，含有，含有n个结点的二叉树，个结点的二叉树，当且仅当每个结点的编号与相应满二叉树结点当且仅当每个结点的编号与相应满二叉树结点顺序编号从顺序编号从1到到n相对应时，则称此二叉树为完相对应时，则称此二叉树为完全二叉树，如图全二叉树，如图6.8所示。所示。23图6.7 满二叉树 图6.8 完全二叉树 24 性质性质4:具有n个结点的完全二叉树树深为 +1（其中 表示不大于x的最大整数）。【证明证明】假设某完全二叉树的结点总数是n，它的值应该大于树深为K-1的满二叉树结点数2k-1-1，小于等于树深
12、为K的满二叉树结点数2k-1。2k-1-1 n 2k-11log2n x25由于该不等式各项均为整数，当对两端两项各加1时不等式发生变化得：2k-1 n 2k 再对其取对数得：k-1 log2n 1时，该结点的双亲结点编号为 ；若2in，它有编号为2i的左孩子，否则没有左孩子；若2i+1n，则它有编号为2i+1的右孩子，否则没有右孩子。286.2.3 6.2.3 二叉树的存储结构二叉树的存储结构 1.顺序存储结构顺序存储结构 将二叉树的所有元素放在一维数组之中。这是最简单的顺序存储结构。#define MAXLEN 20 typedef char DataType;DataType btMAX
13、LEN;其中，bt是一维数组，每个数组元素存储树的一个结点的数据信息。我们假定让0号位置（即bt0）空置不用，从1位置开始存储二叉树的所有元素。我们按照完全二叉树上编号自上而下、从左至右的顺序将每个元素存入数组当中。29 如左图中的完全二叉树存入到数组中，可以很容易地看到第i个结点及其双亲和左、右孩子结点2i、2i+1的存储位置。30 若二叉树为一棵单边树如图6.9所示，要如何存储？虽然此二叉树只有四个结点，但对于任何一棵二叉树来说，都有插入新的结点的可能。依然要保留其存储空间。即可见，对于四个结点的单边树，要开辟8个存储空间来存储。若有一棵深度为K的二叉单边树，那么至少有2k个存储空间，则有
14、2kK个空间为空，这样有许多空间浪费了。这种存储结构适合用于存储完全二叉树、满二叉树。一般的二叉树较少采用这种存储结构。312链表存储结构链表存储结构 二叉树的链表结构，常见的有二种：二叉链表和三叉链表。由二叉树的定义可知，二叉树的结点由一个数据元素和分别指向其左、右子树的指针组成，如图6.10（a）所示。32根据结点的定义，二叉链表的每个结点有一个数据域和两个指针域，一个指向其左孩子，一个指向其右孩子，见图6.10（b）。其结点结构描述如下：struct node Datatype data;/*数据域*/node*lchild;/*指向其左孩子的指针域*/node*rchild;/*指向期
15、右孩子的指针域*/33 可使用三叉链表。它是比二叉链表多了一个指向其双亲的指针域，如图6.10（c）所示。其结点描述如下：struct node3 Datatype data;/*数据域*/node3*lchild;/*指向其左孩子的指针域*/node3*rchild;/*指向其右孩子的指针域*/node3*parent;/*指向其双亲的指针域*/34356.3 6.3 二叉树的遍历二叉树的遍历 所谓遍历是指按一定的次序将每个元素都访问一遍，且只能访问一次。访问访问是指对结点进行各种操作的简称，包括输出、查找、修改等等操作。在线性结构中我们没有提出遍历的概念及说法，因为线性结构相较而言比较简单
16、，元素之间只存在有前后的次序问题，访问操作我们只限定在在了输出操作上，即按从前到后的顺序逐个输出.36 遍历二叉树遍历二叉树是指以一定的次序访问二叉树中的每个结点，并且每个结点仅被访问一次。假设遍历二叉树时访问结点的操作就是输出结点数据域的值，那么遍历的结果得到一个线性序列。37 遍历二叉树的过程实质是把二叉树的结点进行线性排列的过程。对于二叉树结构来讲，元素之间的关系不再是简单的先后关系，每个结点都可以有两棵子树（后继）。如何遍历呢？38 二叉树的是由三个单元组成：根结点（T）、左子树（L）、右子树（R）。若能依次遍历这三个部分，就是遍历了整个二叉树。按我们从左至右的习惯，我们可以有三种遍历
17、方案，即根左子树右子树（TLR）；左子树根右子树（LTR）；左子树右子树根（LRT）。分别称之为先序遍历，中序遍历，后序遍历 39例如有一棵二叉树它有4个结点。为了便于理解遍历的思想，暂且为每个没有子树的结点均补充上相应的空子树，用来表示，见图6.12。设想有一条搜索路线（用虚线表示），它从根结点的左侧开始，自上而下自左至右搜索，最后由根结点的右侧向上出去。不难看出，若考虑到空子树的话，恰好搜索线途经每个有效的树结点都是三次。40 把搜索线第一次经过就访问的结点列出，它们是A、B、C、D，这就是先序遍历的结果。那么搜索线第二次经过才访问的则是中序遍历，其结果是B、A、D、C。搜索线第三次经过才
18、访问的就是后序遍历，结果是B、D、C、A。416.3.1 6.3.1 先序遍历先序遍历 先序遍历二叉树递归定义为：若二叉树根空，则返回；否则：（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。42先序遍历递归算法如下：void fstorder(Bnode*p)if(p!=NULL)printf(%6c,p-data);/*访问根结点*/fstorder(p-lch);/*对左子树按先序遍历进行*/fstorder(p-rch);/*对右子树按先序遍历进行*/43 先序遍历递归调用的执行过程如下:446.3.26.3.2中序遍历中序遍历中序遍历二叉树递归定义为：若二叉树根空，则返回
19、；否则：（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。45中序遍历递归算法如下：void middleorder(Bnode*p)if(p!=NULL)middleorder(p-lch);/*对左子树按中序遍历进行*/printf(%6c,p-data);/*访问根结点*/middleorder(p-rch);/*对右子树按中序遍历进行*/466.3.3 6.3.3 后根遍历后根遍历后根遍历可以递归的定义为：如果根不空:(1)按后根次序遍历左子树；(2)按后根次序遍历右子树；(3)访问根结点；否则返回。47后根遍历递归算法如下：void lastorder(Bnode*p)i
20、f(p!=NULL)lastorder(p-lch);/*对左子树按后先序遍历进行*/lastorder(p-rch);/*对右子树按后先序遍历进行*/printf(%6c,p-data);/*访问根结点*/486.3.4 6.3.4 按层遍历按层遍历按层遍历引入了队列作为辅助工具。算法思想为：（1）将二叉树根入队列；（2）将队头元素出队列，并判断此元素是否有左右孩子，若有，则将它的左右孩子入列，否则转（3）；（3）重复步骤（2），直到队列为空 49viod levelorder(Bnode*p)Bnode*q20;front=rear=0;/*/队头与队尾指针*/if(p!=NULL)rea
21、r+;qrear=p;/*根结点不空，进队*/while(front!=rear)front+;p=qfront;printf(“%6c”,p-data);/*出队并访问该队头元素*/if(p-lch!=NULL)rear+;qrear=p-lch;/*若左孩子不空，进队*/if(p-rch!=NULL)rear+;qrear=p-rch;/*若右孩子不空，进队*/506.3.5 6.3.5 非递归遍历算法非递归遍历算法 递归算法简明精练，但效率较低。因为系统需要维护一个工作栈以保证递归函数的正确执行。在实际应用中往往会用到非递归方法。在某些高级语言中，没有提供递归调用的语句及功能。为了提高程
22、序设计的能力，有必要进行由递归方法到非递归方法的基本训练。非递归算法的关键问题在于如何实现由系统完成的递归工作栈。此时，可人为地设置栈来仿照系统工作栈的工作过程。511前序遍历的非递归算法前序遍历的非递归算法 对递归方法执行的分析可看出，每进行一次深层次调用都需保留当前调用层上的一些信息，主要是指向根结点的指针。在先序遍历的非递归算法中。设置一个栈S来存放所经过的根结点的指针。为了在访问完某个结点及其左子树后，方便地找到此结点的右子树.所以，在访问完某个结点后，将该结点的指针保存在栈中.52先序非递归的过程如下:（1）设置一个空栈。（2）若二叉树不空，访问根结点，并将其指针入栈，然后遍历它的左
23、子树。（3）左子树遍历结束后，若栈不空，将栈顶元素出栈，遍历栈顶元素的右子树。直至栈空为止。53先序遍历非递归算法如下：void fstorder(Bnode*p)top=-1;/*空栈*/while(p!=NULL|top!=-1)while(p!=NULL)printf(“%6c”,p-data);top+;stop=p;p=p-lch;if(top=-1)p=stop;top-;p=p-rch;542中序遍历的非递归算法中序遍历的非递归算法 中序遍历与前序遍历不同之处在于第一次遇到根结点时，并不访问，而是去遍历其左子树，当左子树遍历结束后，才访问根结点，那么，中序的非递归算法当中，可将根
24、指针先入栈，当其左子树遍历完毕后，再从栈中弹出并访问它。55中序非递归遍历算法如下：void middleorder(Bnode*p)top=-1;/*空栈*/while(p!=NULL|top!=-1)while(p!=NULL)top+;stop=p;p=p-lch;if(top=-1)p=stop;printf(“%6c”,p-data);top-;p=p-rch;56&A&A&B&A&C&C&D&C遇根A其地址进栈遍历A的左子树遇根B其地址进栈遍历B的左子树B的左子树为空；出栈访问BB的右子树为空出栈访问A遍历A的右子树遇根C其地址进栈遍历C的左子树遇根D其地址进栈遍历D的左子树D的左
25、子树为空；出栈访问DD的右子树为空出栈访问C；C的右子树空；栈空结束。图6.14 二叉树的中序非递归栈573.后序遍历非递归算法后序遍历非递归算法 后序遍历当中，二叉树的根结点需要其左右子树都遍历结束后才访问，其非递归算法较复杂些。除之前所需的栈，另需一个辅助栈s2用来记录经过某根结点的次数。两个栈的类型：Bnode *s10；int s220；58void lastorder(Bnode*p)qp；top0；bool1；printf(“n 后根遍历:n”)do while(q!NULL)top+；stopq；s2top1；qq-lch;if(top=0)bool0；else 第二次及第三次经
26、过栈的操作 while bool；printf(“n”);中序非递归遍历算法如下：59/*第二次及第三次经过栈的操作*/if(s2top=1)s2top2；/*第2次经过，不出栈*/qstop；qq-rch；else qstop；/*第3次经过，出栈并且访问结点*/s2top0；top-；printf(“6c”，q-data)；qNULL；606.3.66.3.6 二叉树的建立二叉树的建立 在此，介绍两种创建二叉树的方法。1、利用二叉树的性质5。2、递归建立二叉树、递归建立二叉树61 1、利用二叉树的性质5 根据二叉树的性质5，对任意二叉树，先将其补全为满二叉树，并对每个结点进行编号，再去掉所
27、有补上结点，得到每个结点的编点。如图6.15(a)所示。62 由于此树并非完全二叉树，所以结点的编号并不连续。算法中使用一个辅助向量s用于存放树结点的指针（即地址），如si中应该存放编号为i的结点的地址指针。此例原始数据序列如图6.15(b)所示，照此一一输入即可生成二叉链表。63 其生成过程如下：当结点编号i=1时，所产生的结点为根结点，同时将指向该结点的指针存入s1。当结点编号i1时，产生一个新的结点之后，也要将指向该结点的指针存入si。由性质5可知：j=i/2 为它的双亲结点编号。如果i为偶数，则它是双亲结点的左孩子，即让sj-lch=si；如果i为奇数，则它是双亲结点的右孩子，即让sj
28、-rch=si。64结点存储结构如前所描述为结点存储结构如前所描述为Bnode，辅助向量：，辅助向量：Bnode*s20。二叉树生成算法如下：。二叉树生成算法如下：Bnode *creat()Bnode*t=NULL;printf(n i,x=);scanf(%d%d,&i,&x);while(i!=0)&(x!=0)q=(struct node*)malloc(sizeof(struct node);/*产生一个结点*/q-data=x;q-lch=NULL;q-rch=NULL;si=q;if(i=1)t=q;/*q为树根结点*/else j=i/2;/*j为双亲结点编号*/if(i%2)
29、=0)sj-lch=q;else sj-rch=q;printf(n i,x=);scanf(%d%d,&i,&x);returu t;652、递归建立二叉树、递归建立二叉树 我们按先序递归遍历的思想来建立二叉树。其建立思想如下：（1）建立二叉树的根结点；（2）先序建立二叉树的左子树；（3）先序建立二叉树的右子树。66 算法描述如下：算法描述如下：Bnode*creat()Bnode*p;scanf(%d,&x);/*输入结点的数据域*/if(x=0)p=NULL;elsep=(Bnode*)malloc(sizeof(Bnode);p-data=x;/*建立根结点*/p-lch=creat(
30、);/*建立左子树*/p-rch=creat();/*建立右子树*/return p;67问题：了解了二叉树,二叉树的遍历,那么二叉树遍历可以在哪里可以用得上呢？686.3.76.3.7 二叉树遍历的应用举例二叉树遍历的应用举例 利用二叉树遍历算法的思路，若访问结点的操作不局限于输出结点的数据域的值，而将访问扩展到结点的判别、计数等等操作。可以解决关于二叉树其他实际问题。本小节主要利用二叉树的递归遍历来实现。691统计二叉树的叶子结点的数量 叶子结点是指那些没有左子树，也没有右子树的结点。那么，先设置一个计数器m，记录叶子结点的数量，那么，可以在遍历的过程中，判断结点是否为叶子结点，是，则计数
31、量m加1，这样，直到遍历结束，就可以得到叶子结点的数量。70以先序遍历方法统计叶子结点的数量，其算法如下：void numofleaf(Bnode*p,int*m)if(p!=NULL)if(p-lch=NULL&p-rch=NULL)/*叶子结点左、右子树为空*/(*m)+;numofleaf(p-lch,m);numofleaf(p-rch,m);71这里，m作为引用型形参，每一次递归调用时，都可以实时记录叶子结点的个数。相应的主调函数示意如下：main()Bnode*t;t=creat();/*建立二叉树t*/m=0;/*全局变量m置初值*/numofleaf(t,m);/*求树t叶子结
32、点的个数m*/printf(n m=%4d,m);/*输出结果*/722求二叉树的树深 在6.1节中，我们介绍了树深。我们除了计算二叉树结点所处的最大层次数之外，树的深度也可以这样得到：设二叉树根所在结点的深度为1，比较其左子树和右子树的深度，取其深度的最大值N，那么树的深度为N加1。可以利用二叉树的先序、中序或后序遍历的思路来完成，73其算法如下：int fstdepth(Bnode*p)if(p=NULL)return 0;elseint dl=fstdepth(p-lch);/*左子树的深度*/int dr=fstdepth(p-rch);/*/右子树的深度*/return 1+(dld
33、r?dl:dr);/*树的深度*/74 相应主调函数如下：main()Bnode*t;t=creat();h=fstdepth(t);printf(”树深度为%d”,h);756.4 6.4 二叉树与树、森林的转换二叉树与树、森林的转换 我们着重介绍了二叉树，而本章的主题内容是树与二叉树，那么，树与二叉树之间有什么联系呢？766.4.1 6.4.1 树与二叉树的转换树与二叉树的转换1、树转换成二叉树，其方法为：（1）加线在树中所有相邻的兄弟之间加一条线段。（2）抹线对树中的每个结点，只保留它与第一个孩子结点之间的连线，删去它与其他孩子结点的连线。（3）调整以每一个结点为轴心，将其右侧所有结点按
34、顺时针转动45度，使之成为一棵二叉树。其转换过程如图6.14所示。77（a）原来的树 （b）加线 图6.14 树转换成二叉树78（c）抹线 （d）调整图6.14 树转换成二叉树注意：由于树的根结点没有右兄弟，所以转换后，二叉树根结点的右子树一定为空 792、二叉树转换成树，其方法为：树与二叉树的转换是可逆的，将二叉树转换为树的方法依然是三步，具体如下：（1）加线若某结点是其双亲结点的左孩子，则把该孩子的右孩子、右孩子的右孩子、，都与该结点用线连起来。（2）抹线删去二叉树中所有双亲结点与右孩子结点的连线。（3）调整把虚线改为实线，把结点按层次排列。图6.15给出了二叉树转换为一般树的过程。80（
35、a）二叉树 （b）加线 图6.15 树转换成二叉树81（c）抹线 （d）调整 图6.15 树转换成二叉树826.4.2 6.4.2 森林与二叉树的转换森林与二叉树的转换 森林是树的集合。既然树可以与二叉树互相转换，那么森林是否可以与二叉树进行转换呢？若是可以，该如何操作呢？831、森林转换为二叉树 我们知道，当一棵树转换为二叉树时，此二叉树是没有右子树的。现在，我们就来利用这个空的右子树的位置。转换方法如下：（1）转换将森林中的每棵子树转换成二叉树，我们可以给每个二叉树进行编号为第1、2、3、n棵二叉树。（2）加线在所有的二叉树的根结点之间加一条连线，即依次将第i+1棵二叉树作为第i棵二叉树的
36、右子树。图6.16是将一个森林转换成一棵二叉树的例子。84(a)一般树的森林(b)二叉树的森林85(c)第二棵子树并入第一棵子树(d)最终的二叉树862、二叉树转换为森林其具体步骤为：（1）抹线将二叉树的根结点与其右孩子的连线以及当且仅当连续地沿着右链不断地搜索到的所有右孩子的连线全部抹去，这样就得到包含有若干棵二叉树的森林。（2）还原将每棵二叉树按二叉树还原一般树的方法还原为一般树。于是得到森林。你能画出这个森林吗?87 问题：从6.4节当中，我们了解到二叉树与树、森林的转换。这是在逻辑关系上的转换，那么为什么我们一定要转换呢？它的实际意义是什么呢？886.5 6.5 树的存储结构树的存储结
37、构 对于树来说，树中结点这间的逻辑关系是一个双亲结点，可能有多个孩子，我们该如何将树存储在计算机中呢？是否仍然可以用顺序存储和链式存储呢？896.5.1 6.5.1 树的双亲表示树的双亲表示 由树的定义可知，树中每个结点都有且仅有一个双亲对点，按这个特点，在每个数组元素中存放一个结点信息和其双亲结点的下标位置。这种存储方式叫做双亲表示法。数组元素的表示如下：其中：data域，用来存储结点信息；parent域，用来存储该结点的双亲在数组中的下标位置。data parent90 图6.17表示了左图的双亲表示法 图6.17 树的双亲表示法 916.5.2 6.5.2 孩子表示法孩子表示法 树的孩子
38、表示法是一种基于链表的存储方法。可称之为多重链表表示法，即结点中的每个指针域指向一个孩子。因为树的每个结点度是不同的，我们可以让结点的指针域的数量等于树的度，其结点结构为：92图6.18给出了左图所示的树采用多重链表表示法的存储示意图 图 6.18 多重链表表示法93 从图中可以看出，空链域的数量会比较多，如果出现树的度很大，假如树的度为12且只有一个结点的度为12，其他大多数的结点度很小，只为1。那么空链域会更多，就会造成浪费空间。946.5.3 孩子兄弟表示法孩子兄弟表示法 孩子-兄弟表示法是树最常用的表示法，这种方法表示规范，不仅适用于多叉树的存储，也适用于森林的存储。树的孩子兄弟表示法
39、又称为二叉链表表示法。构成孩子兄弟二叉链表的结点结构是：一个数据域和两个指针域，一个指针指向它的长子，另一指针指向它的一个兄弟。其结点结构为：95 左图中树的孩子-兄弟二叉链表结构如图6.19(a)所示 图6.19 树的孩子兄弟表示示意图(a)96 假设把图6.19(a)中指向兄弟的水平方向指针改为下斜45，如图6.19(b)，不难发现它与一棵二叉树十分相似。由本章第6.2节可知二叉树结构规范、简单并具有一些重的要性质，因此常将一般树结构转换为二叉树结构进行处理。976.6 6.6 树的遍历树的遍历 树和森林又都与二叉树可以互相转换，转换的依据是树和森林的孩子兄弟存储表示。因此，根据二叉树遍历
40、的思想可以实现树和森林的遍历。树和森林选用孩子兄弟链表存储结构，它的结点的结构如下：typedef struct node char data;struct node*firstchild;/*指向第一个孩子*/struct node *nextsilbing;/*指向下一个兄弟 */CSnode;986.6.1 6.6.1 一般树的遍历一般树的遍历 1树的先序遍历 对一般树进行先序遍历，首先访问树的根结点，然后从左至右逐一先序遍历根的每一棵子树。99树的先序遍历递归该算法如下：void preordertre(CSnode *root)/*root 一般树的根结点*/if(root!=NUL
41、L)printf(“%6c”,root-data);/*访问根结点*/preordertre(root-firstchild);preordertre(root-nextsilbing);100 2树的后序遍历 对一般树进行后序遍历，首先从左至右逐一后序遍历树根的每一棵子树，最后访问树的根结点。由于一般树转换为二叉树后，此二叉树没有右子树，对此二叉树的中序遍历结果与上述一般树的后序遍历结果相同。101树的后序遍历递归算法：void postordertre(CSnode *root)/*root 一般树的根结点*/if(root!=NULL)postordertre(root-firstchi
42、ld);printf(“%6c”,root-data);postordertre(root-nextsilbing);1023树的按层遍历本算法运用队列做辅助存储结构。其步骤为：首先将树根入队列；出队一个结点便立即访问之，然后将它的非空的第一个孩子结点进队，同时将它的所有非空兄弟结点逐一进队；重复，这样便实现了树按层遍历。103按层遍历算法如下：void leveltraverse(CSnode*root)CSnode *q20;/*辅助队列，假设树结点不超过19个*/front=0;rear=0;/*置空队列*/p=root;printf(“n”);if(p!=NULL)rear+;qrea
43、r=p;/*根结点进队*/while(front!=rear)front+;p=qfront;/*队首结点出队，并访问*/printf(“%6c”,p-data);if(p-firstchild!=NULL)rear+;/*P第一个孩子，不空则进队*/qrear=p-firstchild;/*再找p的一个个兄弟结点，不空则进队*/while(p-firstchild!=NULL)rear+;qrear=p-nextsilbing;p=p-nextsilbing;/*当队列为空时，结束循环*/1046.6.2 6.6.2 森林的遍历森林的遍历森林有两种遍历方法：（1）前序遍历森林：前序遍历森林中
44、的每一棵树。（2）后序遍历森林：后序遍历森林中的每一棵树。105 例如右图中的森林，前序遍历的序列为：A，B，C，D，E，F，G，H，I，J；其后序遍历的序列为：B，C，D，A，F，E，H，J，I，G。1066.7 6.7 二叉树的应用二叉树的应用 树结构可以用来表示集合，应用比较广泛。它可以用于通信及数据传送中的二进制编码、判定和决策、信息的检索和排序等。1076.7.1 6.7.1 哈夫曼树哈夫曼树 路径、路径长度：从树一个结点到另一结点的分支构成两个结点之间的路径，路径上的分支的数目称为路径长度。树的路径长度：从根到树中每个结点路径长度。树的带权路径长度（WPL）：树中所有叶子结点的带权
45、路径长度之和。哈夫曼树：设有n个权值 ，构造一个具有n个叶子结点的二叉树，每个叶子结点带有权值，在所有的二叉树中，带权路径长度WPL最小的二叉树称为哈夫曼树。nwww,21108 例如：给定中子结点的权值分别2，3，4，5，可以构造出形状不同的多个二叉树，如图6.20所示。图6.20 不同带权路径长度的二叉树 1096.7.2 6.7.2 哈夫曼树的构造哈夫曼树的构造建立哈夫曼树的方法如下：1根据已知的n个权值 ，首先构造n棵二叉树，每棵二叉树只有一个根结点，根结点的权值是，得到一个由n棵二叉树的集合F 。2在集合F中选取两棵根结点权值最小的二叉树，作为一棵新二叉树的左、右子树，新二叉树根结点
46、的权值为两棵二叉树的根结点权值之和。nwww,21nTTT,211103在集合F中去掉两棵树，并将新建立的二叉树加入到集合F中去。4重复步骤2和3，直到F集合中只剩下一棵二叉树为止。这棵二叉树即所求的哈夫曼树 111已知权值已知权值 W=5,6,2,9,7，哈夫曼树的构造过，哈夫曼树的构造过程如下：程如下：（b）（a）112（c）（d）113（e）114 注意：在上述例子中，我们没有指定新生成的二叉树的左、右子树是的权值是左大右小，还是左小右大；也没有指定当出现两个权值相同时，先选哪个。所以，我们在构造一棵哈夫曼树时，其形态可能有多个，但若是指明了具体算法时，其形态就会唯一。1156.7.36
47、.7.3 哈夫曼树的实现算法哈夫曼树的实现算法 讨论顺序存储结构下哈夫曼树的实现.因为哈夫曼树中没有度为1的结点。由二叉树的性质2可知n0n21，而现在结点总数为02，也即201。如果叶子数0用n来表示，则二叉树结点总数为2n1，向量的大小就定义为2n1 116假设n10，存储结构如下：typedef struct int data；/*权值域*/int lch，rch；/*左、右孩子结点在数组中的下标*/int tag；/*tag=0 结点独立；tag=1 结点已并入树中*/huff huff h20；117 首先将所有叶子的权值输入向量h的data域中，并将lch，rch，tag域全置零。
48、如前例中的权值 5,6,2,9,7，其初始化如表6-1所示，并按哈夫曼树的构造过程，最后结果如表6-2所示。118119int hufftree(huff h20)scanf(“n n=%d”，&n)；/*n为叶子结点的个数*/for(j=1；j=n；j+)scanf(“%d”，&rj.data)；hj.tag0；hj.lch0；hj.rch0；i0；/*合并合并n-1n-1次次*/hx1.tag=1；hx2.tag=1；i+；hn+i.data=hx1.data+hx2.data；/*m1+m2*/hn+i.tag=0；hn+i.lch=x1；hn+i.rch=x2；t=2*n-1；retu
49、rn(t)；120 while(in-1)/*合并n-1次*/x1=0；m1=32767；/*m1是最小值单元，x1为下标号*/x2=0；m2=32767；/*m2为次小值单元，x2为下标号*/for(j=1；j=n+i；j+)if(hj.datam1)&(hj.tag=0)）m2=m1；x2=x1；m1=rj.data；x1=j；else if(hj.datam2)&(hj.tag=0)m2=hj.data;x2=j;1216.7.4 6.7.4 哈夫曼编码哈夫曼编码 假定有一段电文，其中使用了5个字符Q、T、L、N、P，它们在电文中出现的次数分别为5、6、2、9、7。由它们所构造的哈夫曼树
50、如6.21（e）所示。在树中让所有左分支的编码为0，右分支的编码为1，将从根结点起到某个叶子结点路径上的各左、右分支的编码顺序排列，就得到这个叶子结点所代表的字符的二进制编码，如图6.22所示。122图6.22 哈夫曼编码123本章小结本章小结 树与二叉树属于非线性结构。除根以外，每个结点只能有一个前驱，除叶子结点外，每个结点都可以多个后继（即孩子结点）。二叉树是度至多为2的有序树，有严格的左右之分，称之为左子树和右子树，二叉树的存储也有两类：顺序存储结构：适用于满二叉树和完全二叉树存储；链式存储结构。适合一般树的存储。分为二叉链表和三叉链表。124 二叉树的遍历操作分为：先序遍历、中序遍历、
