数据结构-第7章-树演示课件

.,第7章 树,7.1 树的基本概念 7.2 树的存储结构 7.3 二叉树 7.4 遍历二叉树 7.5 树和森林7.6 哈夫曼树及其应用7.7 二叉树的应用举例7.8 小结习题7,.,7.1 树的基本概念,树是n(n1)个结点的有限集合。它满足如下条件：(1) 有一个特殊的结点称为根结点(Root)；(2) 除根结点之外的其余结点可分为m(m0)个互不相交的有限集合：T1，T2，T3，Tm，其中每一个集合本身又是一棵树，并且称为根的子树(Subtree)。这是一个递归定义，因为在树的定义中用到了树本身。树的递归定义给出了树中的每一个结点都是该树中某一棵子树的根。,.,下面我们将引入与树有关的常用术语。如图7-1所示是具有12个结点的树，其中结点A是根，其余结点分成互不相交的结点子集：T1 =B，E，F，J，KT2 =CT3 =D，G，H，I，LT1，T2，T3都是根A的子树，且它们本身也是一棵树。例如T1，根结点是B，其余结点又可分为两个互不相交的子集：T11=ET12=F，J，K,.,而T11是只有一个根结点的树，没有子树；T12中F是根，J和K是两棵互不相交的子树，其本身又是只有一个根结点的树。值得注意的是，每棵子树是绝对不能相交的，否则就不能构造一棵递归定义的树。,.,图7-1 树的示例,.,从树的示例中还可以看到，自然界中的树，树根在下，而数据结构中的树根在上。下面介绍树的一些相关术语。结点的度(Degree)：一个结点分出的子树个数称为该结点的度。如图7-1所示，A结点的度数是3，B结点的度数是2，C结点的度数是0。 叶结点：度数为零的结点称为叶结点。图7-1中的结点E、J、K、C、L、H、I的度数都为零，都是树的叶结点。还有一种情况，若树仅有一个结点，那么该结点既是根结点又是叶结点。通常叶结点也称作终结结点。,.,非终结结点：度数不为零的结点称为非终结结点，又叫做分支结点。如图7-1中的A、B、F、D、G等都是分支结点，根结点A也可称为非终结结点。树的度：树中结点的度数最大值称为树的度。如图7-1中结点A和D的度数为3，是树中结点度数的最大值。因此该树的度数也为3。树中结点之间的关系：通常用家族关系来形象地描述结点之间的关系。根结点的子树称为该结点的孩子(Child)，相应地，该结点称为孩子的双亲(Parents)。例如，图7-1中结点A是孩子B、C、D的双亲，也称结点A是子结点B、C、D的父结点。,.,同样在子树T1=B，E，F，J，K中结点B是结点E、F的父结点，E、F是结点B的子结点。同一父亲的孩子之间互称兄弟(Sibling)。例如在图7-1中，B、C、D都是A的孩子，因此它们就是兄弟；G、H、I都是D的孩子，它们也是兄弟；但是E和G不是兄弟，因E的父结点是B，G的父结点是D。将这种关系进一步推广，可以认为D是L的祖先。一个结点的祖先是指从根到该结点的路径上的所有结点。例如，B的子孙是E、F、J、K，L的祖先是G、D、A。,.,结点的层次(Level)：一棵树从根结点开始定义，根为第一层，根的孩子为第二层。若某结点在第i层，则其子树的根就在第i+1层。其双亲在同一层的结点互为堂兄弟。例如，在图7-1中树根结点A是第一层，B、C、D是第二层，E、F、G、H、I是第三层，J、K、L是第四层，其中E、F和G、H、I互为堂兄弟。树的深度(Depth)：树中结点的最大层次称为树的深度或称为高度。如图7-1中树的深度为4。森林(Forest)：m0棵互不相交的树的集合。图7-2给出了由三棵树T1、T2、T3组成的森林。我们也可以把树的根结点删除掉，形成由根的子树组成的森林。,.,图7-2 森林的示例,.,在树的范畴中还有二叉树、满二叉树、完全二叉树、二叉排序树、哈夫曼树等概念，我们将在本章中逐一讨论。,.,7.2 树的存储结构,树结构在计算机中的存储形式，将直接关系到树结构如何能被程序清晰、迅速、准确地处理。 树的基本结构是结点。图7-3给出了结点的结构示意图，其中，i是结点的序号，也可表示为该结点在存储状态的地址或指针。DATA是该结点的数据域。CHILDi是结点i的指针域，它们分别指向各子树的树根。,.,图7-3 树的结点结构,.,根据结点指针域的个数是否固定，可将结点的长度划分为定长结点和不定长结点两种。也可以用链表的形式加以区分，采用多重链表来表示树形结构，就能比较清晰地表示出家族关系(如父、子关系)和结点间的层次关系。 1多重链表表示法 多重链表由结点和链结点的指针组成，每个结点由一个数据域和若干个指针域组成，结点的结构如图7-3所示。每一个指针指向该结点的儿子。由于每个结点有多个孩子或没有孩子是根据需要而定的，也就是说，结点指针的多少也是根据子树的多少而设定的。根据指针设置的个数，多重链表可分为定长结点的多重链表和不定长结点的多重链表。,.,1) 定长结点的多重链表 为使树结点子树的个数最大，取树中结点的最大度数为每个结点的指针域个数。也就是说，不论结点的孩子个数多少，结点的长度均取最大长度。由于树中大部分结点的度数可能小于树的度数，因此该设计方法虽然能使树的处理简单方便，但是这种方法使相当部分的指针域为空，将会浪费很多存储空间。图7-4给出了定长结点的树的多重链表，其中结点B的度数最大为3，则定长结点中的指针域为3个。除了B结点之外，其余结点的指针域没有充分利用。,.,图7-4 定长结点的树的多重链表(a) 树；(b) 定长结点表示,.,2) 不定长结点的多重链表 树中每个结点的指针域个数等于该结点的孩子个数，每个指针指向一个孩子，每个叶结点不设指针域，在每个结点中设置一个度数域，表示该结点的度数。图7-5给出了7-4(a)所示的树的不定长结点的多重链表。图中A结点的度数为2，有2个链指针；B结点的度数为3，有3个链指针；E结点为叶结点，度数为0，没有指针域。不定长结点的多重链表，可以节约大量的存储空间，但树的处理比较复杂。,.,图7-5 不定长结点的多重链表,.,2树的顺序存储表示 在树的存储表示中，也可用顺序存储的线性表方式。设线性表DATA(n)表示结点的数据域，用m个线性表CHILDi(n)表示结点的指针域。以定长结点的方法为例，说明树的存储。图7-6表示了图7-4所示的树的存储状态。,.,图7-6 树的顺序存储表示,.,图7-6中(a)表示带有结点序号的树，其中结点A旁的1表示序号；图7-6(b)中DATA和CHILD1、CHILD2、CHILD3分别存放数据域和指针域，又设置变量T为树的入口，指向树根，这里T=1。显然，在这种方法中，通过CHILDi可以找到结点i的孩子或子树，当某结点的所有CHILDi为零时，该结点就是叶结点。 当然，树的存储结构还有很多种表示法，如二重链表法、三重链表法等，这里就不一一列举了。,.,7.3 二叉树,二叉树(Binary Tree)是一种很重要的树结构。它的特点是每个结点最多只能有两棵子树，故命名为二叉树。二叉树的子树有左、右之分，必须严格区分，其次序不能颠倒，即使在只有一棵子树的情况下，也应区分是左子树还是右子树，若改变次序则就变成另一棵二叉树了。7.3.1 二叉树的表示 二叉树是结点的有限集合，这个集合或者是空，或者由一个根结点和两棵互不相交的称为左子树和右子树的二叉树组成。,.,由于该定义用二叉树定义二叉树的结构，因此也是一个递归定义。从二叉树的定义可以得出，不含有任何结点的空树也是二叉树。图7-7是二叉树的五种基本形态。其中：(a)图是没有任何结点的空树；(b)图是仅有一个结点的二叉树，它既是根结点，也是叶结点；(c)图是有左子树，而右子树为空的二叉树；(d)图是有右子树，而左子树为空的二叉树；(e)图是左、右子树非空的二叉树。,.,图7-7 二叉树的五种基本形态,.,图7-8 二叉树与树的比较(a) 两个结点二叉树表示；(b) 两个结点树表示,.,二叉树的基本运算包括： (1) 二叉树初始化，其作用是设置一棵空二叉树BT= 。 (2) 二叉树求根ROOT(BT)，其结果是得到二叉树BT的根结点指针；若BT为，则是空二叉树。 (3) 求结点指针X的父结点PARENT(BT，X)，其结果是结点X在二叉树上的父结点的指针。 (4) 求父结点的左、右孩子LCHILD(BT，X)和RCHILD(BT，X)运算，其结果是求出父结点BT的左、右子树的根结点指针X。 (5) 建立二叉树CREAT(X，LBT，RBT)，其结果是建立一棵以结点X为根，以二叉树LBT、RBT分别为X的左、右子树的二叉树。,.,(6) 删除父结点的左子树或右子树DELLCHILD(BT，X)和DELRCHILD(BT，X)，其结果是在二叉树BT上删除其左子树或右子树。 7.3.2 二叉树的特性 从二叉树的形状可看出，二叉树有如下的外形特点： (1) 在二叉树中，第i层结点个数最多为2i-1个，其中i1。 第i层 第i层最多结点数 1 21-1 = 1 2 22-1 = 2 3 23-1 = 4 N 2n-1,.,关于这个结论，读者可以自行画不同层次的二叉树验证，也可用数学归纳法证明(本书从略)。(2) 一个深度为k的二叉树，最多有2k-1个结点，其中k1。深度 最多结点数1 21 -1 = 12 22 -1 = 33 23 -1 = 74 24 -1 = 15N 2n -1,.,(3) 对任何二叉树，若度数为2的结点为n2，则叶结点的个数为n0 = n2 +1。 下面介绍几种重要的二叉树。 满二叉树：一深度为k且有2k -1个结点的二叉树称为满二叉树。如图7-9所示是一深度为4的满二叉树。这种树的特点是每一层上的结点数都达到该层最大结点数。,.,图7-9 满二叉树,.,完全二叉树：对满二叉树的结点进行连续编号，约定编号从根结点起，自上而下，自左至右(如图7-9中满二叉树的编号)，由此可知深度为k、有n个结点的二叉树，能够与深度为k的顺序编号的满二叉树从1到n标号的结点相对应，则称这样的二叉树是完全二叉树。如图7-10所示是一深度为4的完全二叉树。从完全二叉树的定义和图示可以看到，该树具有以下特点： (1) 叶结点只能在最大的一层或最多只能在层次最大的两层上出现。(2) 对任一结点，若其右分支下子孙的最大层次为n(n1)，则其左分支下的子孙最大层次不小于1。,.,(3) 若是满二叉树，则必定是完全二叉树，反之不一定成立。,.,图7-10 完全二叉树,.,在图7-10中，完全二叉树的叶结点出现在第三、第四层；而图7-9所示的树既是满二叉树，也是完全二叉树，其叶结点仅出现在最大的层次(第四层)上。图7-11所示的两棵树均不是完全二叉树，(a)图中树的结点的编号不是按照满二叉树从1至n编排，6号、7号两个结点应是3号结点的左子树和右子树；(b)图中6号结点是3号结点的右子树，但3号结点的左分支的最大层次为零，所以也不是完全二叉树。,.,图7-11 非完全二叉树,.,7.3.3 二叉树的存储结构 二叉树有顺序存储结构和链式存储结构两种。 1顺序存储结构 线性表的存储结构可以用于对二叉树的存储，这对于完全二叉树和满二叉树比较合适。其方法是对二叉树进行编号，然后将二叉树中编号为i的结点的数据存放在线性表LIST(i)中，使其一一对应。图7-12中的二叉树线性表表示是根据图7-10所示的完全二叉树按结点的编号而存放的。,.,图7-12 二叉树线性表表示,.,同样，按此方式对满二叉树进行顺序存储也是合适的。这种存储方法既不浪费内存，又可以利用一维地址的计算公式，在已知向量地址的基础上确定结点的地址。由于顺序存储是以结点在线性表中的位置表示结点之间的关系的，因此，对一般的二叉树也按结点的序号进行顺序存储时，将造成极大的浪费。如图7-13(a)中一般的二叉树，树的入口T指向1号单元，其他的结点按每个结点的指定序号存储，可以看到空间的利用率是相当低的。从图7-13(a)中可以看出，二叉树仅有四个结点，由于结点的序号最小为1，最大为12，,.,因此顺序存储的线性表结构至少长度为12，该存储空间的利用率仅33%；图7-13(b)中的二叉树实际是单链结构，显然用顺序存储的方法解决二叉树的存储方法是不尽合理的。,.,图7-13 一般二叉树的顺序分配,.,2链式存储结构 用链指针表示二叉树，根据二叉树的定义，每个结点要设置一个数据域和两个指针域：左孩子LCHILD(通常用左子树指针Lnext)和右孩子RCHILD(右子树指针Rnext)。图7-14是二叉树的链式存储分配状态。图7-14(a)是二叉树结点的结构图，i是结点的序号或结点的存储地址，数据域可根据实际需要而设定数据项。图7-14(c)是(b)图中二叉树的链式存储表示，每一结点的左子树指针的值iLnext表示所指向的左子树的树根或指向左子树的根结点地址。,.,图7-14 二叉树的链式存储,.,图7-15 二叉树的存储状态,.,图7-15给出了图7-14(c)所示的链式存储表示的存储状态。 用链表所表示的二叉树存储方式，也会出现存储空间的浪费，尤其是叶结点，其结点的左、右指针均为空，有些结点的指针域也没有被利用，因为并非所有的结点都有左、右指针。 二叉树所谓的留下的空域在线索树中将会被使用，这里不做讨论。 除了以上按结点域分配外，还可根据实际的需要增加一个指向父结点的指针，这里不作具体的介绍。,.,我们主要讨论具有三个域左指针域iLnext、数据域iDATA和右指针域iRnext的二叉树以及相应的运算和操作。,.,7.4 遍历二叉树,遍历(Traversal)二叉树是指按一定的规则和次序，访问二叉树中的每个结点，且每一结点只能被访问一次。所谓访问，就是在遍历过程中对每一个结点的数据域进行查阅、修改和加工或进行其他的操作。遍历二叉树的过程实际上就是得到二叉树中各结点的线性排序，使非线性的二叉树线性化。根据二叉树的结构特征可知，每个结点都可能有两棵子树，即有两个分支，因此就要寻找一种规律，使得所遍历的次序不同，得到访问的每一个结点的排列次序也不同。,.,7.4.1 遍历二叉树的递归算法 从二叉树的递归定义可得知，二叉树由三个基本单元组组成，即根结点的数据、 左子树和右子树。图7-16给出了二叉树的基本结构形式。假如以L、D、R分别表示遍历左子树、访问根结点和遍历右子树，则对一棵二叉树有六种不同的遍历方式：DLR、LDR、LRD、DRL、RDL、RLD。若限定遍历子树的次序是先左后右，则只有前三种情况：DLR(先根遍历)、LDR(中根遍历)、LRD,.,图7-16 二叉树的基本结构,.,(后根遍历)，本书主要讨论这三种情况。1二叉树的中根遍历 在二叉树的遍历中，应用较广的是二叉树的中根遍历(LDR)。其遍历的递归定义如下： 若二叉树为空，则返回；否则，进行如下操作： (1) 按中根次序遍历左子树； (2) 访问根接点； (3) 按中根次序遍历右子树； (4) 返回。,.,中根遍历的递归定义可理解为对于非空的二叉树，首先从根结点进入，然后“遇左寻左”，即从当前结点判断有无左子树，若有左子树，则不断地找该结点的左子树；若该结点无左子树了，则“无左访中”，即访问中间的根结点；然后从被访问的结点判断有无右子树，即“最后寻右”，若存在右子树，则从右子树的树根入口，按中根遍历的法则访问结点。 图7-17给出了两棵不同形状的二叉树，按中根遍历的规则得到(a)图的结点序列是 GDHBEAIFJC 按中根历的规则得到 (b)图的结点序列是 BGDAEHCF,.,图7-17 二叉树的中根遍历,.,在中根遍历图7-17(b)的过程中，从根结点T2进入，由于A结点有左子树，所以“有左寻左”，通过A结点的左指针得B结点，因为结点B没有左子树，故“无左访中”，即访问当前根结点B，这就是(b)图中首先访问B结点的原因。 中根遍历二叉树的递归算法叙述比较简单，描述如下：INORDER(t)/* 按中根遍历二叉树t */ if(t! = NULL) INORDER(t lnext)；/* 递归调用，达到递归访问左子树 */,.,printf(%dn，tdata)； INORDER(trnext)；/* 递归访问右子树 */ 递归算法简明扼要，这对于允许递归调用的语言是合适的。但是设计递归程序相对难度较大，读者可以根据实际情况选择使用。,.,2二叉树的先根遍历 二叉树的先根遍历对二叉树形式所表示的表达式的计算是很有效的。图7-18是表达式(a+b *(c-d)-e/f的二叉树表示。 根据先根遍历法则，对图7-18所示的二叉树进行遍历，得到的访问序列为- + a*b - cd/ef，这就是表达式中的前缀表示或称作逆波兰表示。它可以使表达式的计算按计算机容易实现的扫描方法完成表达式的计算，同时保证表达式计算中的次序。,.,图7-18 表示表达式的二叉树,.,先根遍历的递归算法可归纳为以下几个步骤： 若二叉树为空，则返回，否则： (1) 按先根次序访问根结点； (2) 按先根次序遍历左子树； (3) 按先根次序遍历右子树； (4) 返回。 根据先根遍历二叉树的递归定义，有如下的递归过程的算法：,.,PREORDER(t)/* 按先根遍历二叉树t，t是树的入口 */ if(t! = NULL) printf(%dn，tdata)； PREORDER (tlnext)； PREORDER (trnext)； ,.,PREORDER是一个递归过程，通过对图7-18所示表示表达式的二叉树的先根遍历执行过程进行分析，解析递归执行的过程。算法在执行中，第一次调用本过程为主调用，过程在执行中再调用过程本身为递归调用。图7-19是PREORDER递归调用的执行过程。在遍历二叉树中，访问根结点，输出该结点的数据域的值a，图中写成“访根”；递归调用，遍历左子树，图中写为“左”；递归调用，遍历右子树，图中写为“右”；方括号“ ”所括出的范围是说明某一次调用的内容。,.,图7-19 PREORDER递归执行情况,.,通过对图7-18所示的二叉树的先根遍历递归调用过程的分析，可以清楚递地了解递归调用的执行情况。图7-19中进入以PREORDER为过程名的算法就是最外层的主调用，它包含该算法的全过程。以递归方式描述的算法，简明扼要，程序也较精炼。但了解程序执行的递归过程，具有一定深度。在递归程序执行时，除了用一个地址栈保存程序返回的地址外，还要有一个栈保存调用的参数和工作单元的内容，以便程序在执行过程中不被破坏，待递归返回后可继续使用。,.,递归调用的过程大致如下： (1) 参数和工作单元依次进栈； (2) 递归程序返回地址进栈； (3) 形参和实参相替代； (4) 调用子过程； (5) 调用结束，数据栈依次退出参数和工作单元； (6) 返回地址退栈，原程序继续执行。 根据以上的递归调用原则，对上述执行过程作如下说明：,.,在主调用的括号里，由于图7-18是非空二叉树，T不为空，在递归算法中首先访问根结点“-”，接着是第一次递归调用算法本身。算法中形式参数“T”用左子树Lnext(T)的实参代替，同时执行程序的有关数据、工作单元和返回地址进栈保存。在执行第一次递归调用中，也首先访问当前的根结点“+”，然后又是第二次递归调用，再一次进栈保存参数、工作单元和返回地址，执行递归遍历右子树。访问当前所遍历的根结点“a”，当紧接着下一次递归调用“a”的左子树时，由于该结点是叶结点，其左子树为空，故返回，即结束本次左子树遍历的递归调用，图7-19中表示为：左访根空，返回。,.,然后，系统从栈中依次退出递归地遍历以“a”为根结点的右子树时的有关参数、工作单元的数据和执行的地址。由于“a”的右子树为空，不执行算法中遍历右子树的程序，图7-19中表示为：右访根空，返回。至此，算法已完成第二次遍历左子树的过程。返回第一次递归调用，然后又递归地遍历“+”为结点的右子树。依次类推，直至整个递归调用结束。 以上是先根遍历的递归算法。 3二叉树的后根遍历 后根遍历的算法步骤可归纳如下： 若二叉树为空，则返回，否则：,.,(1) 按后根次序遍历左子树； (2) 按后根次序遍历右子树； (3) 访问根结点； (4) 返回。 根据以上的递归含义，有如下递归算法： POSTORDER(t) /* 按后根遍历二叉树t，t是树的入口 */ if(t! = NULL) POSTORDER(tlnext)； POSTORDER(trnext)；,.,printf(%dn，tdata)； 如图7-20中的二叉树，入口为T，结点内的数据是数据域的关键值，结点上的数表示结点的序号或结点的地址。如指针为6的结点是二叉树的根结点，即树的入口为6，6data=A。后根遍历的结果是 DGEBFCA 后根遍历二叉树，若有n个结点，对结点的访问算法的执行量级为O(n)。,.,图7-20 后根遍历的二叉树,.,7.4.2 中根遍历的非递归算法 实现中根遍历的算法有递归和非递归两种。由于运行环境和设计要求不同，因此中根遍历的非递归算法有相当的适应性，而且在设计非递归算法的过程中，将有助于提高读者逻辑思维和判断数据流向的能力。 以下是非递归算法的设计算法思想： 设T是二叉树的入口；Stack(top)是栈，栈指针top=1，2，n；i是结点的序号(地址)。 若树T为空，则返回，否则： (1) 树的根结点进栈；,.,(2) 若栈不空，则栈顶结点出栈，该结点作为当前子树的根结点； (3) 不断地寻找当前根结点的左子树，若有左子树，当前结点进栈，直至当前子树的根结点无左子树； (4) 访问当前结点； (5) 若访问结点有右子树，则右子树的根结点进栈，否则栈顶的结点出栈。 重复步骤(2)、(3)、(4)、(5)，直至结束。 必须注意：算法中所涉及的是结点的序号或地址，若得到了结点的序号，则该结点的数据域和指针域均可读出。,.,图7-21是根据中根遍历非递归算法思想画出的程序流程框图。,.,图7-21 中根遍历非递归算法框图,.,以下是根据中根遍历的非递归算法框图而编写的算法。INORDER(t)/* 中根遍历二叉树入口为t的算法，stack(1:n)是栈 */if(t! = NULL) top =1；stack top = t；/* 栈初始化 */ while(top!=0) i = stack top ； top+； ,.,/* 出栈的结点作为当前遍历的左子树的根结点 */ while(iLnext!=NULL) /* 当前遍历的子树是否有左子树 */ if(topn) printf(栈溢出)； else top +； stacktop= i；,.,i = iLnext； while(i! = NULL) printf(%dn，idata)； if(irnext!=NULL) if(topn) printf(栈溢出)； ,.,else top +； stacktop= irnext； i = NULL； /* 当前访问结点有右子树，右子树进栈，准备递归地访问该树根结点的左子树 */ else if(top!= 0),.,top-； /* 栈顶结点退栈，准备立即访问该结点 */ else i = NULL； /* 栈空，结束算法 */ ,.,执行以上算法，设遍历的二叉树有n个结点，访问所有的结点要执行循环语句n次，才完成结点的访问。每个结点都必须进栈和出栈各一次。因此入栈和出栈的操作要各执行n次。这样，该算法的执行量级为O(n2)。,.,7.5 树和森林,树结构已广泛应用于信息管理、数据库系统、操作系统和应用程序中，这里主要介绍为了便于对树结构中的信息进行处理而做的森林和树对于二叉树的转换。 在一般情况下，树是由多链表表示的，也就是说树中的某个结点可以由多个子结点组成，每个子结点由链指针链接。树在计算机中一般有两种链表表示方法第一种采用不定长度结点的多重链表表示，其每个,.,结点的指针域是按该结点的子结点个数而定的，每个链指针指向一个子结点，结点有n个孩子，就需要n个指针。该方法虽然可以节省一定数量的存储空间，但给存储分配和各种运算都带来很大的困难。第二种采用固定长度结点的多重链表表示，树中所有结点的指针个数都取树的度数。用这种方法，可以使树的处理比较简单，但存储空间浪费很大。最重要的是一般树的处理算法(包括查找、插入和删除的算法)均比较复杂，而对于二叉树已有一系列遍历、查找、插入和删除的成熟算法。因此完成树和森林对二叉树的转换能简化对树的处理。以下讨论树、森林对二叉树的相互转换。,.,7.5.1 森林与二叉树的转换 把一般树转换成二叉树可按下列步骤进行操作： (1) 加线：在各同胞兄弟结点之间加一虚线。 (2) 切线：对每个结点，除了保留其最左边的孩子 外，切断该点与其余孩子之间的连线。 (3) 旋转：以树的根结点为旋转的轴心，将整棵树按顺时针方向旋转45，且把新加上的虚连线变为实线。 图7-22给出了一般树转化为二叉树的三个步骤。 必须注意，树中某结点仅有一个孩子时，在转换成二叉树后，该孩子必定成为其父结点的左孩子。,.,图7-22 树转换成二叉树过程(a)一般树；(b)加线后；(c)切线后；(d)旋转后,.,转换成的二叉树有两个特点： (1) 第一层结点没有右子树，即二叉树的根结点没有右子树。 (2) 转换后的二叉树中各结点的右孩子是原树中该结点的兄弟， 而该结点的左孩子还是原来树中该结点最左边的孩子。 森林是树的有限集合，使森林转化为二叉树，其变换的规则与 树转换成二叉树有很多相似之处： (1) 加线：在每棵树的根结点之间加一虚线；同时，在每棵树各同胞兄弟点之间也加一虚线。,.,(2) 切线：对于每一棵树中的所有结点，除了保留其最左边的孩子外，切断该结点与其余孩子之间的连线。 (3) 旋转：以森林中最左边一棵树的根结点为旋转的轴心，将整个森林按顺时针方向旋转45，并且把新加上的虚连线改为直线。 图7-23给出了森林转化为二叉树的整个过程。,.,图7-23 森林转化为二叉树的过程(a)森林；(b)加线后；(c)切线后；(d)旋转后,.,森林转化为二叉树，转化过程中除了在森林的每棵树的根结点之间加一虚连线外，其他的步骤完全与将树转化为二叉树相同。 n(n2)棵树所组成的森林所转换的二叉树，树的根结点有右子树，这是它与一般的树转化成二叉树的根本区别。 关于二叉树如何再转化成为一般的树和森林的问题留给读者作为练习。,.,7.5.2 树的遍历 与二叉树类似，对树中结点的遍历也是一种重要的运算。由于树中的子树可以有两棵以上，因此就不存在二叉树结点的中序遍历。以下给出常用的、实现比较方便的树中结点的三种遍历方法：先根遍历、后根遍历和层次遍历。 1先根遍历 若树非空，则 （1) 访问根结点； (2) 依次先根遍历的各个子树T1，T2，Tm。 如图7-24所示的树，先根遍历的结果是：ABECFGHIJLKD。,.,图7-24 树的遍历,.,2后根遍历若树非空，则(1) 依次后根遍历的各个子树T1，T2，Tm；(2) 访问根结点。如图7-24所示的树，后根遍历的结果是：EBFHILJKGCDA。,.,3层次遍历若树非空，则(1) 访问根结点；(2) 若第1，i，n(i1)层结点已被访问，且第i+1层结点尚未被访问，则从左到右依次访问第i+1层中树的结点。 如图7-24所示的树，层次遍历的结果是：ABCDEFGHIJKL。从树的遍历结果可以看出，树的先根遍历对应树转换为二叉树的先根遍历结果，树的后根遍历对应树转换为二叉树的中根遍历结果。因此，当以二叉链表作为树的存储结构时，树的先根遍历和后根遍历可以借用二叉树的先根遍历和中根遍历的算法实现，读者可以自行验证。,.,7.6 哈夫曼树及其应用,7.6.1 哈夫曼树的表示对于给定一组记录的元素，若以每个结点包含一个记录，就可以构造出若干个不同的二叉树，设有A、B、C、D、E五个记录，构造成图7-25所示两棵不同的二叉查找树。可以看出，任一元素的查找时间取决于该结点在树中所处的位置。如果待查找的结点处于二叉树的第k层上，则需要进行k次比较，如图7-25(a)中结点E要进行四次比较才能查到，而图7-25(b)中则只要三次比较就能查找成功。,.,图7-25 同一组元素构造两种不同的二叉树,.,若每个结点的查找概率相等，则图7-25(b)中的二叉树要比图7-25(a)中的二叉树查找的效率高。这可以从二叉树查找的平均比较次数得到判断。图7-25(a)中的平均查找次数为图7-25(b)中的平均查找次数为,.,因此，对于给定的一组记录元素，所构造的二叉树应该尽可能减小树的深度。然而，在实际的应用中，并非每个记录的查找概率都是相等的，有的记录由于需要而经常被查询，而有的记录只是偶尔被查询。由此可见，所构造的二叉树的查找效率不仅与结点在树中的位置有关，而且还与结点的查找概率有关，这就是哈夫曼树问题。在介绍哈夫曼树之前，首先介绍有关树的路径长度问题。,.,两个结点之间的路径长度是指从一个结点到另一个结点之间所经过的路的条数。从树的根结点到每一个结点的路径长度之和称为树的路径长度，用PL表示。对于图7-25(a)而言PL =0+1+1+2+3 =7对于图7-25(b)而言PL =0+1+1+2+2 =6,.,以上讨论是在每个结点平均查找概率相同的情况下进行的。如果在路径长度的概念中加入查找概率的因素，可把查找概率作为数值赋给结点。而且，我们仅考虑给叶结点加权，而不是给所有的结点加权。称这种叶结点加权的二叉树为叶子二叉查找树，又叫空心二叉树。设有一组实数为权，其集合表示为W1，W2，Wn定义叶子二叉查找树的加权路径长度为WPL =,.,其中，Lk为从根到具有权Wk的叶结点的长度。对于给定的一组权值，可以构造出若干个不同形式的叶子二叉查找树。例如，有组权WG =2，4，5，8，图7-26有三种可能的叶子二叉查找树，其加权路径长度分别为 (a) WPL =22+42+52+82 =38(b) WPL =21+42+53+83 =49(c) WPL =81+52+23+43 =36,.,图7-26 具有不同加权路径长度的二叉查找树,.,7.6.2 哈夫曼树的构造那么怎样才能构造出一棵有最小叶结点加权路径长度的二叉树呢-这就是以下要讨论的哈夫曼算法和哈夫曼树。哈夫曼算法的算法思想简述如下：(1) 给定一组权值的数列WG =W1，W2，Wn，把权值赋给n个结点，从而生成一个森林F，使得F中有n棵只有一个根结点的树Ti，并且Ti带有权值Wi;(2) 将森林F中的树按根的权值由小到大排序；(3) 从森林中取出第一和第二棵树构成一棵新树，使新树根的权值为两棵树的根的权值之和，并且以第一棵为新树的左子树，第二棵为右子树，再把该树放到森林F中；,.,(4) 重复执行步骤(2)、(3)，直到森林F中只有一棵树为止。按哈夫曼算法构造的叶结点带权的二叉树为哈夫曼树。设有一组权值WG=8，5，2，4，其哈夫曼树的构造过程如图7-27所示。,.,图7-27 哈夫曼树的构造过程,.,7.6.3 哈夫曼树的应用在利用哈夫曼树的结构时，权值为查找频率，频率越大就越靠近根结点，这样可以构造成最佳判断过程。我们把整个判断过程看成二叉树，以开始测试作为根结点，测试或判断的结果分成两个方向，选其中的一个分支再作进一步的测试和判断，最后得到某测试数据的属性。例如，完成对一批正整数进行分类，其要求如下：(1) 某数ai20，属于第一类，出现频率为2/18；(2) 20ai50，属于第二类，出现频率为4/18；(3) 50ai100，属于第三类，出现频率为5/18；(4) ai100，属于第四类，出现频率为7/18。,.,给出的每一个数都要求判断是否属于第n类，可按一般的逻辑顺序得到判断过程之一。如图7-28所示，按此判断过程，将得到平均执行时间为最长。,.,图7-28 一般逻辑判断过程,.,对以上的判断方式作一点修改，即按哈夫曼树的构造原则组织判断过程，如图7-29所示，则判断过程的平均执行时间时间最短。,.,图7-29 哈夫曼树应用于判断过程,.,7.7 二叉树的应用举例,前面介绍了二叉树的先根、中根和后根遍历的算法。若以C语言在计算机中实现二叉树的遍历或应用二叉树的遍历解决实际问题，则先要建立二叉树的链表结构。我们可以用多种方法建立二叉树，这里介绍用线性表的方式存储二叉树的数据域和指针域。如对图7-20所示的二叉树建立三个线性表：DATA(i)、RLINK(i)和LLINK(i)，i =1，2，7。图7-30表示了存储状态，其中T是树的入口。,.,图7-30 对图7-20所示的二叉树的线性表表示,.,建立线性表的存储表示，可以用如下的变量说明和过程表示图7-20所示的二叉树： char data 8； int rlink 8，llink 8； int i，j，l； char k ； CREATE( ) for( i =1；i=7；i+) scanf(%d%d%d，&j，&k，&l)；,.,/* j是序号为i的左子树，l是i的右子树，k是结点i的数据值 */ data i = k； rlink i = j； llink i = l； t = 6； /* 建立二叉树的入口 */ ,.,实现以上的算法，可以建立一棵以T(T=6)为入口的二叉树。如要得到序号为7的结点的值“E”，其路径为：从T=6入口，以LLINK(6)=5，得到6号结点的左子树的根为5号结点，再从5号结点的右子树RLINK(5)=7，得到7号结点，然后从DATA(7)得到该结点的值“E”。我们可以从二叉树的遍历中，访问每一个结点的关键值，查询和检索二叉树中所需要的信息。例7.1 有一棵二叉树，入口为T，每一个结点存放着某企业中职工的工号“no”、职工的工资数“a1”、职工的工龄“a2”等，要求通过遍历二叉树，输出工资a1中大于h并且工龄数大于k的职工的工号。,.,下面我们用C语言，以中根遍历的非递归算法实现以上的设计要求。struct treenode char no，a1，a2； struct treenode * rnext，* lnext； n =1000；struct treenode * h，* i，* stack n；char g n；char h，k；int top，p，j；SLB(struct treenode * h),., if(t!=NULL) CREATE( )； p=0； top =1； stack top=h； h =getchar( )；h =getchar( )； while(top!= 0),., i =stacktop； top-； while( i -lnext!=NULL) if(top)= n( ) printf(STACK FULL)； exit(l)； else top +； stacktop = i； i = i-lnext； ,.,while(i!=NULL) if(i -a1h)&(i -a2k) if(pno； else puts(LIST FULL)； exit(2)； ,.,if(i -rnex