《树与二叉树 》PPT课件.ppt

《《树与二叉树 》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《树与二叉树 》PPT课件.ppt（87页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第八章第八章 树与二叉树树与二叉树1.树的定义及其基本概念树的定义及其基本概念2.二叉树的基本概念和存储结构二叉树的基本概念和存储结构3.二叉树的遍历二叉树的遍历4.线索二叉树的概念及其遍历线索二叉树的概念及其遍历6.哈夫曼树及其构造方法哈夫曼树及其构造方法7.树与森林树与森林5.二叉排序树二叉排序树8.1 树的概念和基本术语树的概念和基本术语一、树的定义一、树的定义 树是由树是由 n(n 0)个结点的有限集合。如果个结点的有限集合。如果 n=0，称为空树；如果，称为空树；如果 n 0，则，则 有且仅有一个特定的称之为根有且仅有一个特定的称之为根(Root)的结的结点，它只有直接后继，但没有直

2、接前驱；点，它只有直接后继，但没有直接前驱；当当n 1，除根以外的其它结点划分为，除根以外的其它结点划分为 m(m 0)个互不相交的有限集个互不相交的有限集 T1,T2,Tm，其中每个集合本身又是一棵树，并且称为根其中每个集合本身又是一棵树，并且称为根的子树的子树(SubTree)。A只有根结点的树只有根结点的树ABCDEFGHIJKLM有子树的树有子树的树根根子子树树空树空树特点：树中至少有一个结点特点：树中至少有一个结点根根 树中各子树是互不相交的集合树中各子树是互不相交的集合二、树的表示二、树的表示1树形结构表示法树形结构表示法 2.凹入法表示法凹入法表示法3.嵌套集合表示法（文氏图表示

3、法）嵌套集合表示法（文氏图表示法）4.广义表表示法（括号表现法）广义表表示法（括号表现法）对树结构，广义表表示法可表示为：对树结构，广义表表示法可表示为：(A(B(E(J，K，L)，F)，C(G)，D(H(M)，I)分支分支(branch)：结点之间的二元关系（序偶）。：结点之间的二元关系（序偶）。结点结点(node)：一个数据元素及指向其子树的分支。：一个数据元素及指向其子树的分支。结点的度结点的度(degree)：结点拥有的子树个数。：结点拥有的子树个数。叶结点叶结点(leaf)：度为零的结点。：度为零的结点。分支结点分支结点(branch node):有后继的结点称为分支结点。有后继的结

4、点称为分支结点。儿子儿子(sons)：结点：结点x的子树的根。的子树的根。父亲父亲(parent):结点结点x的前驱结点称为的前驱结点称为x的父亲。的父亲。兄弟兄弟(brother)：同一父亲的结点的子女结点。：同一父亲的结点的子女结点。祖先祖先(ancestor)：根到该结点路径上的所有结点。：根到该结点路径上的所有结点。子孙子孙(descendant)：某结点为根的子树上的任意结点。：某结点为根的子树上的任意结点。堂兄弟堂兄弟(cousin):父亲是兄弟关系或堂兄弟关系的结点。父亲是兄弟关系或堂兄弟关系的结点。结点层次结点层次(level)：从根开始，根为第一层，根的子女为：从根开始，根为

5、第一层，根的子女为第二层，以此类推。第二层，以此类推。树的深度（高度）树的深度（高度）(depth)：树中结点的最大层次数：树中结点的最大层次数树的度树的度：一棵树中最大的结点度数。：一棵树中最大的结点度数。结点按层编号（层中编号）结点按层编号（层中编号）：将树中结点按从上层到下：将树中结点按从上层到下层，同层从左到右的次序排成一个线性序列，依次给层，同层从左到右的次序排成一个线性序列，依次给他们编以连续的自然数。他们编以连续的自然数。祖辈（上层）：祖辈（上层）：层号比结点层号比结点x小的结点，称为小的结点，称为x的祖辈。的祖辈。后辈（下层）：后辈（下层）：层号比结点层号比结点x大的结点，称为

6、大的结点，称为x的后辈。的后辈。有序树有序树：若一棵树中所有子树从左到右的排序是有顺序：若一棵树中所有子树从左到右的排序是有顺序的，不能颠倒次序。称该树为有序树。的，不能颠倒次序。称该树为有序树。无序树无序树：若一棵树中所有子树的次序无关紧要，则称为：若一棵树中所有子树的次序无关紧要，则称为无序树。无序树。森林森林(forest)：m(m 0)棵互不相交的树。棵互不相交的树。三、树的基本术语三、树的基本术语1层2层4层3层height=4ACGBDEFKLHMIJ结点结点结点的度结点的度叶结点叶结点分支结点分支结点子女子女双亲双亲兄弟兄弟祖先祖先子孙子孙结点层次结点层次树的深树的深度度树的度树

7、的度有序树有序树无序树无序树森林森林ABCDEFGHIJKLM结点结点A的度：的度：3结点结点B的度：的度：2结点结点M的度：的度：0叶子：叶子：K，L，F，G，M，I，J结点结点A的孩子：的孩子：B，C，D结点结点B的孩子：的孩子：E，F结点结点I的父亲：的父亲：D结点结点L的父亲：的父亲：E结点结点B，C，D为兄弟为兄弟结点结点K，L为兄弟为兄弟树的度：树的度：3结点结点A的层次：的层次：1结点结点M的层次：的层次：4树的深度：树的深度：4结点结点F，G为堂兄弟为堂兄弟结点结点A是结点是结点F，G的祖先的祖先8.2 二叉树二叉树(Binary Tree)定义定义:五种形态五种形态:一棵二叉

8、树是结点的一个有限集合，该一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互上两棵分别称为左子树和右子树的、互不相交的二叉树组成。不相交的二叉树组成。LLRR特点特点:每个结点至多只有两棵子树（二叉树中每个结点至多只有两棵子树（二叉树中不存在度大于不存在度大于2的结点）的结点）二叉树的基本操作二叉树的基本操作（1）creat_tree(bt,str)根据二叉树的括号表示法根据二叉树的括号表示法str建立一棵二叉树建立一棵二叉树bt。（2）disptree(bt)以凹入法显示一棵二叉树以凹入法显示一棵二叉树bt

9、。（3）depth_bttree(bt)求一棵二叉树求一棵二叉树bt的深度。的深度。（4）count_bttree(bt)求一棵二叉树求一棵二叉树bt的结点个数。的结点个数。（5）leafcount_bttree(bt)求一棵二叉树求一棵二叉树bt的叶子结点个数。的叶子结点个数。（6）nleafcount_bttree(bt)求一棵二叉树求一棵二叉树bt 的非叶子结点个数。的非叶子结点个数。性质性质1 在二叉树的第在二叉树的第 i 层上至多有层上至多有 2i 1个结个结点。点。(i 1)证明用归纳法证明用归纳法证明：当证明：当i=1时，只有根结点，时，只有根结点，2 i-1=2 0=1。假设对

10、所有假设对所有j，ij 1，命题成立，即第，命题成立，即第j层上层上至多有至多有2 j-1 个结点。个结点。由归纳假设第由归纳假设第i-1 层上至多有层上至多有 2i 2个结点。个结点。由于二叉树的每个结点的度至多为由于二叉树的每个结点的度至多为2，故在第，故在第i层上的最大结点数为第层上的最大结点数为第i-1层上的最大结点数层上的最大结点数的的2倍，即倍，即2*2i 2=2 i-1。二叉树的性质二叉树的性质性质性质2 深度为深度为 k 的二叉树至多有的二叉树至多有 2k-1个个结点结点(k 1)。证明：由性质证明：由性质1可见，深度为可见，深度为k的二叉树的最的二叉树的最大结点数为大结点数为

11、 20+21+2k-1=2k-1性质性质3 对任何一棵二叉树对任何一棵二叉树T,如果其叶结如果其叶结点数为点数为 n0,度为度为2的结点数为的结点数为 n2,则则n0n21.证明：若度为证明：若度为1的结点有的结点有 n1 个，总结点个数个，总结点个数为为 n，总边数为，总边数为 e，则根据二叉树的定义，则根据二叉树的定义，n=n0+n1+n2 e=2n2+n1=n-1因此，有因此，有 2n2+n1=n0+n1+n2-1 n2=n0-1 n0=n2+1 定义定义1 满二叉树满二叉树(Full Binary Tree)一棵深度为一棵深度为k且有且有2k-1个结点的二叉树称为个结点的二叉树称为满二

12、叉树。满二叉树。两种特殊形态的二叉树两种特殊形态的二叉树621754389 10 1113 14 1512满二叉树满二叉树215436 7216543非完全二叉树非完全二叉树定义定义2 完全二叉树完全二叉树(Complete Binary Tree)若设二叉树的高度为若设二叉树的高度为h，则共有，则共有h层。除第层。除第 h 层外，其它各层层外，其它各层(0 h-1)的结点数都达到的结点数都达到最大个数，第最大个数，第 h 层从右向左连续缺若干结点，层从右向左连续缺若干结点，这就是完全二叉树。这就是完全二叉树。621754389 10 11 12完全二叉树完全二叉树性质性质4 具有具有 n(n

13、 0)个结点的完全二叉个结点的完全二叉树的深度为树的深度为 log2(n)1 证明：证明：设完全二叉树的深度为设完全二叉树的深度为 h，则根据性，则根据性质质2和完全二叉树的定义有和完全二叉树的定义有2h1-1 n 2h-1或或 2h1 n 2h取对数取对数 h1 1,则则 i 的双亲为的双亲为(i/2)若若2*i n,则则 i 无左孩子无左孩子,否则其左孩子是结点否则其左孩子是结点2i.若若2*i+1n,则结点则结点i无右孩子无右孩子,否则其右孩子为结点否则其右孩子为结点2*i+118234567910完全二叉树完全二叉树 一般二叉树一般二叉树的顺序表示的顺序表示 的顺序表示的顺序表示8.3

14、 二叉树的存储结构二叉树的存储结构11 2 3 4 5 6 7 8 9102489 105673一、顺序表示一、顺序表示91 2 3 4 0 5 6 7 8 0 0 0 0 9 10 123654789 10二、链表表示二、链表表示datalChildrChild二叉链表二叉链表lChild data rChild含两个指针域的结点结构含两个指针域的结点结构lChild data parent rChild含三个指针域的结点结构含三个指针域的结点结构parentdatalChildrChild三叉链表三叉链表二叉树链表表示的示例二叉树链表表示的示例ABCDFEroot ABCDFEroot A

15、BCDFEroot二叉树二叉树 二叉链表二叉链表 三叉链表三叉链表typedef struct btnode struct btnode*lchild;int data;struct btnode*rchild;bitnode,*bitree;二叉链表的定义二叉链表的定义若一个二叉树含有若一个二叉树含有n个结点，则它的二叉链表中必个结点，则它的二叉链表中必含有含有2n个指针域，其中必有个指针域，其中必有n+1个空链域。个空链域。证明：边数证明：边数e=n-1;即非空链域为即非空链域为n-1个，则空链域为个，则空链域为2n-(n-1)=n+1个。个。三、二叉链表的递归创建及其基本操作的实现三、二

16、叉链表的递归创建及其基本操作的实现 char s=,a,b,c,d,e,f,g,h,I;root=creat_tree(s,1);bitree creat_tree(char*s,int p)bitree new;if(sp=|p15)return NULL;else new=(bitree)malloc(sizeof(bitree);new-data=sp;new-lchild=creat_tree(s,2*p);new-rchile=creat_tree(s,2*p+1);return new;8.4 二叉树遍历二叉树遍历树的遍历就是按某种次序访问树中的结点，树的遍历就是按某种次序访问树中

17、的结点，要求每个结点访问一次且仅访问一次。要求每个结点访问一次且仅访问一次。设访问根结点记作设访问根结点记作 V 遍历根的左子树记作遍历根的左子树记作 L 遍历根的右子树记作遍历根的右子树记作 R 则可能的遍历次序有则可能的遍历次序有 前序前序 VLR 中序中序 LVR 后序后序 LRV VLR中序遍历二叉树算法的定义：中序遍历二叉树算法的定义：若二叉树为空，则空操作；若二叉树为空，则空操作；否则否则中序遍历左子树中序遍历左子树(L)；访问根结点访问根结点(V)；中序遍历右子树中序遍历右子树(R)。遍历结果遍历结果 a+b*c-d-e/f中序遍历中序遍历(Inorder Traversal)-

18、/+*abcdefvoid inorder(bitree bt)if(bt!=NULL)inorder(bt-lchild);printf(“%c”,bt-data);inorder(bt-rchild);中序遍历二叉树的递归算法中序遍历二叉树的递归算法-/+*abcdef前序遍历二叉树算法的定义：前序遍历二叉树算法的定义：若二叉树为空，则空操作；若二叉树为空，则空操作；否则否则访问根结点访问根结点(V)；前序遍历左子树前序遍历左子树(L)；前序遍历右子树前序遍历右子树(R)。遍历结果遍历结果-+a*b-c d/e f前序遍历前序遍历(Preorder Traversal)-/+*abcdef

19、前序遍历二叉树的递归算法前序遍历二叉树的递归算法void preorder(bitree bt)if(bt!=NULL)printf(“%c”,bt-data);preorder(bt-lchild);preorder(bt-rchild);-/+*abcdef后序遍历二叉树算法的定义：后序遍历二叉树算法的定义：若二叉树为空，则空操作；若二叉树为空，则空操作；否则否则后序遍历左子树后序遍历左子树(L)；后序遍历右子树后序遍历右子树(R)；访问根结点访问根结点(V)。遍历结果遍历结果 a b c d-*+e f/-后序遍历后序遍历(Postorder Traversal)-/+*abcdef后序

20、遍历二叉树的递归算法：后序遍历二叉树的递归算法：void postorder(bitree bt)if(bt!=NULL)postorder(bt-lchild);postorder(bt-rchild);printf(“%c”,bt-data);-/+*abcdef非递归实现先序遍历二叉树非递归实现先序遍历二叉树 利用一个一维数组作为栈，来存储二叉链表利用一个一维数组作为栈，来存储二叉链表中结点，算法思想为：中结点，算法思想为：1、从二叉树根结点开始，先将根结点入栈。、从二叉树根结点开始，先将根结点入栈。2、然后将栈顶结点出栈，输出结点的值，同、然后将栈顶结点出栈，输出结点的值，同时判断该结

21、点有没有右子树，有则将右子树时判断该结点有没有右子树，有则将右子树的根结点入栈；再判断有没有左子树，有则的根结点入栈；再判断有没有左子树，有则将左子树的根结点入栈。如果栈不空则重复将左子树的根结点入栈。如果栈不空则重复第第2步，直到栈为空。步，直到栈为空。void preorder(bitree root)bitree p,stack100;int top=-1;/top为栈顶指针为栈顶指针 if(root!=NULL)top+;stacktop=root;/将根结点压入栈内将根结点压入栈内 while(top!=-1)p=stacktop;top-;printf(“%d ”,p-data);

22、if(p-rchild!=NULL)stack+top=p-rchlid;/压右子树压右子树 if(p-lchild!=NULL)stack+top=p-lchild;/压左子树压左子树 非递归实现中序遍历二叉树非递归实现中序遍历二叉树 同样利用一个一维数组作栈，来存贮二叉链同样利用一个一维数组作栈，来存贮二叉链表中结点，算法思想为：表中结点，算法思想为：1、将所指的结点的左子树入栈，其下面的左、将所指的结点的左子树入栈，其下面的左子树也入栈子树也入栈2、弹出一个结点并输出，判断其是否有右子、弹出一个结点并输出，判断其是否有右子树，有则入栈，再转到第树，有则入栈，再转到第1步，没有右子树则步，

23、没有右子树则判断栈是否为空，不空则弹出一个结点，转判断栈是否为空，不空则弹出一个结点，转回第回第2步，为空则结束。步，为空则结束。void inorder(bitree root)bitree p=root,stack100;/s为一个栈，为一个栈，top为栈顶指针为栈顶指针 int top=-1;do while(p!=NULL)top+;stacktop=p;p=p-lchild;if(top=0)p=stacktop;top-;printf(“%d ”,p-data);p=p-rchild;while(p!=NULL|top=0);非递归实现后序遍历二叉树非递归实现后序遍历二叉树 在后序

24、遍历中，当搜索指针指向某一个结在后序遍历中，当搜索指针指向某一个结点时，不能马上进行访问，而先要遍历左子点时，不能马上进行访问，而先要遍历左子树，所以此结点应先进栈保存，当遍历完它树，所以此结点应先进栈保存，当遍历完它的左子树后，再次回到该结点，还不能访问的左子树后，再次回到该结点，还不能访问它，还需先遍历其右子树它，还需先遍历其右子树,所以该结点还必须所以该结点还必须再次进栈，只有等它的右子树遍历完后，再再次进栈，只有等它的右子树遍历完后，再次退栈时，才能访问该结点。次退栈时，才能访问该结点。为了区分同一结点的三次进栈及出栈，引为了区分同一结点的三次进栈及出栈，引入一个栈次数的标志，一个元素

25、第一次进栈入一个栈次数的标志，一个元素第一次进栈标志为标志为1，第二次进标志为，第二次进标志为2，第三次进栈标，第三次进栈标志为志为3，并将标志同时存入栈中，当出栈的元，并将标志同时存入栈中，当出栈的元素的标志为素的标志为3时，才输出此结点。时，才输出此结点。struct forpost int sign;bitnode*treenode;void postorder(bitnode *root)forpost stack100,p,q;int top=0,i;p.treenode=root;p.sign=1;stacktop=p;top+;/将根结点入栈将根结点入栈while(top!=0)

26、top-;p=stacktop;if(p.treenode!=NULL)if(p.sign=1)q.treenode=p.treenode;q.sign=2;stacktop+=q;q.treenode=p.treenode-lchild;q.sign=1;stacktop+=q;if(p.sign=2)q.treenode=p.treenode;q.sign=3;stacktop+=q;q.treenode=p.treenode-rchild;q.sign=1;stacktop+=q;if(p.sign=3)printf(“%dt”,p.treenode-data);线索二叉树的引入：线索二

27、叉树的引入：对二叉树遍历的过程实质上是对一个非线性结构对二叉树遍历的过程实质上是对一个非线性结构进行线性化的操作。以二叉链表为存储结构时进行线性化的操作。以二叉链表为存储结构时,结点的左右孩子可以直接找到结点的左右孩子可以直接找到,但不能直接找到但不能直接找到结点的前驱和后继结点的前驱和后继,而结点的前驱和后继只有在而结点的前驱和后继只有在遍历二叉树的过程中才能得到。遍历二叉树的过程中才能得到。用二叉链表表示的二叉树中用二叉链表表示的二叉树中,n个结点的二叉树有个结点的二叉树有n+1个空链域，可利用这些空链域存储结点的前个空链域，可利用这些空链域存储结点的前驱或后继。驱或后继。8.5 线索二叉

28、树线索二叉树(Threaded Binary Tree)ltag=0,lchild为为左孩子指针左孩子指针ltag=1,lchild为为前驱线索前驱线索rtag=0,rchild为为右孩子指针右孩子指针rtag=1,rchild为为后继线索后继线索lchildlchildrchildrchilddatadataltagrtag结点结构结点结构typedef struct bithrnode elemtype data;/*数据域数据域*/struct bithrnode*lchild，*rchild;/*左右指针左右指针*/ptrtag ltag,rtag;/*左右标志左右标志*/bithrn

29、ode,*bithrtree;线索二叉树线索二叉树 中结点的定义中结点的定义线索二叉树的创建和遍历线索二叉树的创建和遍历中序构造线索二叉树算法思想中序构造线索二叉树算法思想:对二叉树一边中序遍历一边建线索对二叉树一边中序遍历一边建线索,若访问结若访问结点的左孩子为空点的左孩子为空,建立前趋线索建立前趋线索;若右孩子为空若右孩子为空,建立后继线索。建立后继线索。并且在二叉树的线索链表上也添加一个头结点，并且在二叉树的线索链表上也添加一个头结点，并令其并令其lchild域的指针指向二叉树的根结点，域的指针指向二叉树的根结点，其其rchild域的指针指向中序序列的最后一个结域的指针指向中序序列的最后

30、一个结点；反之，令二叉树的中序序列的第一个结点点；反之，令二叉树的中序序列的第一个结点的的lchild域指针和最后一个结点域指针和最后一个结点rchild域的指针域的指针均指向头结点。均指向头结点。先序序列为：先序序列为：ABCD中序序列为：中序序列为：BADC后序序列为：后序序列为：BDCA void inthread(bithrtree p,bithrtree pre)if(p)inthread(p-lchild,pre)/左子树线索化左子树线索化 if(p-lchild=NULL)p-ltag=1;p-lchild=pre;/产生前驱产生前驱 if(p-rchild=NULL)pre-r

31、tag=1;pre-rchild=p;/产生后继产生后继 pre=p;/保持保持pre指向指向p的前驱的前驱 inthread(p-rchild,pre);/右子树线索化右子树线索化 遍历中序线索二叉树算法思想：遍历中序线索二叉树算法思想：先判断指针域是用作线索还是指向子树，再决定是先判断指针域是用作线索还是指向子树，再决定是否进行递归调用。否进行递归调用。bithrtree inorder_thread(bithrtree t)bithrtree thrt,pre,p;thrt=(bithrtree)malloc(sizeof(bithrnode);thrt-ltag=0;thrt-rtag

32、=1;thrt-rchild=thrt;if(t=NULL)thrt-lchild=thrt;else p=thrt-lchild=t;thrt-ltag=0;pre=thrt;inthread(p,pre);pre-rtag=1;thrt-rchild=pre;thrt-rtag=1;return thrt;8.6 二叉排序树二叉排序树 二叉排序树（二叉查找树）是一种特殊的二叉二叉排序树（二叉查找树）是一种特殊的二叉树，一般二叉树中只区分左、右子树，但不区树，一般二叉树中只区分左、右子树，但不区分结点的顺序，在二叉排序树中，所有结点都分结点的顺序，在二叉排序树中，所有结点都是有序的。是有序的

33、。特征：特征：（1）若它左子树非空，则左子树上的所有结点）若它左子树非空，则左子树上的所有结点的关键字均小于根结点的关键字。的关键字均小于根结点的关键字。（2）若它右子树非空，则右子树上所有结点的）若它右子树非空，则右子树上所有结点的关键字均大于根结点的关键字。关键字均大于根结点的关键字。（3）左、右子树本身各又是一个二叉排序树。）左、右子树本身各又是一个二叉排序树。利用二叉排序树进行查找，算法比较简单利用二叉排序树进行查找，算法比较简单如想查找数据如想查找数据6，先和根，先和根5比较，转到右子树上比较，转到右子树上查找，再比较查找，再比较7，转左子树上，就找到了，转左子树上，就找到了6。即为

34、查找算法中的二分查找法。即为查找算法中的二分查找法。1 12 26 68 85 54 43 37 7二叉查找树的查找二叉查找树的查找 bitree binary_traverse_search(bitree p,int v)while(p!=NULL)if(p-data=value)return p;else if(p-datav)p=p-lchild;else p=p-rchild;return NULL;main()bitree root=NULL,p;int v,s16=0,5,4,7,2,0,6,8,1,3,0,0,0,0,0,0;root=creat_tree(s,1);printf

35、(“请输入要查找的结点的值：请输入要查找的结点的值：n”);scanf(“%d”,&v);p=binary_traverse_search(root,v);if(p=NULL)printf(“没有找到！没有找到！n”);else printf(“找到了数据找到了数据%d”,v);8.7 哈夫曼树哈夫曼树(Huffman Tree)一、哈夫曼一、哈夫曼(Huffman)树树,又称最优树又称最优树,是一类带权路是一类带权路径长度最短的树径长度最短的树1路径和路径长度路径和路径长度在一棵树中，从一个结点往下可以达到的孩子或子孙在一棵树中，从一个结点往下可以达到的孩子或子孙结点之间的通路，称为结点之间

36、的通路，称为路径路径。通路中分支的数目称为。通路中分支的数目称为路径长度路径长度。若规定根结点的层数为若规定根结点的层数为1，则从根结点到第，则从根结点到第L层结点的层结点的路径长度为路径长度为L-1。2结点的权及带权路径长度结点的权及带权路径长度若将树中结点赋予一个有着某种含义的数值，则这个若将树中结点赋予一个有着某种含义的数值，则这个数值称为该数值称为该结点的权结点的权。结点的带权路径长度结点的带权路径长度为：从根结点到该结点之间的路为：从根结点到该结点之间的路径长度与该结点的权的乘积。径长度与该结点的权的乘积。3树的带权路径长度树的带权路径长度树树的的带带权权路路径径长长度度规规定定为为

37、所所有有叶叶子子结结点点的的带带权权路路径径长长度之和，度之和，记为记为wpl=，其中，其中n 为叶子结点数目，为叶子结点数目，wi为第为第i 个叶子结点的权值，个叶子结点的权值，li 为第为第i 个叶子结点的路径长度。个叶子结点的路径长度。WPL=2*2+WPL=2*1+WPL=7*1+4*2+5*2+4*2+5*3+5*2+2*3+7*2=36 7*3=46 4*3=35 222444555777带权路径长度达带权路径长度达到最小到最小哈夫曼树哈夫曼树树的带权路径长度达到最小的二叉树即为哈夫曼树。树的带权路径长度达到最小的二叉树即为哈夫曼树。在哈夫曼树中，权值大的结点离根最近。在哈夫曼树中

38、，权值大的结点离根最近。(1)由给定的由给定的 n 个权值个权值 w0,w1,w2,wn-1，构造具有，构造具有 n 棵扩充二叉树的森林棵扩充二叉树的森林 F=T0,T1,T2,Tn-1，其中每棵扩充二叉树，其中每棵扩充二叉树 Ti 只有一只有一 个带权值个带权值 wi 的根结点的根结点,其左、右子树均为空。其左、右子树均为空。二、哈夫曼树的构造二、哈夫曼树的构造算法算法 (2)重复以下步骤重复以下步骤,直到直到 F 中仅剩下一棵中仅剩下一棵树为止：树为止：在在 F 中选取两棵根结点的权值最小的中选取两棵根结点的权值最小的扩充二叉树扩充二叉树,做为左、右子树构造一棵新做为左、右子树构造一棵新的

39、二叉树。置新的二叉树的根结点的权值为的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。其左、右子树上根结点的权值之和。在在 F 中删去这两棵二叉树。中删去这两棵二叉树。把新的二叉树加入把新的二叉树加入 F。F:7 5 2 47524初始F:7 5 6合并2 475246F:7 11 1175246合并5 6F:18 5合并7 1127461118哈夫曼树的构造过程哈夫曼树的构造过程例例 w=5,29,7,8,14,23,3,1151429 7823 3111429 7823 1135887151429233581111358191429238715113581929 231

40、48715292914871529113581923421135819234229148715295811358192342291487152958100三、哈夫曼树的应用三、哈夫曼树的应用-哈夫曼编码哈夫曼编码 在传送电文时在传送电文时,总是希望传送的时间尽可能短，总是希望传送的时间尽可能短，如果每个字符设计长度不等的编码，且能让出如果每个字符设计长度不等的编码，且能让出现频率高的采用尽可能短的编码，则传送的电现频率高的采用尽可能短的编码，则传送的电文长度就会缩短。文长度就会缩短。例如：需要传送的电文为例如：需要传送的电文为“ABACCDA”,如果设如果设计计A、B、C、D的编码分别为的编码

41、分别为0、00、1和和01，则上述，则上述7个字符的电文就转换成为长度为个字符的电文就转换成为长度为9个个字符串字符串“000011010”。前缀编码：设计长短不等的编码，必须使任何一个字符前缀编码：设计长短不等的编码，必须使任何一个字符都不是另一个字符的前缀，这样保证译码的唯一性。都不是另一个字符的前缀，这样保证译码的唯一性。哈夫曼编码哈夫曼编码主要用途是实现数据压缩。主要用途是实现数据压缩。设给出一段报文：设给出一段报文：CAST CAST SAT AT A TASA字符集合是字符集合是 C,A,S,T，各字符出现概，各字符出现概率为率为 C:2/18,A:7/18,S:4/18,T:5/

42、18,化整化整为为 2,7,4,5。若给每个字符以等长编码若给每个字符以等长编码 A:00 T:10 C:01 S:11则总编码长度为则总编码长度为(2+7+4+5)*2=36.若按各个字符出现的概率不同而给予不等长若按各个字符出现的概率不同而给予不等长编码，尽可能减少总编码长度。编码，尽可能减少总编码长度。各字符出现概率为各字符出现概率为 2,7,4,5。以它们为。以它们为各叶结点上的权值各叶结点上的权值,建立哈夫曼树。建立哈夫曼树。左分支左分支赋赋 0，右分支赋，右分支赋 1，得哈夫曼编码得哈夫曼编码(变长编码变长编码)。7254010011A AC CT TS S CAST CAST S

43、AT AT A TASA A:0 T:10 C:110 S:111它的总它的总编码长度：编码长度：7*1+5*2+(2+4)*3=35。比等长编码的情形要短。比等长编码的情形要短。总编码长度正好等于哈夫总编码长度正好等于哈夫曼树的带权路径长度曼树的带权路径长度WPL。哈夫曼编码是一种哈夫曼编码是一种无前缀无前缀编码编码(都由叶结点组成都由叶结点组成,路径路径不会重复不会重复)。解码时不会混淆。解码时不会混淆。哈夫曼编码哈夫曼编码:A:0 T:10 C:110 S:111等长编码等长编码:A:00 T:10 C:01 S:110001112457#define MAX 50 typedef st

44、ruct char data;int weight;int parent;int left;int right;int flag;huffnode;huffnode ht2*MAX;int select(int i)int k=32767,j,q;for(j=0;j=i;j+)if(htj.weightk&htj.flag=-1)k=htj.weight;q=j;htq.flag=1;return q;void creat_hufftree(int n)int i,k,l,r;for(i=0;i2*n-1;i+)hti.parent=hti.left=hti.right=hti.flag=-1

45、;for(i=n;i2*n-1;i+)l=select(i-1);r=select(i-1);htl.parent=i;htr.parent=i;hti.weight=htl.weight+htr.weight;hti.left=l;hti.right=r;哈夫曼编码算法：哈夫曼编码算法：在建好的哈夫曼树中求哈夫曼编码，实质上就是在建好的哈夫曼树中求哈夫曼编码，实质上就是从叶结点开始，沿结点的双亲链域回退到根结点，从叶结点开始，沿结点的双亲链域回退到根结点，每回退一步，就走过了哈夫曼树的一个分支，从而每回退一步，就走过了哈夫曼树的一个分支，从而得到一位哈夫曼码值。得到一位哈夫曼码值。这样求得的

46、码是从低位到高位，可以设置一结构这样求得的码是从低位到高位，可以设置一结构体数组体数组huffcode来存放各字符的哈夫曼编码。其结来存放各字符的哈夫曼编码。其结构如下：构如下：cd start 其中其中cd是一维数组用来存放编码，是一维数组用来存放编码，start表示该编码表示该编码在数组在数组cd中的开始位置。对于第中的开始位置。对于第i个字符，它的编码个字符，它的编码存放在存放在huffcodei.cd中的从中的从huffcodei.start到到n的分量上。的分量上。typedef struct char cdMAX;int start;huffcode;huffcode hcdMAX

47、;76-1-1155-1-1124-1-1144-1-116523111614118-105-1w parent l r flag 0 1 2 3 4 5 6 creat_huffcode(int n)int i,f,c;huffcode d;for(i=0;in;i+)d.start=n+1;c=i;f=hti.parent;while(f!=-1)if(htf.left=c)d.cd-d.start=0;else d.cd-d.start=1;c=f;f=htf.parent;hcdi=d;void display_huffcode(int n)int i,k;printf(“输出哈夫曼编

48、码：输出哈夫曼编码：n”);for(i=0;in;i+)printf(“%c:”,hti.data);for(k=hcdi.start;k=n;k+)printf(“%c”,hcdi.cdk);printf(“n”);一、树的存储结构一、树的存储结构1 1、双亲表示：以一组连续空间存储树的结点，、双亲表示：以一组连续空间存储树的结点，同时在同时在结点中附设一个指针，存放双亲结点结点中附设一个指针，存放双亲结点在链表中的位置。该方法利用每个结点只有在链表中的位置。该方法利用每个结点只有一个双亲的特点，可以很方便求结点的双亲，一个双亲的特点，可以很方便求结点的双亲，但不方便求结点的孩子。但不方便求

49、结点的孩子。8.8 树与森林树与森林ABCDEFGdataparentA B C D E F G-1 0 0 0 1 1 3 0 1 2 3 4 5 6用双亲表示实现的树定义用双亲表示实现的树定义typedef struct char data;int parent;ptnode;typedef struct ptnode nodesMAXSIZE;int nodenum;pttree;ABCDEFG2、孩子表示法、孩子表示法(多重链表多重链表)第一种解决方案第一种解决方案 等数量的链域等数量的链域(d为树的度为树的度)data child1child2child3childdABCDEFG

50、第二种解决方案第二种解决方案 孩子链表孩子链表将每个结点的孩子链在该结点之后组成链表，再将所将每个结点的孩子链在该结点之后组成链表，再将所有头结点组成一个线性表。有头结点组成一个线性表。ABCDEFG0 A1 B2 C 3 D4 E 5 F6 G 123 45 6 孩子表示法的存储结构类型定义孩子表示法的存储结构类型定义typedef struct cnode int child;struct cnode*next;childlink;typedef struct char data;childlink*headptr;ctnode;/*表头向量中结点结构表头向量中结点结构*/typedef