数据结构4树与二叉树.ppt
第第6 6章章 树和二叉树树和二叉树 线索二叉树（线索二叉树（Threaded Binary）-+/-a*cdefb一棵具有一棵具有n个结点二叉树，用二叉链表表示时，树中存在个结点二叉树，用二叉链表表示时，树中存在空指针域的个数为：空指针域的个数为：n+1利用空指针域指向结点的前驱或后继利用空指针域指向结点的前驱或后继结点结构结点结构lchildrchildltagdatartag其中：其中：ltag=0 lchild指向结点的左孩子指向结点的左孩子 ltag=1 lchild指向结点的前驱指向结点的前驱 rtag=0 rchild指向结点的右孩子指向结点的右孩子 rtag=1 rchild指向结点的后继指向结点的后继 以这种结构构成的二叉链表叫线索链表，其中指以这种结构构成的二叉链表叫线索链表，其中指向前驱和后继的指针称作线索，加上线索的二叉树成向前驱和后继的指针称作线索，加上线索的二叉树成为线索二叉树。为线索二叉树。二叉树的二叉线索存储表示二叉树的二叉线索存储表示Typedef enum Link,Thread PointerTag;Typedef struct BiThrNode TElemType data;struct BiThrNode *lchild,*rchild;PointerTag LTag,RTag;BiThrNode,*BiThrTree;-+/-a*cdefb01-00+00/00e11a11*00f11b11-00c11d11thrtbt例如：例如：中序序列：中序序列：a+b*c-d-e/fStatus InOrderTraverse_Thr(BiThrTree T,Status(*Visit)(TElemType e)P=T-lchild;while(p!=T)while(p-LTag=Link)p=p-lchild;if(!Visit(p-data)return ERROR;while(p-RTag=Thread&p-rchild!=T)p=p-rchild;Visit(p-data);p=p-rchild;return OK中序序列：中序序列：a+b*c-d-e/f01-00+00/00e11a11*00f11b11-00c11d11thrtbt线索化二叉树线索化二叉树01thrt空线索化二叉树空线索化二叉树Status InOrderThreading(BiThrTree&Thrt,BiThrTree T)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;return OKvoid InThreading(BiThrTree p)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例：求中序线索树中给定结点的后继结点例：求中序线索树中给定结点的后继结点BiThrTree inordernext(BiThrTree p)if(p-RTag=Thread)return(p-rchild);else q=p-rchild;while(q-LTag=Link)q=q-lchild;return(q);6.6 赫夫曼赫夫曼(Huffman)树及其应用树及其应用一、赫夫曼一、赫夫曼(Huffman)树树-最优最优树树l路径：从树中一个结点到另一个结点之间的分支构成这路径：从树中一个结点到另一个结点之间的分支构成这 两个结点间的路径两个结点间的路径l路径路径长度：路径上的分支数长度：路径上的分支数l树的路径长度：从树根到每一个结点的路径长度之和树的路径长度：从树根到每一个结点的路径长度之和l结点的带权路径结点的带权路径长度：长度：该结点到根的路径长度与结点上权的乘积。该结点到根的路径长度与结点上权的乘积。l树的带权路径树的带权路径长度：树中所有叶子结点的带权路径长度之和。长度：树中所有叶子结点的带权路径长度之和。n记作：记作：wpl=wklk k=1定义：给定一组权定义：给定一组权w1 w2 wn,且且w1 w2 wn，设有一个二叉树，共有设有一个二叉树，共有n片叶子，分别带权片叶子，分别带权w1 w2 wn，该，该二叉树称为带权二叉树。二叉树称为带权二叉树。最优二叉树或最优二叉树或Huffman树树设有设有n个权值个权值w1 w2 wn，构造一棵有构造一棵有n个叶子结点的二叉树，每个叶子的个叶子结点的二叉树，每个叶子的权值为权值为wi,则则wpl最小的最小的那棵那棵二叉树叫二叉树叫最优二叉树或最优二叉树或Huffman树树.例有例有4 4个结点个结点,权值分别为权值分别为7,5,2,4,7,5,2,4,构造有构造有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例：将百分制成绩转换成例：将百分制成绩转换成5 5级分制成绩级分制成绩if(a60)b=“bad”;else if(a70)b=“pass”;else if(a80)b=“general”;else if(a90)b=“good”;else b=“excellent”分数分数 比例比例 0-59 60-69 70-79 80-89 90-100 0.05 0.15 0.40 0.30 0.10a80a70a60a90不及格不及格及格及格中等中等良好良好优秀优秀YYYYNNNN设有设有10000个记录个记录需需31500次比较次比较需需22000次比较次比较定理：定理：u设设T为带权为带权w1 w2 wn 的最优树的最优树 则则 a)带权带权w1,w2的的叶子叶子Vw1,Vw2是兄弟是兄弟 b)以以Vw1,Vw2为为儿子的分枝点，其通路长度最长。儿子的分枝点，其通路长度最长。u设设T为带权为带权w1 w2 wn 的最优树，若将以带权的最优树，若将以带权w1,w2 的树叶为儿子的分枝点改为带权的树叶为儿子的分枝点改为带权w1+w2的树叶，得到新树的树叶，得到新树T，则则T也是最优树。也是最优树。Huffman树的树的构造构造1.根据给定的根据给定的n个权值个权值w1,w2,wn构构成成n棵二叉树的棵二叉树的集合集合F=T1,T2,Tn，其中每棵二叉树其中每棵二叉树Ti中中只有一只有一个带权为个带权为Wi的的结点，其左右子树均为空。结点，其左右子树均为空。2.在在F中选取两棵根结点权值最小的树作左右子树，构中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，造一棵新的二叉树，且且置新的二叉树根结点的权值为置新的二叉树根结点的权值为其左右子树根结点权值之和。其左右子树根结点权值之和。3.在在F中删除这两棵树，同时将新得到的二叉树加入森中删除这两棵树，同时将新得到的二叉树加入森林中林中4.重复重复2、3上述两步，上述两步，直到直到F只含一棵树为止，这棵树只含一棵树为止，这棵树即即为为哈夫曼树。哈夫曼树。例a7b5c2d4a7b5c2d46a7b5c2d4611a7b5c2d461118例 w=5,29,7,8,14,23,3,1151429 7823 3111429 7823 1135887151429233581111358191429238715113581929 23148715292914871529113581923421135819234229148715295811358192342291487152958100二、二、Haffman编码编码前缀码：给定一个序列的集合，若没有一个序列是另一个前缀码：给定一个序列的集合，若没有一个序列是另一个序列的前缀，该序列集合称为前缀码。序列的前缀，该序列集合称为前缀码。例如：例如：000，001，01，10，11 1，0001，000 定理：任意一棵二叉树的树叶可对应一个前缀码。定理：任意一棵二叉树的树叶可对应一个前缀码。定理：任何一个前缀码都对应一棵二叉树。定理：任何一个前缀码都对应一棵二叉树。数据传输过程中字符的编码问题。数据传输过程中字符的编码问题。在为字符编码时，总希望总的编码长度尽可能地短，因在为字符编码时，总希望总的编码长度尽可能地短，因电文中每个字符出现的频率不同，所以可用前缀码，对常电文中每个字符出现的频率不同，所以可用前缀码，对常出现的字符用短码表示，使得到电文总长度最短。出现的字符用短码表示，使得到电文总长度最短。假设每个字符在电文中出现的次数为假设每个字符在电文中出现的次数为wi，其编码长度其编码长度为为li，电文中只有电文中只有n中字符中字符 n则电文总长为则电文总长为 wili i=1对应二叉树上，若对应二叉树上，若wi为叶子结点的权，为叶子结点的权，li为根到叶子的路径为根到叶子的路径长度长度 n 则二叉树的带权路径长度为则二叉树的带权路径长度为 wili i=1 所以设计电文总长最短的二进制前缀码，即为以几种所以设计电文总长最短的二进制前缀码，即为以几种字符出现的频率作为权值，设计一棵字符出现的频率作为权值，设计一棵Huffman树的问题，树的问题，由此得到的二进制前缀码便称为由此得到的二进制前缀码便称为Huffman编码。编码。一棵一棵n个叶子结点的个叶子结点的Huffman树树共有共有2n-1个结点个结点赫夫曼树和赫夫曼编码的存储表示赫夫曼树和赫夫曼编码的存储表示typedef struct unsigned int weight;unsigned int parent,lchild,rchild;HTNode,*HuffmanTree;typedef char *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=15void HuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,int n)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,i1,s1,s2);HTs1.parent=i;HTs2.parent=i;HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;5000290007000800014000230003000110000000000000000000000000000000123456789101112131415weight parent lchild rchildHT99178101034151111891912125102913136114214142125815151314100 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;else cd -start =1;HC i =(char*)malloc(n start)*sizeof(char);strcpy(HC i ,&cd start );free(cd);HTweight parent lchild rchild123456789101112131415590029140071000810001412002313003900111100811171512341913892914510421561158152121000131411358192342291487152958100
