六章树和二叉树.PPT

第六章树和二叉树,6.1 树的定义和基本术语6.2 二叉树6.3 遍历二叉树和线索二叉树6.4 树和森林6.5 赫夫曼树及其应用,1.树(Tree)：是n(n0)个结点的有限集。在任意一棵非空树中(1)有且只有一个称为根(Root)的结点。(2)其余的结点被分为m(m0)个互不相交的有限集，其中每个集合本身又是一棵树，称为根(Root)结点的子树(Sub_Tree)。,6.1 树的定义和基本术语,6.1.1 基本术语,树的定义本身是递归的。递归定义和递归操作在树和二叉树中应用是比较广泛的，应注意领会递归的实质。,2.树的表示法：有图示法、集合表示法、广义表表示法和缩进表示法，见图6.1。,(A(B(E,F(L),G),C(H,I(M,N),D(J,K)(b)广义表表示法,图4.1 树的几种表示法,3.结点的分类：从计算机的角度来分，可以分为终端结点和非终端结点；以树的特征来分，可以分根结点、分支结点和叶子结点；用族谱的关系来分，可以分为双亲结点和孩子结点、祖先结点和子孙结点、兄弟结点和堂兄弟结点。4.度：分为结点的度和树的度两种。结点的度是指与该结点相连接的孩子结点的数目。树的度是指该棵树中所有结点的度中的最大值。5.深度：树是一种分层结构，根结点作为第一层。结点的层次(或称深度)就是指从根结点开始的层次数。树的深度(或层数)是指该树中所有结点的层次中的最大值。,用图示法表示的二叉树中，边的数目(或称分支数，用e表示)恰好比结点数目(用n表示)少一个，即e=n-1。这是树状结构中最重要的一个结论。,6.有序树与无序树：如果将树中结点的各棵子树看成是从左到右有次序的(即不能互换),则称该树为有序树，否则称为无序树。7有向树与无向树：如果树的每个分支都是从一个结点到另一个结点有方向的，则称该树为有向树，否则称为无向树。8.n元树：树的度为n的有向树。9.位置树：是一棵有向树。如果树中结点的每个孩子结点位置是不能被改变的(改变则不是原树)，则称该树为位置树。如某结点可能没有第一个孩子结点，但却可能会有第二个、第三个孩子结点。10.m叉树：是树的度为m的有向位置树，即m元位置树。11.森林：是m(m0)棵互不相交的树的集合。对于树中的每个结点而言，其子树的集合就是森林。因此，森林和树是密切相关的。森林中的树也可以有顺序关系和位置关系。,树状结构也是用于存储数据的，我们也要对其中的数据进行加工处理。总体上，树的基本操作有如下几种：InitTree(T)构造一棵空树T。ClearTree(T)将已经存在的树T清空。TreeEmpty(T)判断树T是否为空树。TreeDepth(T)计算树T的深度。InsertChild(T,p,i,c)插入子树c为树T中p指向结点的第i棵子树。DeleteChild(T,p,i)删除树T中p所指结点的第i棵子树。TraverseTree(T)按某种次序对树T中的所有结点进行访问，每个结点仅访问一次。,6.1.2 树的基本操作,二叉树(Binary Tree)是一种特殊的有向树，也称二元位置树。它的特点是每个结点至多有两棵子树，即二叉树中的每个结点至多有两个孩子结点，且每个孩子结点都有各自的位置关系。或者说，二叉树的子树有左右之分，其次序不能任意颠倒。给二叉树下个更加确切的定义，就是：二叉树或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。,6.2 二叉树,6.2.1 二叉树的定义,可以看出，二叉树的定义是递归的，前面提到的树的定义也是递归的。这说明树状结构在处理数据时很多操作是可以通过递归来完成的。,图6.2 二叉树的五种基本形态,根据二叉树的定义，可以总结出二叉树有如图6.2所示的五种形态：,【例6.1】列举出只有两个结点、三个结点的二叉树的所 有形态,1.只有两个结点的二叉树的形态有两种，如图6.3所示,2.只有三个结点的二叉树的形态有五种，如图6.4所示,6.2.2 二叉树的性质与结论,性质1：在二叉树的第i(i1)层上至多有2i-1个结点。(该性质证明利用归纳法很容易实现，留给读者自己去思考),性质2：深度为k(k1)的二叉树上至多有2k-1个结点。(该性质证明直接利用性质1即可，留给读者自己去思考),性质3：任意一棵二叉树中，叶子结点的数目(用n0表示)总比度为2的结点的数目(用n2表示)多一个，即n0=n2+1。,证明：设结点总数为n，度为1的结点数目为n1，则有 n=n0+n1+n2(6-1)由于二叉树中除根之外的每个结点都带有一个向上的分支，设分支总数为e，则e=n-1(6-2)由于这些分支不是度为1的结点射出的分支，就是度为2的结点射出的分支,则e=1n1+2n2(6-3)由(6-2)式和(6-3)式，得n-1=n1+2n2(6-4)由(6-1)式和(6-4)式，得1=n0-n2 即 n0=n2+1 证毕。,两种特殊形态的二叉树,满二叉树:除叶子结点外的任何结点均有两个孩子结点，且所有的叶子结点都在同一层上的二叉树。特点是每一层上的结点数都是最大的。,完全二叉树:除去最底层结点后的二叉树是一棵满二叉树，且最底层结点均靠左对齐的二叉树。在这里，靠左对齐的含义是左边是满的，即没有空隙再放入任何一个结点。,如图6.5(a)是一棵深度为4的满二叉树，而图6.5(b)是一棵深度为4的完全二叉树。实质上，满二叉树是完全二叉树的一个特例,证明：设具有n个结点的完全二叉树的深度为k，则由性质2可知2k-1-1n2k-1则 2k-1n2k 取以2为底的对数，得 k-1log2nk log2n处于两个连续的整数k-1和k之间 k-1=log2n即 k=log2n+1 证毕。,性质4：具有n个结点的完全二叉树的深度为log2n+1。,性质5：对有n个结点的完全二叉树中的任一结点i(1in)，有(1)其双亲结点编号为i/2(1in)。(2)其左孩子结点的编号为2i(1in/2)。(3)其右孩子结点的编号为2i+1(1i(n-1)/2),证明：设树中分支数为e，则根据树的定义可知：e=n-1。若n为偶数，则分支数e为奇数，根据完全二叉树的定义可知，在完全二叉树中仅有一个度为1的结点。同理，若n为奇数时，则分支数e为偶数，所以在完全二叉树中没有度为1的结点。证毕。,性质6：当结点个数n为偶数时，完全二叉树中有且仅有一个度为1的结点；当结点个数n为奇数时，完全二叉树中没有度为1的结点,证明：(1)当n为偶数时，由性质6可知：完全二叉树中有一个度为1的结点，即 n1=1,由性质3可知，n0=n2+1，即 n0=n2+n1(6-5)又结点总数为 n=n0+n1+n2(6-6)由(6-5)和(6-6)式，得 n0=n2+n1=n/2=n/2 即，当n为偶数时，编号大于n/2的结点均为叶子结点。(2)当n为奇数时，由性质6可知：完全二叉树中没有度为1的结点，即n1=0,由性质3可知，n0=n2+1(6-7)又结点总数为 n=n0+n1+n2，即 n=n0+n2(6-8)由(6-7)式和(6-8)式，得n=2n2+1 即 n1+n2=(n-1)/2=n/2 所以，当n为奇数时，编号大于n/2的结点均为叶子结点。,性质7：在完全二叉树中编号大于n/2的结点均为叶子结点。,【例6.2】已知一棵完全二叉树中有234个结点，问(1)树的高度是多少？(2)第7层和第8层上各有多少个结点？(3)树中有多少个叶子结点？多少个度为2的结点？多少个度为1的结点？,注意:一般二叉树的性质可用于完全二叉树；反之，完全二叉树的性质和结论是不能用于一般二叉树中的。,解:(1)由性质4可知该完全二叉树的高度(k)为：k=log2234+1=log227+1=8 即该二叉树的高度为8层。(2)由性质1可知第7层上的结点数为：27-1=26=64(个)。由性质2可知第8层上的结点数为：234-(27-1)=107(个)。(3)由性质7可知树中叶子结点个数为：234-234/2=117(个)。由性质2可知度为2的结点个数为：117-1=116(个)。由性质6可知度为1的结点个数为：1(个)。,6.2.3 二叉树的存储结构6.2.3.1 二叉树的顺序存储结构将二叉树上的结点值按从上至下、从左至右的顺序存储到一个线性结构(常为数组)中,数组中的下标为0的单元可用于存放二叉树中结点的个数或二叉树的深度,虚结点可以用一个特殊的标志来识别。,图6.6,void leveltree(SqBitTree bt)/*按满二叉树输出*/int i=1,j;while(i=bt0)/*按层扫描*/for(j=i;j2*i;j+)/*扫描第i层结点*/if(btj=VirNode)printf(*);/*若是虚结点，则输出一个“*”号*/else printf(%d,btj);printf(n);i=2*i;/*跳到下一层*/,【例6.3】按层输出二叉树中的所有结点的值。,void exchangetree(SqBitTree bt)/*该二叉树应添加若干虚结点变为满二叉树*/int k=2,i,j;TelemType t;/*第1层只一个结点，所以从第二层开始进行*/while(k=bt0)for(i=k,j=2*k-1;ij;i+,j-)/*同一层结点值逆置即可完成交换*/t=bti;bti=btj;btj=t;k=2*k;,【例6.4】交换二叉树中所有结点的左右子树。,void searchtree(SqBitTree bt,TElemType x,TElemType*pa,TElemType*lc,TElemType*rc)int i=1,k=1;while(k1)*pa=bti/2;else printf(“该结点为根结点!”);if(2*i=bt0)*lc=bt2*i;else printf(“该结点为叶子结点!”);if(2*i+1=bt0)*rc=bt2*i+1;/*左右孩子可能为虚结点*/break;/*找到，处理之后结束*/else k=2*k;,【例6.5】找出值为x的结点的双亲结点和左右孩子结点的值。,6.2.3.2 二叉树的链式存储结构以链表的形式存储二叉树中的结点及其相互之间的关系,图6.7 二叉树的各种链式存储结构,二叉链表的存储类型说明typedef int TElemType;typedef struct BitNode TElemType data;struct BitNode*lchild,*rchild;BitNode,*BitTree;有了这个类型定义，就可以用它来定义二叉链表根结点的指针变量，如同线性链表中用头指针标识整个链表一样，整个二叉链表就是由这个根结点的指针来识别的。比如：BitTree bt;在此，bt就是指向二叉链表的根结点的指针变量，用以标识整个二叉链表。,性质8：具有n个结点的二叉链表中一定有n+1个空链域。,2.二叉树的基本操作CreateBiTree(bt)建立二叉树；PreOrderTraverse(bt)先序遍历二叉树；InOrderTraverse(bt)中序遍历二叉树；PostOrderTraverse(bt)后序遍历二叉树；SearchBiTree(bt,x,p)查找二叉树值为x的结点，带回该结点的指针p；InsertBiTree(bt,p,x)在p指向的结点位置插入一个值为x的结点；DelBiTree(bt,p)删除p指向的结点；,6.3 遍历二叉树和线索二叉树,6.3.1 遍历二叉树依次访问二叉树中的各个结点，而且每个结点仅被访问一次。,数据元素之间的关系是一种一对多的关系，很难从头至尾一遍扫描完,先序遍历(D L R):访问根结点，按先序遍历左子树，按先序遍历右子树。中序遍历(L D R):按中序遍历左子树，访问根结点，按中序遍历右子树。后序遍历(L R D):按后序遍历左子树，按后序遍历右子树，访问根结点。二叉树为空时，执行空操作，即空二叉树已遍历完。,1.二叉树的遍历过程,实质上在遍历二叉树时，每个结点均经过了三次，由于访问的时机不同，就得到了上述三种遍历算法，如图6.8，其中“”表示空指针。,【例6.6】已知一棵二叉树如图6.9，分别写出其三种遍历顺序。,此三种序列恰为表达式a+b*c-d-e/f的前缀表示(波兰式)、中缀表示和后缀表示(逆波兰式)。,f,f,先序遍历：,中序遍历：,后序遍历：,-,+,a,*,b,-,c,d,/,e,-,+,a,*,b,-,c,d,/,e,+,a,*,b,-,c,d,/,e,f,-,【例6.7】已知一棵二叉树的先序序列和中序序列分别为：KAFGIBEDHJC和AGFKEDBHJIC，试画出这棵二叉树的形状。,分析：先序序列中的第一个一定是(子)树的根结点，而中序序列中左子树遍历完成才会访问这个根结点，所以在中序序列中，排在这个根结点前面的结点一定是其左子树上的结点，排在这个根结点后面的结点一定是其右子树上的结点。如此依次作用于各个子树，就可以画出整个二叉树的树形，而且是惟一的，如图6.10所示。,【例6.8】已知一棵二叉树的后序序列和中序序列分别为FBCGIEJDAH和BFGCHIEADJ，试画出这棵二叉树。,分析：后序序列中的最后一个结点一定是(子)树的根结点，而中序序列中左子树遍历完成才会访问这个根结点，所以在中序序列中，排在这个根结点前面的结点一定是其左子树上的结点，排在这个根结点后面的结点一定是其右子树上的结点。如此依次作用于各个子树，就可以画出整个二叉树的树形，而且是惟一的，如图6.11所示。,【例6.9】已知一棵二叉树的先序序列和后序序列分别为：AB和BA，试画出这棵二叉树的形状。,由先序序列可知A一定是根结点，综合两种序列考虑可知B可能是A的左孩子结点，也可能是A的右孩子结点，所以这棵树的形状是不确定的，如图6.12所示。,性质9：若已知一棵二叉树的先(后)序序列和中序序列，则惟一确定这棵二叉树的形状。该性质的结论根据例6.7和例6.8很容易证实，证明略。,(1)先序遍历二叉树的递归算法void PreOrderTraverse(BitTree bt)if(bt!=NULL)printf(“%d”,bt-data);/*访问根结点*/PreOrderTraverse(bt-lchild);/*遍历左子树*/PreOrderTraverse(bt-rchild);/*遍历右子树*/,2.遍历二叉树的递归算法,(3)后序遍历二叉树的递归算法void PostOrderTraverse(BitTree bt)if(bt!=NULL)PostOrderTraverse(bt-lchild);PostOrderTraverse(bt-rchild);printf(%d,bt-data);,(2)中序遍历二叉树的递归算法void InOrderTraverse(BitTree bt)if(bt!=NULL)InOrderTraverse(bt-lchild);printf(%d,bt-data);InOrderTraverse(bt-rchild);,3.二叉树的建立算法,因为在含有n个结点的二叉链表中一定有n+1个空指针域，所以在输出数据时一定要给出n+1个空指针值。对于数值型数据一般以“-1”代替空指针，对于字符型数据一般以空格“”代替空指针。,BitTree CreateBiTree(void)BitTree bt;TelemType x;scanf(%d,/*返回根结点的指针*/,若输入如下数据：124-1-1-1357-1-18-1-16-1-1，则建立的二叉树如图6.13所示，其中-1用来安排空指针。若data域为字符型，则输入如下数据：12435786,也可以建立如图4.13所示的二叉树，其中“”表示空格符，用来安排空指针。需要注意的是n个结点的二叉树中一定有n+1个空指针，所以要输入n+1个“-1”或空格“”。,二叉树递归遍历应用举例【例6.10】统计二叉树中叶子结点的个数。int n=0;/*定义一个全局变量用来存放叶子结点的个数*/void leafcount(BitTree bt)if(bt!=NULL)if(bt-lchild=NULL,【例6.11】交换二叉树中所有结点的左右子树。BitTree exchangetree(BitTree bt)BitTree t;if(bt!=NULL)if(bt-lchild!=NULL|bt-rchild!=NULL)/*将访问换成交换指针的语句*/t=bt-lchild;bt-lchild=bt-rchild;bt-rchild=t;bt-lchild=exchangetree(bt-lchild);bt-rchild=exchangetree(bt-rchild);,【例6.12】求二叉树的高度。int hightree(BitTree bt)int H,H1,H2;if(bt=NULL)H=0;/*树空，则高度为0*/else H1=hightree(bt-lchild);/*否则，分别计算左右子树的高度*/H2=hightree(bt-rchild);H=(H1H2?H1:H2)+1;/*取左右子树高度的最大值再加1(根结点)作为树的高度*/return H;,【例6.13】查找值为x的结点。找到带回该结点的指针，否则带回空指针。int find=0;/*设置查找标记：0表示未找到，1表示找到*/void searchtree(BitTree bt,TElemType x,BitTree*p)if(bt!=NULL,【例6.14】删除值为x的结点，使得其左右子树的安排仍然满足原来的中序遍历序列。,分析：为了保持中序遍历序列不变，对于找到的结点p可以分为四种情况考虑：若结点p为叶子结点，则只需将该结点的双亲结点(f)的左指针或右指针置为空即可；若结点p的左子树为空，则只需将该结点(p)的双亲结点(f)的左指针或右指针指向该结点(p)的右孩子结点即可；若结点p的左子树非空，则只需找到结点p的左子树中最右下的结点s(s的右指针必为空)，将该结点(s)的左子树接到该结点(s)的双亲结点(q)上，再用该结点(s)中的数据替换结点(p)中的数据即可；若结点p为根结点(bt)且该结点左子树为空，则只需将根结点的指针(bt)移到结点p的右子树上即可，如图6.14。为此需重新设计查找算法如下：,int find=0;searchtree(BitTree bt,TElemType x,BitTree*p,BitTree*f)if(bt!=NULL,删除值为x结点的算法如下：void deltree(BitTree bt,TElemType x)BitTree p,f,q,s,;p=f=NULL;searchtree(bt,x,二叉树的非递归遍历1.二叉树的先序非递归遍历算法,先将根结点的指针进栈，算法如下：PreOrderBiTree(BitTree T)stack S;BitTree p;InitStack(S);/*初始化一个栈*/push(S,T);/*根结点指针进栈*/while(!EmptyStack(S)/*栈为空时算法结束*/p=pop(S);/*弹栈，p指向(子树)根结点*/while(p)printf(%d,p-data);/*访问根结点*/if(p-rchild)push(S,p-rchild);/*非空的右指针进栈*/p=p-lchild;/*沿着左指针访问，直到左指针为空*/,2.二叉树的中序非递归遍历算法InOrderBitree(BitTree T)stack S;BitTree p;Initstack(S);/*初始化一个栈*/p=T;/*p指向根结点*/while(p|!EmptyStack(S)/*当p为空且栈为空时算法结束*/while(p)push(S,p);p=p-lchild;/*沿左指针走，沿途经过的(子树)根结点指针进栈*/p=pop(S);printf(%d,p-data);/*当左指针为空时弹栈并访问该结点(子树根结点)*/p=p-rchild;/*向右跳一步到右子树上继续进行遍历过程*/,3.二叉树的后序非递归遍历算法 PostOrderBiTree(BitTree T)stack S;BitTree p,q;InitStack(S);p=T;q=NULL;while(p|!EmptyStack(S)if(p!=q)while(p)push(S,p);/*p非空时，压栈*/if(p-lchild)p=p-lchild;/*沿左指针下移，若左指针为空，*/else p=p-rchild;/*则沿右指针下移*/if(EmptyStack(S)break;/*若栈空，则结束*/q=gettop(S);/*取栈顶指针送q，*/if(q-rchild=p)/*若q的右指针为空(p为空时)或指向刚刚访问过的结点*/p=pop(S);/*则弹栈并访问该结点*/printf(%d,p-data);else p=q-rchild;/*否则，沿q的右指针继续遍历访问*/,在此，安排了一个指针(q)指向栈顶元素，目的是观察其右子树是否已经访问过了。若确实已访问过了，则该指针一定是指向刚刚访问过的(子树)根结点(p结点)，即q=p，否则，再对其右子树进行压栈处理，直到右指针为空。然后再取出新的栈顶元素送q，观察其是否被访问过了。若未访问过(q-rchild=p)，则弹栈并访问之，否则，再沿其右指针下移，如此进行，直到所有结点均被访问过为止。,后序遍历的非递归算法也可以类似于先序遍历的非递归算法一样，只是从右子树到左子树再到根结点进行遍历搜索，将沿途经过的结点依次依次进栈，最后再统一出栈完成遍历的过程。这种方法需要栈的空间较大，不太适用,6.3.2 线索二叉树,线索二叉树的定义,遍历二叉树实质上是对一个非线性结构进行的线性化操作，使每个结点(除第一个结点和最后一个结点外)均有惟一的一个直接前驱和直接后继。,但是，二叉树本身并不是线性关系的结构，如果进行线性化的处理，那么在动态的遍历过程中如何保存这种前驱和后继的关系就成为关键所在。为此，对二叉链表作以改进，增加两个标志域来记录这种线性化的信息。其类型定义为：typedef struct BiThrNode TElemType data;int ltag,rtag;/*增加左指针及右指针的信息标志*/struct BiThrNode*lchild,*rchild;BiThrNode,*BiThrTree;,其中 0 lchild指针指向该结点的左孩子结点 ltag=1 lchild指针指向该结点的直接前驱结点 0 rchild指针指向该结点的右孩子结点 rtag=1 rchild指针指向该结点的直接后继结点,这种结构中结点构成为：,以这种结点结构构成的二叉链表作为二叉树的存储结构，就称为线索链表。指向前驱和后继的指针称为线索，加上线索的二叉树称为线索二叉树(Threaded Binary Tree)。对二叉链表以某种次序遍历使之成为线索二叉树的过程称为线索化处理。按先序遍历得到的线索二叉树称为先序线索二叉树，按中序遍历得到的线索二叉树称为中序线索二叉树，按后序遍历得到的线索二叉树称为后序线索二叉树。其中，还可以分出先序(中序、后序)前驱线索二叉树和先序(中序、后序)后继线索二叉树等等。,【例6.15】已知一棵二叉树如图6.15(a)所示，试画出其三种线索二叉树。,(a)已知二 叉树,线索化处理算法,1.先序线索化处理算法BiThrTree pre;/*中序与后序也要定义该变量,用以记录遍历时的前驱结点*/BiThrTree PreOrderThreading(BiThrTree T)BiThrTree Thrt;Thrt=(BiThrTree)malloc(sizeof(BiThrNode);Thrt-ltag=0;Thrt-rtag=1;Thrt-rchild=Thrt;if(!T)Thrt-lchild=Thrt;/*则头结点自身构成一个循环链表*/else/*头结点中的左指针指向根结点*/Thrt-lchild=T;pre=Thrt;/*且记录根结点的前驱结点指针pre*/PreThreading(T);/*对二叉树进行线索化处理*/pre-rchild=Thrt;pre-rtag=1;/*序列中最后一个结点与头结点相互连接*/Thrt-rchild=pre;void PreThreading(BiThrTree p)if(p)if(!p-lchild)p-ltag=1;p-lchild=pre;/*若左指针为空，则安排前驱线索*/else p-ltag=0;if(!pre-rchild)pre-rtag=1;pre-rchild=p;/*若右指针为空，则安排后继线索*/else p-rtag=0;pre=p;/*前驱结点指针*/if(p-ltag=0)PreThreading(p-lchild);/*左子树线索化处理*/PreThreading(p-rchild);/*右子树线索化处理*/,为便于处理，与线性链表类似，可以在线索二叉链表中增加一个头结点Thrt，其左指针指向根结点，右指针可以指向序列中的最后一个结点。,2.中序线索化处理算法BiThrTree InOrderThreading(BiThrTree T)BiThrTree Thrt;Thrt=(BiThrTree)malloc(sizeof(BiThrNode);Thrt-ltag=0;Thrt-rtag=1;Thrt-rchild=Thrt;if(!T)Thrt-lchild=Thrt;else Thrt-lchild=T;pre=Thrt;InThreading(T);pre-rchild=Thrt;pre-rtag=1;Thrt-rchild=pre;void InThreading(BiThrTree p)if(p)pre=p;InThreading(p-lchild);if(!p-lchild)p-ltag=1;p-lchild=pre;else p-ltag=0;if(pre-rchild)pre-rtag=1;pre-rchild=p;else pre-rtag=0;InThreading(p-rchild);,3.后序线索化处理算法BiThrTree PostOrderThreading(BiThrTree T)BiThrTree Thrt;Thrt=(BiThrTree)malloc(sizeof(BiThrNode);Thrt-ltag=0;Thrt-rtag=1;Thrt-rchild=Thrt;if(!T)Thrt-lchild=Thrt;else Thrt-lchild=T;pre=Thrt;PostThreading(T);pre-rchild=Thrt;pre-rtag=1;Thrt-rchild=pre;void PostThreading(BiThrTree p)if(p)PostThreading(p-lchild);PostThreading(p-rchild);if(!p-lchild)p-ltag=1;p-lchild=pre;else p-ltag=0;if(pre-rchild)pre-rtag=1;pre-rchild=p;else pre-rtag=0;pre=p;,【例6.16】编制算法对中序线索二叉树进行中序后继线索遍历。,inorderthread1(BiThrTree Thrt)BiThrTree p=Thrt-lchild;while(p!=Thrt)while(p-ltag=0)p=p-lchild;printf(%d,p-data);while(p-rtag=1,【例6.17】编制算法对中序线索二叉树进行中序前驱线索遍历。,inorderthread2(BiThrTree Thrt)BiThrTree p=Thrt-rchild;while(p!=Thrt)while(p-rtag=0)p=p-rchild;printf(%d,p-data);while(p-ltag=1,6.4 树和森林,实际应用中，很多事物是不能直接用二叉树来描述的，而只能用树和森林来表示。,6.4.1 树的存储结构,1.双亲表示法双亲表示法是用一组连续的空间来存储树上的结点，同时在每个结点上附加一个指示器来指明其双亲结点所在的位置。图6.16展示了一棵树及其双亲表示法的存储结构。,在这种表中，每个结点(除根结点外)有且仅有一个双亲结点，通过parent域很容易查找任何结点的双亲。但是，在查找孩子结点时则需要遍历整个表。为了找孩子结点更方便些，可以采取下面的存储结构。,2.孩子链表表示法,孩子表示法也是用一组连续的空间来存储树上的结点，同时在每个结点上附加一个指针指向由其孩子结点构成的单链表。,这种表示法中，找孩子结点比较容易，只要搜索firstchild指针指向的单链表即可。但找某一结点的双亲结点就比较困难了，需要搜索所有的单链表。为了克服上述两种表示法的弊端，可以将两种表示法综合起来变成如下的形式,3.孩子双亲表示法孩子双亲表示法也是用一组连续的空间来存储树上的结点，同时在每个结点上附加一个提示器来指示其双亲结点的位置，再附加一个指针指向其孩子结点构成的单链表。如图6.18,在这种表示法中，既能很快地找到每个结点的双亲结点，又能很快地找到每个结点的孩子结点。但这是用空间的代价换来的时间效率,以上三种结构都是用顺序表的形式表示的树和森林，这很难转换成二叉树的存储形式，也就不能用二叉树中理论和结构来描述树和森林了。,4.孩子兄弟表示法孩子兄弟表示法是以二叉链表作为存储结构来表示树和森林的一种结构，其中每个结点的两个指针分别指向其第一个孩子结点和下一个兄弟结点。如图6.19,这种结构有利于实现树和森林的各种操作。比如找某个结点的第i个孩子结点，只要先沿着firstchild指针找到第一个孩子结点，然后再沿着该孩子结点的nextsibling指针走i-1步即可。若每个结点增加一个双亲指针域，则可很快找到其双亲结点。此外，孩子兄弟链表实质上就是前述的二叉链表，只是解释不同而已，有关二叉树的大部分操作均可在这种结构上实现。因此，孩子兄弟链表也成为树、森林与二叉树之间的桥梁和纽带。,6.4.2 树、森林与二叉树之间的转换,从结构上来看，树和森林的孩子兄弟链表表示法与二叉链表表示的二叉树没有什么区别，只是在指针指向的结点含义上有所不同。二叉树中的二叉链表存储结构，其左右指针分别指向结点的左孩子结点和右孩子结点，而树和森林的孩子兄弟链表表示法中，其左右指针分别指向结点的第一个孩子结点和下一个兄弟结点。,通过孩子兄弟链表做媒介，就可以将一棵树或森林转换成对应的二叉树，反之，也可以将一棵二叉树转换成树或森林。,1.树和森林转换成二叉树,将森林中的每一棵树的根结点看成是同一层的有序排列的兄弟结点。则转换规则为：(1)将树和森林中每个结点的第一个孩子结点转换成二叉树中该结点的左孩子结点；(2)将树和森林中每个结点的右邻兄弟结点转换成二叉树中该结点的右孩子结点。,【例6.18】将图6.20(a)所示的森林转换成对应的二叉树。,(a)例6.18的森林(b)森林转换成二叉树 图6.20,2.二叉树转换成树和森林与上述过程恰好相反，二叉树转换成树和森林的规则为：(1)将二叉树中每个结点的左孩子结点转换成树和森林中该结点的第一个孩子结点；(2)将二叉树中每个结点的右孩子结点转换成树和森林中该结点的右邻兄弟结点。,6.4.3 树和森林的遍历,1.树的遍历,(1)先根遍历：若树非空，则先访问根结点，再依次先根遍历其每一棵子树。(2)后根遍历：若树非空，则先依次后根遍历其每一棵子树，再访问根结点。(3)层次遍历：若树非空，则按从上至下、从左至右的顺序依次访问树中的每一个结点。,先根遍历序列为：ABFGCHLMDEINJK 后根遍历序列为：FGBLMHCDNIJKEA 层次遍历序列为：ABCDEFGHIJKLMN,【例6.19】给出图6.16的树的三种遍历序列。,2.森林的遍历,(1)先序遍历：若森林非空，则可按如下规则进行遍历：访问森林中第一棵树的根结点；先序遍历第一棵树中根结点的子树森林；先序遍历其余的树构成的森林。,(2)后序遍历：若森林非空，则可按如下规则进行遍历：后序遍历第一棵树中根结点的子树森林；访问第一棵树的根结点；后序遍历其余的树构成的森林,【例6.20】给出例6.18中的森林的二种遍历序列。,由上述树和森林的遍历可知，树和森林的遍历没有中序遍历，因为无法确定根在中序序列中的位置。另外，树和森林的先根(先序)遍历等同于对应二叉树的先序遍历，其后根(后序)遍历等同于对应二叉树的中序遍历。,先序列遍历序列为：ABEFCGDHIJLKMNO后序列遍历序列为：EFBGCHDALJKINMO,6.5 哈夫曼树及其应用,哈夫曼(Huffman)树，又称最优树，是一类带权路径长度最短的树,6.5.1 哈夫曼树,1.基本概念,(1)结点之间的路径：从一个结点到另一个结点所经过的结点序列。(2)结点之间的路径长度：结点之间的路径上的分支(边)数。(3)树的路径长度：从根结点到每个结点的路径长度之和。(4)结点的带权路径长度：该结点的权值(w)乘以该结点到根结点 的路径长度(l)。(5)树的带权路径长度：树中所有叶子结点带权路径长度之和，记为WPL=wi*li。(6)哈夫曼树：树的带权路径长度(WPL值)最小的二叉树。,在优化查询和缩小编码中非常有用,【例6.21】以4、8、5为叶子结点上的权值，画出具有这3个叶子结点且无度为1的结点的所有可能的二叉树，并分别计算每棵二叉树的WPL值。,若不考虑同一层上结点权值的排列次序，则这棵二叉树可有如图6.22所示的三种情形，其WPL值分别计算如下：,二叉树(b)的权值最小，由此可知将权值大的结点尽量向上靠，可使WPL值较小。,【例6.22】有100个学生要查询个人的成绩，假设其成绩段分布如下：对如下给出的四种查询过程图(见图6.23)分别计算总的比较次数。,(a)WPL=5*1+15*2+40*3+(30+10)*4=315(b)WPL=40*1+30*2+15*3+(5+10)*4=205(c)WPL=(40+30+10)*2+(5+15)*3=220(d)WPL=(5+15+40)*2+(30+10)*3=240,从中可以看出，对于不同的查询方法，比较的次数可能会有很大的不同，这直接影响到算法的效率。,2.构造哈夫曼树,前面讨论了由于二叉树的构造不同导致其WPL值不尽相同，那么，如何构造一棵最优二叉树呢？哈夫曼先生最早给出了一个带有一般规律的算法，俗称哈夫曼算法，步骤如下：(1)根据给定的n个权值w1,w2,wn构成n棵二叉树的集合F=T1,T2,Tn，其中每棵二叉树Ti中只有一个权值为wi的根结点，其左右子树均为空；(2)在F中选取两棵根结点的权值最小的二叉树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点权值为其左右孩子结点权值之和；(3)在F中删除这两棵子树，同时将新得到的二叉树加入到F中；(4)重复步骤(2)和(3)，直到F中仅剩一棵树为止，这棵二叉树即为所求。,通过哈夫曼树的构造过程可以看出，在哈夫曼树中没有度为1的结点。如果叶子结点个数为n，则哈夫曼树中结点总数为2n-1。,【例6.23】已知一个班级的学生每周科目及课时安排如下表，试构造一个哈夫曼树，并计算其WPL值。,解：构造的哈夫曼树如图6.24所示。WPL=(16+20)*2+(4+8+10+12)*3=166,6.5.2 哈夫曼编码,例如，若需传送的电文为“ABADBBACAD”，它只有四个字符，可用编码长度为2的01串来识别。假设A、B、C、D这四个字符的编码分别为00、01、10和11，则上面的电文可翻译成“00010011010100100011”。,实际上，A、B、C、D的编码分别为0、1、01、10。可以节省时间。上面电文使用这种编码发送为“0101011001010”,解码：两位一取,译码时却无从下手