数据结构描述树

《数据结构描述树》由会员分享，可在线阅读，更多相关《数据结构描述树（100页珍藏版）》请在金锄头文库上搜索。

1、第第6 6章章 树树 数据结构（C+描述）6.6哈夫曼树.树和森林6.4线索二叉树线索二叉树6.3遍历二叉树6.2二叉树6.1 树的基本概念树的基本概念退出目录6.1 树的基本概念树的基本概念6.1.1 树的定义树的定义1树的定义树是由n（n0）个结点组成的有限集合。若n=0，称为空树；若n0，则：（1）有一个特定的称为根（root）的结点。它只有直接后继，但没有直接前驱；（2）除根结点以外的其它结点可以划分为m（m0）个互不相交的有限集合T0，T1，Tm1，每个集合Ti（i=0,1,m1）又是一棵树，称为根的子树，每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。由此可知，树

2、的定义是一个递归的定义，即树的定义中又用到了树的概念。树的结构参见图61。在图61(c)中，树的根结点为A，该树还可以分为三个互不相交子集T0，T1，T2，具体请参见图62，其中T0=B，E，F，J，K，L，T1=C，G，T2=D，H，I，M，其中的T0，T1，T2都是树，称为图61（C）中树的子树，而T0，T1，T2又可以分解成若干棵不相交子树。如T0可以分解成T00，T01两个不相交子集，T00=E，J，K，L，T01=F，而T00又可以分为三个不相交子集T000，T001，T002，其中，T000=J，T001=K，T002=L。2树的逻辑结构描述一棵树的逻辑结构可以用二元组描述为：tr

3、ee=(k,R)k=ki1in;n0,kielemtypeR=r其中，n为树中结点个数，若n=0，则为一棵空树，n0时称为一棵非空树，而关系r应满足下列条件：（1）有且仅有一个结点没有前驱,称该结点为树根;（2）除根结点以外,其余每个结点有且仅有一个直接前驱;（3）树中每个结点可以有多个直接后继(孩子结点)。例如，对图61(c)的树结构,可以二元组表示为：K=A，B，C，D，E，F，G，H，I，J，K，L，MR=rr=(A,B)，(A,C)，(A,D)，(B,E)，(B,F)，(C,G)，(D,H)，(D,I)，(E,J)，(E,K)，(E,L)，(H,M)3树的基本运算树的基本运算可以定义如

4、下几种：(1) inittree(&T)初始化树T。(2) root(T)求树T的根结点。(3) parent(T,x)求树T中，值为x的结点的双亲。(4) child(T,x,i)求树T中，值为x的结点的第i个孩子。(5) addchild(y,i,x)把值为x的结点作为值为y的结点的第i个孩子插入到树中。(6) delchild(x,i)删除值为x的结点的第i个孩子。(7) traverse(T)遍历或访问树T。6.1.2 基本术语基本术语1.结点指树中的一个数据元素，一般用一个字母表示。2.度一个结点包含子树的数目，称为该结点的度。3.树叶（叶子）度为0的结点，称为叶子结点或树叶，也叫终

5、端结点。4.孩子结点若结点X有子树，则子树的根结点为X的孩子结点，也称为孩子，儿子，子女等。如图61（c）中A的孩子为B，C，D。5.双亲结点若结点X有子女Y，则X为Y的双亲结点。6.祖先结点从根结点到该结点所经过分枝上的所有结点为该结点的祖先，如图61（c）中M的祖先有A，D，H。7.子孙结点某一结点的子女及子女的子女都为该结点子孙。8.兄弟结点具有同一个双亲的结点，称为兄弟结点。9.分枝结点除叶子结点外的所有结点，为分枝结点，也叫非终端结点。10层数根结点的层数为1，其它结点的层数为从根结点到该结点所经过的分支数目再加1。11.树的高度（深度）树中结点所处的最大层数称为树的高度，如空树的高

6、度为0，只有一个根结点的树高度为1。12.树的度树中结点度的最大值称为树的度。13. 有序树有序树 若一棵树中所有子树从左到右的排序是有顺序的，不能颠倒次序。称该树为有序树。14. 无序树无序树若一棵树中所有子树的次序无关紧要，则称为无序树。15森林（树林）森林（树林）若干棵互不相交的树组成的集合为森林。一棵树可以看成是一个特殊的森林。 6.1.3 树的表示树的表示1树形结构表示法树形结构表示法 具体参见图61。2. 凹入法表示法凹入法表示法具体参见图63。3. 嵌套集合表示法嵌套集合表示法具体参见图64。4.广义表表示法广义表表示法对图61（c）的树结构，广义表表示法可表示为：（ A（ B（

7、 E（ J， K， L） ， F） ， C（ G） ，D（H（M），I）6.1.4 树的性质树的性质性质性质1树中的结点数等于所有结点的度加1。证明：根据树的定义，在一棵树中，除根结点以外，每个结点有且仅有一个直接前驱，也就是说，每个结点与指向它的一个分支一一对应，所以，除根结点以外的结点数等于所有结点的分支数（即度数），而根结点无直接前驱，因此，树中的结点数等于所有结点的度数加1。性质性质 2 度为k的树中第i层上最多有ki1个结点（i1）。下面用数学归纳法证明：对于i=1，显然成立，假设对于i1层，上述条件成立，即第i1层最多有ki2个结点，对于第i层，结点数最多为第i1层结点数的k倍（因

8、为度为k），故第i层的结点数为ki2*k=ki1。性质性质3深度为h的k叉树最多有个结点。证明：由性质2可知，若每一层的结点数最多，则整个k叉树结点数最多，共有=k0+k1+kh1=。当一棵K叉树上的结点数达到时，称为满满K叉叉树树。性质性质4具有n个结点的k叉树的最小深度为logk(n(k1)+1)。（请注意，x表示取不小于x的最小整数，或叫做对x上取整。）证明：设具有n个结点的k叉树的深度为h，即在该树的前面 h1层 都 是 满 的 ， 即 每 一 层 的 结 点 数 等 于 ki1个(1ih1)，第h层（即最后一层）的结点数可能满，也可能不满，这时，该树具有最小的深度。由性质3知道，结点

9、数n应满足下面条件：n，通过转换为：kh1n(k1)+1kh，再取以k为底的对数后，可以得到：h1logk(n(k1)+1)h，即有：logk(n(k1)+1)h0）。可以用数学归纳法证明之。性质性质2深度（高度）为k的二叉树最大结点数为2k1（k0）。证明：深度为k的二叉树，若要求结点数最多，则必须每一层的结点数都为最多，由性质1可知，最大结点数应为每一层最大结点数之和。既为20+21+2k1=2k1。性性质质3 对任意一棵二叉树，如果叶子结点个数为n0，度为2的结点个数为n2，则有n0=n2+1。证明：设二叉树中度为1的结点个数为n1，根据二叉树的定义可知，该二叉树的结点数n=n0+n1+

10、n2。又因为在二叉树中，度为0的结点没有孩子，度为1的结点有1个孩子，度为2的结点有2个结孩子，故该二叉树的孩子结点数为n0*0+n1*1+n2*2，而一棵二叉树中，除根结点外所有都为孩子结点，故该二叉树的结点数应为孩子结点数加1即：n=n0*0+n1*1+n2*2+1因此,有n=n0+n1+n2=n0*0+n2*1+n2*2+1，最后得到n0=n2+1。为继续给出二叉树的其它性质，先定义两种特殊的二叉树。满满二二叉叉树树深度为k具有2k1个结点的二叉树，称为满二叉树。从上面满二叉树定义可知，必须是二叉树的每一层上的结点数都达到最大，否则就不是满二叉树。完完全全二二叉叉树树 如果一棵具有n个结

11、点的深度为k的二叉树，它的每一个结点都与深度为k的满二叉树中编号为1n的结点一一对应，则称这棵二叉树为完全二叉树。从完全二叉树定义可知，结点的排列顺序遵循从上到下、从左到右的规律。所谓从上到下，表示本层结点数达到最大后，才能放入下一层。从左到右，表示同一层结点必须按从左到右排列，若左边空一个位置时不能将结点放入右边。从满二叉树及完全二叉树定义还可以知道，满二叉树一定是一棵完全二叉树，反之完全二叉树不一定是一棵满二叉树。满二叉树的叶子结点全部在最底层，而完全二叉树的叶子结点可以分布在最下面两层。深度为4的满二叉树和完全二叉树如图66所示。性性 质质 4 具 有 n个 结 点 的 完 全 二 叉

12、树 高 度 为log2(n)+1或log2（n+1）。(注意x表示取不大于x的最大整数，也叫做对x下取整，x表示取不小于x的最小整数，也叫做对x上取整。)证明：设该完全二叉树高度为k，则该二叉树的前面k1层为满二叉树，共有2k11个结点，而该二叉具有k层，第k层至少至少有1个结点，最多有2k1个结点。因此有下面的不等式成立：（2k1 1） +1 n （2k11）+2k1，即有2k1n2k1。由式子后半部分可知,n2k1由式子前半部分可知2k1n由有n+12k，同时取对数得：log2(n+1)k故klog2(n+1),即k=log2(n+1)。即得到第二个结论。由有2k1n,同时取对数得：klo

13、g2n+1即k=log2n+1,即第一个结论成立,证毕。性性质质5如果将一棵有n个结点的完全二叉树从上到下，从左到右对结点编号1，2，n，然后按此编号将该二叉树中各结点顺序地存放于一个一维数组中，并简称编号为j的结点为j(1jn)，则有如下结论成立：（1）若j=1，则结点j为根结点，无双亲，否则j的双亲为j/2；（2）若2jn，则结点j的左子女为2j,否则无左子女。即满足2jn的结点为叶子结点；（3）若2j+1n，则结点j的右子女为2j+1，否则无右子女；（4）若结点j序号为奇数且不等于1，则它的左兄弟为j1；（5）若结点j序号为偶数且不等于n，它的右兄弟为j+1；（6）结点j所在层数(层次)

14、为log2j+1；6.2.3 二叉树的存贮结构二叉树的存贮结构1顺序存贮结构顺序存贮结构将一棵二叉树按完全二叉树顺序存放到一个一维数组中，若该二叉树为非完全二叉树，则必须将相应位置空出来，使存放的结果符合完全二叉树形状。如图67给出了顺序存贮形式。对于一棵二叉树,若采用顺序存贮时,当它为完全二叉树时,比较方便,若为非完全二叉树,将会浪费大量存贮存贮单元。最坏的非完全二叉树是全部只有右分支,设高度为K,则需占用2K1个存贮单元,而实际只有k个元素,实际只需k个存储单元。因此，对于非完全二叉树，宜采用下面的链式存储结构。2二叉链表存贮结构（1）二叉链表表示）二叉链表表示将一个结点分成三部分,一部分

15、存放结点本身信息,另外两部分为指针,分别存放左、右孩子的地址。二叉链表中一个结点可描述为:对于图67所示二叉树,用二叉链表形式描述见图68。对于一棵二叉树,若采用二叉链表存贮时,当二叉树为非完全二叉树时,比较方便,若为完全二叉树时,将会占用较多存贮单元(存放地址的指针)。若一棵二叉树有n个结点,采用二叉链表作存贮结构时,共有2n个指针域,其中只有n1个指针指向左右孩子,其余n+1个指针为空,没有发挥作用,被白白浪费掉了,(当然后面介绍的线索可利用它)。（2）二叉链表的数据类型）二叉链表的数据类型二叉链表的数据类型描述如下:structbitreeelemtypedata;/结点数据类型bitr

16、ee*lchild,*rchild;/定义左、右孩子为指针型(3)二叉链表的建立二叉链表的建立为了后面遍历二叉树方便，先介绍建立二叉链表的算法（假设elemtype为char型）。假设二叉链表的数据类型描述如刚才所述，为建立二叉链表，用一个一维表数组来模拟队列，存放输入的结点，但是，输入结点时，必须按完全二叉树形式，才能使结点间满足性质5，若为非完全二叉树，则必须给定一些假想结点(虚结点)，使之符合完全二叉树形式。为此，我们在输入结点值时，存在的结点则输入它对应的字符，不存在的结点(虚结点)，输入逗号，最后以一个特殊符号“#”作为输入的结束,表示建二叉链表已完成。建成的二叉链表可以由根指针ro

17、ot唯一确定。算法描述如下：#includetypedefcharelemtype;structbitreeelemtypedata;bitree*lchild,*rchild;bitree*create()bitree*q100;/定义q数组作为队列存放二叉链表中结点，100为最大容量bitree*s;/二叉链表中的结点bitree*root;/二叉链表的根指针intfront=1,rear=0;/定义队列的头、尾指针charch;/结点的data域值root=NULL;cinch;while(ch!=#)/输入值为#号,算法结束s=NULL;if(ch!=,)/输入数据不为逗号,表示不为虚

18、结点,否则为虚结点s=newbitree;sdata=ch;slchild=NULL;srchild=NULL;rear+;qrear=s;/新结点或虚结点进队if(rear=1)root=s;elseif(s!=NULL)&(qfront!=NULL) if(rear%2=0) qfrontlchild=s; /rear为偶数,s为双亲左孩子elseqfrontrchild=s;/rear为奇数,s为双亲右孩子if(rear%2=1)front+;/出队cinch;returnroot;例如，对图69所示的二叉树，建立的二叉链表如图610所示。对图69(a)所示的二叉树，要用算法建成图610

19、所示的二叉树链表，从键盘输入的数据应为：AB,C,D#其中#为输入结束，为回车符。6.3遍历二叉树所谓遍历二叉树，就是遵从某种次序，访问二叉树中的所有结点，使得每个结点仅被访问一次。这里提到的“访问”是指对结点施行某种操作，操作可以是输出结点信息，修改结点的数据值等，但要求这种访问不破坏它原来的数据结构。在本书中，我们规定访问是输出结点信息data，且以二叉链表作为二叉树的存贮结构。由于二叉树是一种非线性结构，每个结点可能有一个以上的直接后继，因此，必须规定遍历的规则,并按此规则遍历二叉树,最后得到二叉树所有结点的一个线性序列。令L,R,D分别代表二叉树的左子树、右子树、根结点，则遍历二叉树有

20、6种规则：DLR、DRL、LDR、LRD、RDL、RKD。若规定二叉树中必须先左后右(左右顺序不能颠倒)，则只有DLR、LDR、LRD三种遍历规则。DLR称为前根遍历(或前序遍历、先序遍历、先根遍历)，LDR称为中根遍历(或中序遍历)，LRD称为后根遍历(或后序遍历)。6.3.1前根遍历前根遍历所谓前根遍历，就是根结点最先遍历，其次左子树，最后右子树。1递归遍历递归遍历前根遍历二叉树的递归遍历算法描述为：若二叉树为空，则算法结束;否则（1）输出根结点；）输出根结点；（2）前根遍历左子树）前根遍历左子树;（3）前根遍历右子树）前根遍历右子树;算法如下:voidpreorder(bitree*ro

21、ot)bitree*p;p=root;if(p!=NULL)coutdatalchild);preorder(prchild);2非递归遍历非递归遍历利用一个一维数组作为栈，来存储二叉链表中结点，算法思想为：从二叉树根结点开始，沿左子树一直走到末端(左孩子为空)为止，在走的过程中，访问所遇结点，并依次把所遇结点进栈，当左子树为空时，从栈顶退出某结点，并将指针指向该结点的右孩子。如此重复，直到栈为空或指针为空止。算法如下：voidpreorder1(bitree*root)bitree*p,*s100;inttop=0;/top为栈顶指针p=root;while(p!=NULL)|(top0)w

22、hile(p!=NULL)coutdatalchild;p=stop;p=prchild;6.3.2中根遍历中根遍历所谓中根遍历，就是根在中间，先左子树，然后根结点，最后右子树。1递归遍历递归遍历中根遍历二叉树的递归遍历算法描述为：若二叉树为空，则算法结束；否则中根遍历左子树中根遍历左子树;输出根结点输出根结点;中根遍历右子树。中根遍历右子树。算法如下:voidinorder(biteee*root)bitree*p;p=root;if(p!=NULL)inorder(plchild);coutdatarchild);2非递归遍历非递归遍历同样利用一个一维数组作栈，来存贮二叉链表中结点，算法思

23、想为：从二叉树根结点开始，沿左子树一直走到末端(左孩子为空)为止，在走的过程中，把依次遇到的结点进栈,待左子树为空时,从栈中退出结点并访问,然后再转向它的右子树。如此重复，直到栈空或指针为空止。算法如下:voidinorder1(bitree*root)bitree*p,*s100;/s为一个栈，top为栈顶指针inttop=0;p=root;while(p!=NULL)|(top0)while(p!=NULL)s+top=p;p=plchild;p=stop;coutdatarchild;6.3.3 后根遍历后根遍历所谓后根遍历，就是根在最后，即先左子树，然后右子树，最后根结点。1递归遍历递

24、归遍历后根遍历二叉树的递归遍历算法描述为：若二叉树为空，则算法结束;否则（1）后根遍历左子树）后根遍历左子树:（2）后根遍历历子树）后根遍历历子树;（3）访问根结点。）访问根结点。算法如下:voidpostorder(bitree*root)bitree*p;p=root;if(p!=NULL)postorder(plchild);postorder(prchild);coutdatalchild;if(top0)b=s2top;p=s1top;if(b=0)s1top=p;s2top+=1;/第二次进栈标志为0p=prchild;elsecoutdata0);例如，可以利用上面介绍的遍历算法

25、，写出如图611所示二叉树的三种遍历序列为：先序遍历序列：ABDGCEFH中序遍历序列：BGDAECFH后序遍历序列：GDBEHFCA另外，在编译原理中，有用二叉树来表示一个算术表达式的情形。在一棵二叉树中，若用操作数代表树叶，运算符代表非叶子结点，则这样的树可以代表一个算术表达式。若按前序、中序、后序对该二叉树进行遍历，则得到的遍历序列分别称为前缀表达式(或称波兰式)、中缀表达式、后缀表达式(递波兰式)。具体参见图612。图612所对应的前缀表达式：*abc。图612所对应的中缀表达式：a*bc。图612所对应的后缀表达式：ab*c。二叉树所对应的遍历序列可以通过递归算法得到，也可以通过非递

26、归算法得到。但有时要求直接写出序列，故我们可以用图613所示得到图612的遍历序列。从二叉树的三种递归遍历算法可以知道，三种遍历算法不同之处在于访问根结点和遍历左、右子树的顺序不同，若递归算法中去掉与递归无关的语句访问根结点，则三个遍历算法完全相同。于是对于二叉树的遍历，可以看成是从根结点出发，往左子树走，若左子树为空，返回，再进入右子树，右子树访问完后，再返回根结点。这样一来每个结点都被访问三次，若将按顺序第一次访问的结点排列起来，则得到该二叉树的先序序列，第二次访问的结点排列起来，则得到该二叉树的中序序列，第三次访问的结点排列起来，则得到该二叉树的后序序列。对于图613中，第一次访问到的结

27、点用表示,第二次访问到的结点用表示,第三次访问的结点用表示,按虚线顺序将所有排列,则得到先序序列为*abc,将所有排列起来则得到中序序列为a*bc,将所有排列起来则得到后序序列ab*c。6.3.4遍历算法应用举例例65由二叉树的前序序列和中序序列建立该二叉树分析：若二叉树的任意两个结点的值都不相同，则二叉树的前序序列和中序序列能唯一确定一棵二叉树。另外，由前序序列和中序序列的定义可知，前序序列中第一个结点必为根结点，而在中序序列中，根结点刚好是左、右子树的分界点，因此，可按如下方法建立二叉树：1.用前序序列的第一个结点作为根结点;2.在中序序列中查找根结点的位置，并以此为界将中序序列划分为左、

28、右两个序列(左、右子树);3.根据左、右子树的中序序列中的结点个数，将前序序列去掉根结点后的序列划分为左、右两个序列，它们分别是左、右子树的前序序列;4.对左、右子树的前序序列和中序序列递归地实施同样方法，直到所得左、右子树为空。假设前序序列为ABDGHCEFI，中序序列为GDHBAECIF，则得到的二叉树如下页所示1。A为根结点ABDGHCEFIGDHBAECIFBDGHCEFIA2.B为左子树的根结点BDGHGDHBCEFIDHGBA3.D为左子树的左子树的根结点4。C为右子树的根结点5。F为右子树的右子树的根结点CEFIECIF例66按层次遍历一棵二叉树对于一棵二叉树，若规定遍历顺序为从

29、上到下(上层遍历完才进入下层)，从左到右(同一层从左到右进行，这样的遍历称为按层次遍历：例65的树的层次遍历序列为：ABCDEFGHI。下面用一个一维数组来模拟队列，实现二叉树的层次遍历。Voidlorder(bitree*t)bitree*qmaxsize,*p;/maxsize为最大容量intf,r;/f,r类似于头尾指针q1=t;f=r=1;while(f=r)p=qf;f+;/出队coutdata;if(plchild!=NULL)r+;qr=p1child;/入队if(prchild!=NULL)r+;qr=prchild;/入队6.4线索二叉树线索二叉树6.4.1线索的概念通过前面

30、介绍的二叉树可知，遍历二叉树实际上就是将树中所有结点排成一个线性序列(即非线性结构线性化)，在这样的线性序列中，很容易求得某个结点在某种遍历下的直接前驱和后继。然而，有时我们希望不进行遍历就能快速找到某个结点在某种遍历下的直接前驱和后继，这样，就应该把每个结点的直接前驱和直接后继记录下来。为了做到这一点，可以在原来的二叉链表结点中，再增加两个指针域，一个指向前驱，一个指向后继，但这样做将会浪费大量存贮单元，存贮空间的利用率相当低(一个结点中有4个指针，1个指左孩子，1个指右孩子，1个指前驱，1个指后继)，而原来的左、右孩子域有许多空指针又没有利用起来。为了不浪费存存贮空间，我们利用原有的孩子指

31、针为空时来存放直接前驱和后继，这样的指针称为“线索”，加线索的过程称为线索化，加了线索的二叉树，称为线索二叉树，对应的二叉链表称为线索二叉链表。在线索二叉树中，由于有了线索，无需遍历二叉树就可以得到任一结点在某种遍历下的直接前驱和后继。但是，我们怎样来区分孩子指针域中存放的是左、右孩子信息还是直接前驱或直接后继信息呢?为此，在二叉链表结点中，还必须增加两个标志域ltag、rtag。ltag和rtag定义如下：0lchild域指向结点的左孩子ltag=1lchild域指向结点在某种遍历下的直接前驱0rchild域指向结点的右孩子rtag=1rchild域指向结点在某种遍历下的直接后继这样，二叉链

32、表中每个结点还是有5个域，但其中只有2个指针，较原来的4个指针要方便。增加线索后的二叉链表结点结构可描述如下：2线索的分类线索的分类另外，根据遍历的不同要求，线索二叉树可以分为：（1）前序前驱线索二叉树）前序前驱线索二叉树(只需画出前驱只需画出前驱)（2）前序后继线索二叉树）前序后继线索二叉树(只需画出后继只需画出后继)（3）前序线索二叉树）前序线索二叉树(前驱和后继都要标出前驱和后继都要标出)（4）中序前驱线索二叉树）中序前驱线索二叉树(只需画出前驱只需画出前驱)（5）中序后继线索二叉树）中序后继线索二叉树(只需画出中序后继只需画出中序后继)（6）中序线索二叉树）中序线索二叉树(中序前驱和后

33、继都要标出中序前驱和后继都要标出)（7）后序前驱线索二叉树）后序前驱线索二叉树(只需画出后序前驱只需画出后序前驱)（8）后序后继线索二叉树）后序后继线索二叉树(中需画出后序后驱中需画出后序后驱)（9）后序线索二叉树(后前驱和后继都要标出)6.4.2线索的描述线索的描述1结点数据类型描述结点数据类型描述structHbitreeelemtypedata;intltag,rtag;/左、右标志域Hbitree*lchild,*rchild;2线索的画法线索的画法在二叉树或二叉链表中，若左孩子为空，则画出它的直接前驱，右孩子为空时，则画出它的直接后继，左右孩子不为空时，不需画前驱和后继。这样就得到了

34、线索二叉树或线索二叉链表。前序序列为：ABCD中序序列为：BADC后序序列为：BDCA6.4.3 线索的算法实现线索的算法实现在此，仅介绍中序线索二叉树的算法实现，设为P为当前结点，pre为p的前驱结点，算法描述如下：voidinth(Hbitree*p)/将P所指二叉树中序线索化，调用该函数之前，pre为Null，而树中所有结点的ltag和rtag都为0。if(p!=NULL)inth(plchild);左子树线索化if(plchild=NULLl)pltag=1;if(prchild=NULL)prtag;if(pre!=NULL)if(prertag=1)prerchild=p;if(p

35、ltag=1)plchild=pre;pre=p;inth(prchild);/右子树线索化6.4.4 线索二叉树上的运算线索二叉树上的运算1线索二叉树上的查找线索二叉树上的查找（1）查找指定结点在中序线索二叉树中的的直接后继）查找指定结点在中序线索二叉树中的的直接后继若所找结点右标志rtag=1，则右孩子域指向中序后继，否则，中序后继应为遍历右子树时的第一个访问结点,即右子树中最左下的结点（参见图619）。从图619中可知，x的后继为xk。（2）查查找找指指定定结结点点在在中中序序线线索索二二叉叉树树中中的的的的直直接接前前驱驱若所找结点左标志ltag=1，则左孩子域指向中序前驱，否则，中序

36、前驱应为遍历左子树时的最后一个访问结点，即左子树中最右下的结点（参见图620）。从图620中可知，x的前驱为xk。(3) 查找指定点在前序线索二叉树中的直接后继查找指定点在前序线索二叉树中的直接后继前序后继的查找比较方便，若无左孩子，右链为后继，否则左孩子为后继。(4) 查找指定结点在后序线索二叉树中的直接前驱查找指定结点在后序线索二叉树中的直接前驱后序前驱的查找也比较方便，若左孩子为空，左链指前驱，否则，若右子树为空，左孩子指前驱，否则右孩子为前驱。求后序后继和前序前驱都比较麻烦，在此不再作进一步介绍。2线索二叉树上的遍历遍历某种次序的线索二叉树，只要从该次序下的开始结点出发，反复找到结点在

37、该次序下的后继，直到后继为空。这对于中序线索和前序线索二叉树很方便，但对于后序线索二叉树较麻烦(因求后序后继较麻烦)。故后序线索对于遍历没有什么意义。(1)前序遍历线索二叉树算法前序遍历线索二叉树算法voidpreorder2(Hbitree*t)Hbitree*p;p=t;/找到开始结点while(p!=NULL)coutdata;p=preordernext(p);/调查函数找前序后继(2)中序遍历线索二叉树算法中序遍历线索二叉树算法voidinorder2(Hbitree*t)Hbitree*p;p=t;if(p!=NULL)while(pltag=0)p=plchild;/找开始结点w

38、hile(p!=NULL)coutdata;p=inordernext(p);/调用函数找中序后继从上面算法可知，线索二叉树上的遍历较一般二叉树要方便得多。但是这种方便是以增加线索为代价的，增加线索本身要花费大量时间。所以二叉树是以二链表表示，还是以线索二叉链表示，可根据具体问题而定。3线索二叉树的扦入和删除线索二叉树的扦入和删除线索二树上的查找、遍历都较一般二叉树方便，但线索二叉树也存在其缺点，就扦入和删除运算而言，线索二叉树比一般二叉树的时间花费大，因为除修改指针外，还要修改相应线索。线索二叉树的扦入和删除较麻烦，因此本书不再介绍算法.树和森林.树的存储结构1双亲表示双亲表示它是以一组连续

39、的存储单元来存放树中的结点，每个结点有两个域：一个是data域，存放结点信息，另一个是parent域，用来存放双亲的位置(指针)。该结构的具体描述见图621。2孩子表示法将一个结点所有孩子链接成一个单链表形，而树中有若干个结点，故有若干个单链表，每个单链表有一个表头结点，所有表头结点用一个数组来描述，具体描述参见图6223双亲孩子表示法双亲孩子表示法将第1、2两种方法结合起来，则得到双亲孩子表示法，具体参见图623。4 。孩子兄弟表示法。孩子兄弟表示法类似于二叉链表，但第一根链指向第一个孩子，第二根链指向下一个兄弟。将图621(a)的树用孩子兄弟表示法表示，见图624。6.5.2 树、森林和二

40、叉树的转换树、森林和二叉树的转换1树转换成二叉树树转换成二叉树可以分为三步：（1）连线指相邻兄弟之间连线。（2）抹线指抹掉双亲与除左孩子外其它孩子之间的连线。（3）旋转只需将树作适当的旋转。具体实现过程见图625。2森林转换成二叉树森林转换成二叉树（1）将森林中每一棵树分别转换成二叉树这在刚才的树转换成二叉树中已经介绍过。（2）合并）合并使第n棵树接入到第n1棵的右边并成为它的右子树，第n1棵二叉树接入到第n2棵的右边并成为它的右子树，第2棵二叉树接入到第1棵的右边并成为它的右子树，直到最后剩下一棵二叉树为止。3二叉树还原成树或森林二叉树还原成树或森林(1)右链断开将二叉树的根结点的右链及右链

41、的右链等全部断开，得到若干棵无右子树的二叉树。具体操作见图627(b)。（2）二叉树还原成树将（1）中得到的每一棵二叉树都还原成树（与树转换成二叉树的步骤刚好相反）。具体操作步骤见图627(c)。6.5.3树和森林的遍历在树和森林中，一个结点可能有两棵以上的子树，所以不宜讨论它们的中序遍历，即树和森林只有先序遍历和后序遍历。1先序遍历先序遍历（1）树的先序遍历）树的先序遍历若树非空，则先访问根结点，然后依次先序遍历各子树。（2）森林的先序遍历若森林非空，则先访问森林中第一棵树的根结点，再先序遍历第一棵树各子树，接着先序遍历第二棵树、第三棵树、直到最后一棵树。2后序遍历后序遍历（1）树的后序遍历

42、）树的后序遍历若树非空，则依次后序遍历各子树，最后访问根结点。（2）森林的后序遍历）森林的后序遍历按顺序后序遍历森林中的每一棵树。另外，请注意，树和森林的先序遍历等价于它转换成的二叉树的先序遍历，树和森林的后序遍历等价于它转换成的二叉树的中序遍历。6.6哈夫曼树6.6.1基本术语基本术语1路径和路径长度路径和路径长度在一棵树中，从一个结点往下可以达到的孩子或子孙结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L1。2结点的权及带权路径长度结点的权及带权路径长度若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点

43、的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。3树的带权路径长度树的带权路径长度树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为wpl=，其中n为叶子结点数目，wi为第i个叶子结点的权值，li为第i个叶子结点的路径长度。6.6.2哈夫曼树构造1哈夫曼树的定义哈夫曼树的定义在一棵二叉树中，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffmantree)。例如，给定叶子结点的权分别为1,3,5,7，则可以得到如图628所示的不同二叉树。从图628可知，图628(b)的长度最短，图628(c)为较差情形，当然读者还可以自已构造出具有不同的w

44、pl情形来。2哈夫曼树的构造哈夫曼树的构造假设有n个权值，则构造出的哈夫曼树有n个叶子结点。n个权值分别设为w1,w2,wn,则哈夫曼树的构造规则为：(1)将w1,w2,wn看成是有n棵树的森林(每棵树仅有一个结点)；(2)在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；(3)从森林中删除选取的两棵树，并将新树加入森林；(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为我们所求得的哈夫曼树。下面给出哈夫曼树的构造过程，假设给定的叶子结点的权分别为1,5,7,3，则构造哈夫曼树过程如图629所示。从图629可知，n个

45、权值构造哈夫曼树需n1次合并，每次合并，森林中的树数目减1，最后森林中只剩下一棵树，即为我们求得的哈夫曼树。6.6.3哈夫曼树的应用1哈夫曼编码哈夫曼编码通信中，可以采用0,1的不同排列来表示不同的字符，称为二进制编码。而哈夫曼树在数据编码中的应用，是数据的最小冗余编码问题，它是数据压缩学的基础。若每个字符出现的频率相同，则可以采用等长的二进制编码，若频率不同，则可以采用不等长的二进编码，频率较大的采用位数较少的编码，频率较小的字符采用位数较多的编码，这样可以使字符的整体编码长度最小，这就是最小冗余编码的问题。而哈夫曼编码就是一种不等长的二进制编码，且哈夫曼树是一种最优二叉树，它的编码也是一种最优编码，在哈夫曼树中，规定往左编码为0，往右编码为1，则得到叶子结点编码为从根结点到叶子结点中所有路径中0和1的顺序排列。例如，给定权1,5,7,3，得到的哈夫曼树及编码见图632(假定权值就代表该字符名字)。2哈夫曼译码哈夫曼译码在通信中，若将字符用哈夫曼编码形式发送出去，对方接收到编码后，将编码还原成字符的过程，称为哈夫曼译码。