数据结构4树与二叉树VIP

第6章树和二叉树

数据结构4树与二叉树共22页，您现在浏览的是第1页!线索二叉树（ThreadedBinary）-+/-a*cdefb一棵具有n个结点二叉树，用二叉链表表示时，树中存在空指针域的个数为：n+1利用空指针域指向结点的前驱或后继数据结构4树与二叉树共22页，您现在浏览的是第2页!结点结构lchildrchildltagdatartag其中：ltag=0lchild指向结点的左孩子ltag=1lchild指向结点的前驱rtag=0rchild指向结点的右孩子rtag=1rchild指向结点的后继

以这种结构构成的二叉链表叫线索链表，其中指向前驱和后继的指针称作线索，加上线索的二叉树成为线索二叉树。二叉树的二叉线索存储表示Typedefenum{Link,Thread}PointerTag;TypedefstructBiThrNode{TElemTypedata;structBiThrNode*lchild,*rchild;PointerTagLTag,RTag;}BiThrNode,*BiThrTree;数据结构4树与二叉树共22页，您现在浏览的是第3页!StatusInOrderTraverse_Thr(BiThrTreeT,Status(*Visit)(TElemTypee)){P=T->lchild;while(p!=T){while(p->LTag==Link)p=p->lchild;if(!Visit(p->data))returnERROR;while(p->RTag==Thread&&p->rchild!=T){p=p->rchild;Visit(p->data);}p=p->rchild;}returnOK}中序序列：a+b*c-d-e/f01-00+00/00e11a11*00f11b11-00c11d11thrtbt数据结构4树与二叉树共22页，您现在浏览的是第4页!voidInThreading(BiThrTreep){if(p){InThreading(p->lchild);if(!p->lchild){p->LTag=Thread;p->lchild=pre;}if(!pre->rchild){pre->RTag=Thread;pre->rchild=p;}pre=p;InThreading(p->rchild);}}01-00+00/00e11a11*00f11b11-00c11d11thrtbt数据结构4树与二叉树共22页，您现在浏览的是第5页!6.6赫夫曼(Huffman)树及其应用一、赫夫曼(Huffman)树---最优树路径：从树中一个结点到另一个结点之间的分支构成这两个结点间的路径路径长度：路径上的分支数树的路径长度：从树根到每一个结点的路径长度之和结点的带权路径长度：该结点到根的路径长度与结点上权的乘积。树的带权路径长度：树中所有叶子结点的带权路径长度之和。n记作：wpl=∑wklk

k=1定义：给定一组权w1w2……wn,且w1≤

w2≤

……≤wn，设有一个二叉树，共有n片叶子，分别带权w1w2……wn，该二叉树称为带权二叉树。数据结构4树与二叉树共22页，您现在浏览的是第6页!例有4个结点,权值分别为7,5,2,4,构造有4个叶子结点的二叉树abcd7524(1)WPL=7*2+5*2+2*2+4*2=36dcab2475(2)WPL=4*2+7*3+5*3+2*1=46abcd7524(3)WPL=7*1+5*2+2*3+4*3=35数据结构4树与二叉树共22页，您现在浏览的是第7页!定理：设T为带权w1≤

w2≤

……≤wn的最优树则a)带权w1,w2的叶子Vw1,Vw2是兄弟b)以Vw1,Vw2为儿子的分枝点，其通路长度最长。设T为带权w1≤

w2≤

……≤wn的最优树，若将以带权w1,w2的树叶为儿子的分枝点改为带权w1+w2的树叶，得到新树T’，则T’也是最优树。数据结构4树与二叉树共22页，您现在浏览的是第8页!例a7b5c2d4a7b5c2d46a7b5c2d4611a7b5c2d461118数据结构4树与二叉树共22页，您现在浏览的是第9页!二、Haffman编码前缀码：给定一个序列的集合，若没有一个序列是另一个序列的前缀，该序列集合称为前缀码。例如：{000，001，01，10，11}{1，0001，000}定理：任意一棵二叉树的树叶可对应一个前缀码。定理：任何一个前缀码都对应一棵二叉树。数据结构4树与二叉树共22页，您现在浏览的是第10页!一棵n个叶子结点的Huffman树共有2n-1个结点赫夫曼树和赫夫曼编码的存储表示typedefstruct{unsignedintweight;unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;typedefchar**HuffmanCode;例如：某通信系统中可能出现8种字符，其概率分别为0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11,设计Huffman编码。设权w={5,29,7,8,14,23,3,11}n=8则：m=15数据结构4树与二叉树共22页，您现在浏览的是第11页!HC=(HuffmanCode)malloc((n+1)*sizeof(char*));cd=(char*)malloc(n*sizeof(char));cd[n–1]=‘\0’;for(i=1;i<=n;++i){start=n–1;for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)if(HT[f].lchild==c)cd[--start]=‘0’;elsecd[--start]=‘1’;HC[i]=(char*)malloc((n–start)*sizeof(char));strcpy(HC[i],&cd[start]);}free(cd);}数据结构4树与二叉树共22页，您现在浏览的是第12页!-+/-a*cdefb01-00+00/00e11a11*00f11b11-00c11d11thrtbt例如：中序序列：a+b*c-d-e/f数据结构4树与二叉树共22页，您现在浏览的是第13页!线索化二叉树01thrt空线索化二叉树StatusInOrderThreading(BiThrTree&Thrt,BiThrTreeT){if(!(Thrt=(BiThrTree)malloc(sizeof(BithrNode))))exit(OVERFLOW);Thrt->LTag=Link;Thrt->Rtag=Thread;Thrt->rchild=Thrt;if(!T)Thrt->lchild=Thrt;else{Thrt->lchild=T;pre=Thrt;InThreading(T);pre->rchild=Thrt;pre->RTag=Thread;Thrt->rchild=pre;}returnOK}数据结构4树与二叉树共22页，您现在浏览的是第14页!例：求中序线索树中给定结点的后继结点BiThrTreeinordernext(BiThrTreep){if(p->RTag==Thread)return(p->rchild);else{q=p->rchild;while(q->LTag==Link)q=q->lchild;return(q);}}数据结构4树与二叉树共22页，您现在浏览的是第15页!最优二叉树或Huffman树——设有n个权值w1w2……wn，构造一棵有n个叶子结点的二叉树，每个叶子的权值为wi,则wpl最小的那棵二叉树叫最优二叉树或Huffman树.数据结构4树与二叉树共22页，您现在浏览的是第16页!例：将百分制成绩转换成5级分制成绩if(a<60)b=“bad”;elseif(a<70)b=“pass”;elseif(a<80)b=“general”;elseif(a<90)b=“good”;elseb=“excellent”

分数

比例

0--59

60-6970-79

80-8990-100

0.05

0.15

0.40

0.30

0.10a<80a<70a<60a<90不及格及格中等良好优秀YYYYNNNN设有10000个记录需31500次比较需22000次比较数据结构4树与二叉树共22页，您现在浏览的是第17页!Huffman树的构造根据给定的n个权值{w1,w2,……wn}构成n棵二叉树的集合F={T1,T2,……Tn}，其中每棵二叉树Ti中只有一个带权为Wi的结点，其左右子树均为空。在F中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，且置新的二叉树根结点的权值为其左右子树根结点权值之和。在F中删除这两棵树，同时将新得到的二叉树加入森林中重复2、3上述两步，直到F只含一棵树为止，这棵树即为哈夫曼树。数据结构4树与二叉树共22页，您现在浏览的是第18页!例w={5,29,7,8,14,23,3,11}51429782331114297823113588715142923358111135819142923871511358192923148715292914871529113581923421135819234229148715295811358192342291487152958100数据结构4树与二叉树共22页，您现在浏览的是第19页!数据传输过程中字符的编码问题。在为字符编码时，总希望总的编码长度尽可能地短，因电文中每个字符出现的频率不同，所以可用前缀码，对常出现的字符用短码表示，使得到电文总长度最短。假设每个字符在电文中出现的次数为wi，其编码长度为li，电文中只有n中字符n则电文总长为∑wili

i=1对应二叉树上，若wi为叶子结点的权，li为根到叶子的路径长度n则二叉树的带权路径长度为∑wili

i=1所以设计电文总长最短的二进制前缀码，即为以几种字符出现的频率作为权值，设计一棵Huffman树的问题，由此得到的二进制前缀码便称为Huffman编码。数据结构4树与二叉树共22页，您现在浏览的是第20页!voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn){if(n<=1)return;m=2*n–1;HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));for(p=HT,i=1;i<=n;++i,++p,++w)*p={*w,0,0,0};for(;i<=m;++i;++p)*p={0,0,0,0};for(i=n+1;i<=m;++i){select(HT,i–1,s1,s2);HT[s1].parent=i;HT[s2].parent=i;HT[i].lchil