数据结构4树与二叉树.ppt
,第6章 树和二叉树,线索二叉树（Threaded Binary）,一棵具有n个结点二叉树，用二叉链表表示时，树中存在空指针域的个数为：n+1,利用空指针域指向结点的前驱或后继,结点结构,其中：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+b*c-d-e/f,Status 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 return OK,中序序列：a+b*c-d-e/f,线索化二叉树,Status InOrderThreading(BiThrTree return OK,void 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);,例：求中序线索树中给定结点的后继结点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)树-最优树,路径：从树中一个结点到另一个结点之间的分支构成这 两个结点间的路径,路径长度：路径上的分支数,树的路径长度：从树根到每一个结点的路径长度之和,结点的带权路径长度：该结点到根的路径长度与结点上权的乘积。,树的带权路径长度：树中所有叶子结点的带权路径长度之和。,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个结点,权值分别为7,5,2,4,构造有4个叶子结点的二叉树,(1)WPL=7*2+5*2+2*2+4*2=36,(2)WPL=4*2+7*3+5*3+2*1=46,(3)WPL=7*1+5*2+2*3+4*3=35,例：将百分制成绩转换成5级分制成绩,if(a60)b=“bad”;else if(a70)b=“pass”;else if(a80)b=“general”;else if(a90)b=“good”;else b=“excellent”,设有10000个记录,需31500次比较,需22000次比较,定理：设T为带权w1 w2 wn 的最优树 则 a)带权w1,w2的叶子Vw1,Vw2是兄弟 b)以Vw1,Vw2为儿子的分枝点，其通路长度最长。,设T为带权w1 w2 wn 的最优树，若将以带权w1,w2 的树叶为儿子的分枝点改为带权w1+w2的树叶，得到新树T，则T也是最优树。,Huffman树的构造根据给定的n个权值w1,w2,wn构成n棵二叉树的集合F=T1,T2,Tn，其中每棵二叉树Ti中只有一个带权为Wi的结点，其左右子树均为空。在F中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，且置新的二叉树根结点的权值为其左右子树根结点权值之和。在F中删除这两棵树，同时将新得到的二叉树加入森林中重复2、3上述两步，直到F只含一棵树为止，这棵树即为哈夫曼树。,例 w=5,29,7,8,14,23,3,11,二、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=15,void HuffmanCoding(HuffmanTree,123456789101112131415,weight parent lchild rchild,HT,9,9,1,7,8,10,10,3,4,15,11,11,8,9,19,12,12,5,10,29,13,13,6,11,42,14,14,2,12,58,15,15,13,14,100,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,HT,weight parent lchild rchild,123456789101112131415,
