资源描述
软件技术基础软件技术基础上讲主要内容上讲主要内容树的建立二叉树的遍历u深度优先u广度优先二叉树的广度优先遍历 二叉树的广度优先遍历广度优先遍历又称为按按层次遍历层次遍历，这种遍历方式是先遍历二叉树的第一层结点，然后遍历第二层结点，最后遍历最下层的结点。而对每一层的遍历是按从左至右从左至右的方式进行。二叉树的广度优先遍历 按照广度优先遍历方式，在上层中先被访问的结上层中先被访问的结点点，它的下层孩子也必然先被访问下层孩子也必然先被访问，因此在这种遍历算法的实现时，需要使用一个队列队列。在遍历进行之前先把二叉树的根结点的存储地址根结点的存储地址入队，然后依次从队列中出队结点的存储地址出队结点的存储地址，每出队出队一个结点的存储地址则对该结点进行访问对该结点进行访问，然后依次将该结点的左孩子和右孩子左孩子和右孩子的存储地址入队入队，如此反复，直到队空为止。基本思想基本思想二叉树的广度优先遍历算法bitree*Qmaxsize;void Layer(bitree*p)bitree*s;if(p!=NULL)rear=1;front=0;Qrear=p;/*设置指针类型数组来构成队列设置指针类型数组来构成队列*/*层次遍历二叉树，层次遍历二叉树，p指向二叉树的指向二叉树的根结点根结点*/*队尾指针置初值队尾指针置初值*/*队头指针置初值队头指针置初值*/*根结点入队根结点入队*/二叉树的广度优先遍历算法 while(frontlchild;/遍历左子树遍历左子树 else Pop(S,P);/左子树遍历结束，出栈左子树遍历结束，出栈 printf(%c,P-data);/访问根结点访问根结点 P=P-rchild;/遍历右子树遍历右子树 从遍历序列恢复二叉树利用先序序列确定根节点，在中序序列确定左子树的中序序列和左子树的中序序列。根据左子树的结点的数目在先序序列中确定左子树的先序序列；同样得到右子树的先序序列。如此反复，直到取尽先序序列中的结点时，便得到一棵二叉树。基本过程基本过程先序遍历序列第一个结点第一个结点必定是二叉树的根结点根结点。中序遍历序列已知的根结点根结点将中序序列分割成两个子序列，根结点左面的子序列左面的子序列是左子树的中序序列左子树的中序序列，而在根结点右边的子序列右边的子序列是右子树的中序序列右子树的中序序列。序列的特点序列的特点从遍历序列恢复二叉树实例先序序列为A,B,D,G,C,E,F,H，中序序列为D,G,B,A,E,C,H,FA是二叉树的根结点，再根据A在中序序列中的位置，可知结点DGB在A的左子树上和ECHF在A的右子树上；根据先序序列确定B和C分别是A的左子树和右子树的根，再根据B和C在DGB和ECHF中的位置，可知DG在B的左子树上和B的右子树为空以及C的左子树仅有结点E和C的右子树包含结点HF；遍历序列恢复二叉树算法思想先将先序和中序序列分别存在两个数组perodn和inodn中取先序序列的第一个元素建立整个树的根结点，并利用中序序列确定根结点的左、右子树结点在先序序列中的位置。接着再用先序序列和中序序列分别对左子树和右子树进行构造。datatype preodmaxsize，inodmaxsize;遍历序列恢复二叉树算法 int m;bitree*p;p=malloc(sizeof(bitree);pdata=preodi;m=k;while(inodm!=preodi)m+;if(m=k)plchild=NULL;else plchild=BPI(preod,inod,i+1,i+m-k,k,m-1);if(m=l)prchild=NULL;else prchild=BPI(preod,inod,i+m-k+1,j,m+1,l);return(p);/*构造根结点构造根结点*/*查找根结点在中序查找根结点在中序序序列列中的位置中的位置*/*对左子树进行构造对左子树进行构造*/*对右子树进行构造对右子树进行构造*/datatype preodmaxsize，inodmaxsize;bitree*BPI(datatype preod,datatype inod,int i,int j,int k,int l)/*i,j,k,l分别是要构造二叉树的先序和中序序列数组的起始和终点下标分别是要构造二叉树的先序和中序序列数组的起始和终点下标*/遍历算法的应用-统计二叉树中的叶子结点数int count=0;int countleaf(bitree*p)if(p!=NULL)count=countleaf(plchild);if(plchild=NULL)&(prchild=NULL)count=count+1;count=countleaf(prchild);return count;/*对左子树上的叶对左子树上的叶子结点计数子结点计数*/*对右子树上的叶对右子树上的叶子结点计数子结点计数*/*countleaf */遍历算法的应用-求二叉树深度int l=h=0;int treedepth(bitree*p,int l)if(p!=NULL)l+;if (lh)h=l;h=treedepth(plchild,l);h=treedepth(prchild,l);return h;/*计算左子树的深度计算左子树的深度 */*计算右子树的深度计算右子树的深度 */9.6 线索二叉树线索二叉树是将一个非线性结构进行线性化的操作，使每个结点（除第一个和最后一个）在这些线性序列中有且仅有一个直接前趋和直接后继。线索是指向结点前趋和后继的指针，若结点有左孩子，则lchild指示其左孩子，否则lchild中存储该结点的前趋结点的指针；若结点有右孩子，则rchild指示其右孩子，否则rchild中存储指向该结点的后继结点的指针。线索二叉树及其线索链表的表示线索二叉树及其线索链表的表示标志域：标志域：标志域：标志域：ltagltag =0,=0,lchildlchild为左孩子指针为左孩子指针为左孩子指针为左孩子指针ltagltag=1,=1,lchildlchild为为为为前驱线索前驱线索前驱线索前驱线索rtagrtag=0,=0,rchildrchild为右孩子指针为右孩子指针为右孩子指针为右孩子指针rtagrtag=1,=1,rchildrchild为后继指针为后继指针为后继指针为后继指针中序线索二叉树中序线索二叉树中序遍历序列：中序遍历序列：BDAEC树和二叉树间的转换l任任何何一一棵棵树树都都可可以以转转换换为为一一棵棵二二叉叉树树，同同时时一一棵棵二二叉叉树树也也可可转转换换成成一一棵棵树树，而而且且这这种种转转换换是是具有惟一性的。具有惟一性的。l将一棵树转换为二叉树的方法是：将一棵树转换为二叉树的方法是：(1)在兄弟之间增加一条连线；(2)对每个结点，除了保留与其左孩子的连线外，除去与其它孩子之间的连线；(3)以树的根结点为轴心，将整个树顺时针旋转45度。l从一棵二叉树到树的转换规则是：从一棵二叉树到树的转换规则是：(1)若结点X是双亲Y的左孩子，则把X的右孩子，右孩子的右孩子都与Y用连线相连；(2)去掉原有的双亲到右孩子的连线。树和二叉树间的转换实例二叉树的应用n排序中的应用排序中的应用 二叉排序树n通信编码中的应用通信编码中的应用哈夫曼树及其编码、译码二叉排序树的概念：二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：每个结点都有一个关键字(key)，所有结点的关键字互不相同。左子树(若非空)上所有结点的关键字都小于根结点的关键字。右子树(若非空)上所有结点的关键字都大于根结点的关键字。左子树和右子树也是二叉排序树。二叉排序树几个二叉排序树的例子几个二叉排序树的例子zhaodingchenwangmaxiaduni二叉排序树的数据结构如果对一棵二叉排序树进行LDR遍历，可以按从小到大的顺序，将各结点关键字排列起来。如果对一棵二叉排序树进行RDL遍历，可以按从大到小的顺序，将各结点关键字排列起来。二叉排序树的二叉链表存储结构结点结构描述如下：typedef int keytype;typedef struct keytype key;/关键字项 datatype other;/其它数据项 struct node*lchild,*rchild;/左、右指针域 bstnode;二叉排序树的构造构造一棵二叉排序树，就是从空的二叉排序树开始，逐个结点插入到二叉排序树中。对于一组数据元素 R1,R2,Rn ,可按以下方法来构造二叉排序树：(1)(1)令令令令R R1 1为二叉树的根为二叉树的根为二叉树的根为二叉树的根;(2)(2)若若若若R R2 2RR1 1,令令令令R R2 2为为为为R R1 1左左左左子子子子树树树树的的的的根根根根结结结结点点点点，否否否否则则则则R R2 2为为为为R R1 1右右右右子子子子树树树树的的的的根结点；根结点；根结点；根结点；(3)(3)对对对对R R3 3,RnRn结结结结点点点点也也也也是是是是依依依依次次次次与与与与前前前前面面面面生生生生成成成成的的的的结结结结点点点点比比比比较较较较以以以以确确确确定定定定结结结结点的位置。点的位置。点的位置。点的位置。说明：每次插入的新结点都是当前二叉树的叶子结点 给定的关键字序列不同，二叉排序树的形态则不同 二叉排序树中不存在两个结点的关键字相同的结点例：给定关键字序列10、18、3、8、12、2、7、3，建立二叉排序树。将指针s所指的结点插入到根结点指针为t的二叉排序树中的算法bstnode*INSERTBST(bstnode*t,bstnode*s)/t为二叉排序树的根指针，s为插入的结点指针*/bstnode*f,*p;p=t;while(p!=NULL)f=p;/f指向*p结点双亲 if(skey=pkey)return t;if(skey pkey)p=plchild;else p=prchild;if(t=NULL)return s;/原树为空,返回s作为根指针 if(skeyfkey)flchild=s;else frchild=s;return t;/*INSERTBST*/输入一组数据元素的序列，构造二叉排序树的算法bstnode*CREATBST()/生成二叉排序树 bstnode *t,*s;keytype key,endflag=0;/endflag为结点结束标志 datatype data;t=NULL;/设置二叉排序树的初态为空树 scanf(“%d”,&key);/读入一个结点的关键字 while(key!=endflag)/输入未到结束标志时，执行以下操作 s=malloc(sizeof(bstnode);/申请新结点 slchild=srchild=NULL;/赋初值 skey=key;scanf(“%d”,&data);/读入结点的其它数据项 sother=data;t=INSERTBST(t,s)/将新结点插入树t中 scanf(“%d”,&key)/读入下一个结点的关键字 return t;/CREATBST二叉排序树中的结点删除要求删除一个结点后，仍然保持二叉排序树的有序性。要求删除一个结点后，仍然保持二叉排序树的有序性。u删除的结点由删除的结点由p指出，其双亲结点由指出，其双亲结点由q指出，则指出，则二叉排序树中结点删除分四种情况考虑：二叉排序树中结点删除分四种情况考虑：（1）若p指向叶子结点，只需将其双亲结点指向它的指针清零，再释放它即可；（2 2）若被删除结点）若被删除结点）若被删除结点）若被删除结点*P P仅有右子树，则把结点仅有右子树，则把结点仅有右子树，则把结点仅有右子树，则把结点*P P的右子树的全部挂接在的右子树的全部挂接在的右子树的全部挂接在的右子树的全部挂接在*P P的双亲的双亲的双亲的双亲*q q上，且位置是上，且位置是上，且位置是上，且位置是*P P在其双亲中原来的位置；在其双亲中原来的位置；在其双亲中原来的位置；在其双亲中原来的位置；fpfpp是左孩子是左孩子p是是右孩子右孩子（3 3）若被删除结点）若被删除结点*P P仅有左子树，则把结点仅有左子树，则把结点*P P的的左子树的全部挂接在左子树的全部挂接在P P的双亲上，且位置是的双亲上，且位置是*P P在在其双亲中原来的位置；其双亲中原来的位置；（4 4）若p所指结点的左子树pL和右子树pR均非空，则需要将pL和pR链接到合适的位置上，并且保持二叉排序树的特点，即应使中序遍历该二叉树所得序列的相对位置不变。做法按照中序遍历找*p的左子树中的最大结点（*p的直接前趋*s），以此最大结点的值代替P结点的值，然后删除此最大结点；第二种方法按照中序遍历找*p的右子树中的最小结点（*p的直接后继*s），以此最小结点的值代替P结点的值，然后删除此最小结点。哈夫曼树若树中的两个结点之间存一条路径，则路径的长度路径的长度是指路径所经过的边路径所经过的边(即连接两个结点的线段)的数数目目。树的路径长度树的路径长度是树根到树中每一结点每一结点的路径长度之路径长度之和和。树的带权路径长度树的带权路径长度为树中所有叶子结点叶子结点的带权路径带权路径长度之和长度之和，记作：其中n为树中叶子结点的数目叶子结点的数目，wi为叶子结点结点i的权的权值值，li为叶子结点i到根结点之间的路径长度路径长度。概念计算树的路径长度树的路径长度具有不同路径长度的二叉树具有不同路径长度的二叉树具有不同路径长度的二叉树具有不同路径长度的二叉树(a)PLa)PL=0+1*2+2*4+3=13=0+1*2+2*4+3=13(b)PLb)PL=0+1*2+2*3+3*2=14=0+1*2+2*3+3*2=14叶子结点的权值相同，具有不同带权路径长度的二叉树哈夫曼树的定义在有n个带权叶子结点的所有二叉树中，带权路径长度WPL最小最小的二叉树被称为最优最优二叉树或哈夫曼树二叉树或哈夫曼树。定义定义在结点数目相同的二叉树中，完全二叉树的路径在结点数目相同的二叉树中，完全二叉树的路径长度最短（其他树长度最短（其他树）。）。思考思考哈夫曼树的不惟一性 权值为w1,w2,wn 的n个叶子结点形成的二叉树，可以具有多种形态，其中能被称为哈夫曼树的二叉树并不是惟一的。如下图。(a)WPL=3242527238；(b)WPL=334352738。完全二叉树不一定是哈夫曼树 在叶子数和权值相同的二叉树中，完全二叉树不一定是最优二叉树。如下图。(a)WPL2242527236；(b)WPL2343527135。DAVID A.HUFFMAN David Albert Huffman(August 9,1925 October 7,1999)was a pioneer in the computer science field.HUFFMANA native of Ohio,Huffman earned his B.S.in electrical engineering from Ohio State University at the age of 18 in 1944.He then served in the U.S.Navy as a radar maintenance officer on a destroyer that helped to clear mines in Japanese and Chinese waters after World War II.He subsequently earned his M.S.degree from Ohio State in 1949 and his Ph.D.from MIT in 1953,also in electrical engineering.Huffman discovered the Huffman code while a graduate student at MIT as part of a term paper for Robert Fanos class.哈夫曼树的构造算法(1)根据给定的n个权值w1,w2,wn构成n棵二叉树的集合FT1,T2,Tn,其中Ti中只有一个权值为wi的根结点，左、右子树均为空。(2)在F中选取两棵根结点的权值为最小的树作为左、右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为左、右子树上根结点的权值之和。(3)在F中删除这两个棵权值为最小的树，同时将新得到的二叉树加入F中。(4)重复(2)、(3)直到F中仅剩一棵树为止。这棵树就是哈夫曼树。哈夫曼树的构造实例权值为7,5,2,4的4个叶子结点A、B、C、D、构造哈夫曼树来观察哈夫曼树的构造过程，如下图所示。注：注：一个有n个叶子结点的初始集合，要生成哈夫曼树共要进行n-1次合并次合并，产生n-1个新结点。最终求得的哈夫曼树共有2n-1个结点，并且哈夫曼树中没有度为1的分支结点。我们常称没有度为1的结点的二叉树为严格二叉树。构造哈夫曼树算法中的数据结构 define n /*叶子数目*/define m 2*n-1 /*结点总数*/typedef char datatype;typedef struct float weight;datatype data;int lchild,rchild,parent;hufmtree;hufmtree treem;构造哈夫曼树算法实现HUFFMAN(hufmtree tree)int i,j,p;char ch;float small1,small2,f;for(i=0;im;i+)/*初始化*/treei.parent=0;treei.lchild=0;treei.rchild=0;treei.weight=0.0;treei.data=0;for(i=0;in;i+)/*输入前n个结点的权值*/scanf(“%f”,&f);treei.weight=f;scanf(“%c”,&ch);treei.data=ch;for(i=n;im;i+)/*进行n-1次合并，产生n-1个新结点*/p1=p2=0;small1=small2=Maxval;for(j=0;j=i-1;j+)if(treej.parent=0)if(treej.weightsmall1)small2=small1;small1=treej.weight;p2=p1;p1=j;else if(treej.weightsmall2)small2=treej.weight;p2=j;treep1.parent=i;treep2.parent=i;treei.lchild=p1;treei.rchild=p2;treei.weight=reep1.weight+treep2.weight;/*HUFFMAN*/哈夫曼编码主要用途是实现数据压缩。设给出一段报文：afdcbe.(长度100)字符集合是 a,b,c,d，e，f，对应频度(次数)是 W 40,30,10,10，2，8。若给每个字符以等长编码 a:000 b:001 c:010 d:011 e:100 f:101则编码为000101011010001100长度为 100*3=300 能否降低长度？长度为=?n个叶子结点的最大编码长度不会超过n-1。总编码长度正好等于哈夫曼树的带权路径长度WPL。任一字符的编码都不是另一字符编码的前缀，称为前缀编码。哈夫曼编码是一种前缀编码。译码时不会混淆。哈夫曼编码哈夫曼编码 程序设计程序设计从叶子到根逆向求哈夫曼编码从叶子到根逆向求哈夫曼编码 从叶子从叶子从叶子从叶子treeitreeitreeitreei 出发，利用双亲地址找到双亲结点出发，利用双亲地址找到双亲结点出发，利用双亲地址找到双亲结点出发，利用双亲地址找到双亲结点treeptreeptreeptreep ，再利用，再利用，再利用，再利用treeptreeptreeptreep 的的的的lchildlchildlchildlchild和和和和rchildrchildrchildrchild指针域判断指针域判断指针域判断指针域判断treeitreeitreeitreei 是是是是treeptreeptreeptreep 的左孩子还是右孩子，然后决定分配代码的左孩子还是右孩子，然后决定分配代码的左孩子还是右孩子，然后决定分配代码的左孩子还是右孩子，然后决定分配代码的的的的 0 0 0 0 还是代码还是代码还是代码还是代码 1 1 1 1 ,然后以然后以然后以然后以treeptreeptreeptreep 为出发点继续为出发点继续为出发点继续为出发点继续向上回溯，直到根结点为止。向上回溯，直到根结点为止。向上回溯，直到根结点为止。向上回溯，直到根结点为止。哈夫曼编码的存储结构哈夫曼编码的存储结构哈夫曼编码的存储结构哈夫曼编码的存储结构typedeftypedeftypedeftypedef structstructstructstruct char bitsn;char bitsn;char bitsn;char bitsn;intintintint start;start;start;start;char char char char chchchch;codetypecodetypecodetypecodetype;codetypecodetypecodetypecodetype coden;coden;coden;coden;哈夫曼编码的存储结构哈夫曼编码的存储结构code下下标标bitsstartdata0123003a1102b21101c31111d哈夫曼编码算法哈夫曼编码算法哈夫曼编码算法哈夫曼编码算法(根据已构成的哈夫曼树，求出编码根据已构成的哈夫曼树，求出编码根据已构成的哈夫曼树，求出编码根据已构成的哈夫曼树，求出编码)HUFFMANCODE(codetypeHUFFMANCODE(codetypeHUFFMANCODE(codetypeHUFFMANCODE(codetype code,code,code,code,hufmtreehufmtreehufmtreehufmtree tree)tree)tree)tree)intintintint i,j,c,p;i,j,c,p;i,j,c,p;i,j,c,p;codetypecodetypecodetypecodetype ed;ed;ed;ed;for(i=0;in;i+)for(i=0;in;i+)for(i=0;in;i+)for(i=0;in;i+)cd.startcd.startcd.startcd.start=n;=n;=n;=n;c=i+1;c=i+1;c=i+1;c=i+1;p=treei.parent;p=treei.parent;p=treei.parent;p=treei.parent;while(p!=0)while(p!=0)while(p!=0)while(p!=0)cd.startcd.startcd.startcd.start-;-;-;-;if(treep-1.lchild=c)if(treep-1.lchild=c)if(treep-1.lchild=c)if(treep-1.lchild=c)cd.bitscd.startcd.bitscd.startcd.bitscd.startcd.bitscd.start=0 0 0 0;else else else else cd.bitscd.startcd.bitscd.startcd.bitscd.startcd.bitscd.start=1 1 1 1;c=p;c=p;c=p;c=p;p=treep-1.parent;p=treep-1.parent;p=treep-1.parent;p=treep-1.parent;codei=codei=codei=codei=cdcdcdcd;哈夫曼树译码定义：哈夫曼树译码是指由给定的代码求出代码所表示的结点值。译码的过程是：从根结点出发，逐个读入电文中的二进制代码；若代码为0则走向左孩子，否则走向右孩子；一旦到达叶子结点，便可译出代码所对应的字符。然后又重新从根结点开始继续译码，直到二进制电文结束。哈夫曼解码算法哈夫曼解码算法哈夫曼解码算法哈夫曼解码算法DECODE(codetypeDECODE(codetypeDECODE(codetypeDECODE(codetype code,hufmtreecode,hufmtreecode,hufmtreecode,hufmtree tree)tree)tree)tree)intintintint i,j,c,p,b;i,j,c,p,b;i,j,c,p,b;i,j,c,p,b;intintintint endflagendflagendflagendflag=-1;=-1;=-1;=-1;i=m;i=m;i=m;i=m;scanf(scanf(scanf(scanf(“%d%d%d%d”,&b,&b,&b,&b););););while(b!=while(b!=while(b!=while(b!=endflagendflagendflagendflag)if(b=0)i=treei.lchild-1;if(b=0)i=treei.lchild-1;if(b=0)i=treei.lchild-1;if(b=0)i=treei.lchild-1;else i=treei.rchild-1;else i=treei.rchild-1;else i=treei.rchild-1;else i=treei.rchild-1;if(if(if(if(treei.lchildtreei.lchildtreei.lchildtreei.lchild=0)=0)=0)=0)putchar(codei.chputchar(codei.chputchar(codei.chputchar(codei.ch););););i=m;i=m;i=m;i=m;scanf(scanf(scanf(scanf(“%d%d%d%d”,&b,&b,&b,&b););););if(if(if(if(treei.lchildtreei.lchildtreei.lchildtreei.lchild!=0)!=0)!=0)!=0)printf(printf(printf(printf(“nERRORnnERRORnnERRORnnERRORn”););););小结二叉树的建立 二叉树的遍历深度优先广度优先先序遍历中序遍历后序遍历非递归实现
展开阅读全文