《树与二叉树 》ppt课件

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树形构造表示法树形构造表示法 A A B C D I H G

3、F E J K L M （a）空空树树 （b）仅仅含含有有根根结结点点的的树树 （c） 含含有有多多个个结结点点的的树树 2. 凹入法表示法凹入法表示法 A B E J K L F C G D H M I 3. 嵌套集合表示法文氏图表示法嵌套集合表示法文氏图表示法 A B E J K L F C G D H M I 4.广义表表示法括号表现法广义表表示法括号表现法 对树构造，广义表表示法可表示为：对树构造，广义表表示法可表示为：(A(B(E(J，K，L)，F)，C(G)，D(H(M)，I)分支分支(branch)：结点之间的二元关系序偶。：结点之间的二元关系序偶。结点结点(node)：一个数据

4、元素及指向其子树的分支。：一个数据元素及指向其子树的分支。结点的度结点的度(degree)：结点拥有的子树个数。：结点拥有的子树个数。叶结点叶结点(leaf)：度为零的结点。：度为零的结点。分支结点分支结点(branch node):有后继的结点称为分支结点。有后继的结点称为分支结点。儿子儿子(sons)：结点：结点x的子树的根。的子树的根。父亲父亲(parent):结点结点x的前驱结点称为的前驱结点称为x的父亲。的父亲。兄弟兄弟(brother)：同一父亲的结点的子女结点。：同一父亲的结点的子女结点。祖先祖先(ancestor)：根到该结点途径上的一切结点。：根到该结点途径上的一切结点。子孙

5、子孙(descendant)：某结点为根的子树上的恣意结点。：某结点为根的子树上的恣意结点。堂兄弟堂兄弟(cousin):父亲是兄弟关系或堂兄弟关系的结点。父亲是兄弟关系或堂兄弟关系的结点。结点层次结点层次(level)：从根开场，根为第一层，根的子女为：从根开场，根为第一层，根的子女为第二层，以此类推。第二层，以此类推。树的深度高度树的深度高度(depth)：树中结点的最大层次数：树中结点的最大层次数树的度：一棵树中最大的结点度数。树的度：一棵树中最大的结点度数。结点按层编号层中编号：将树中结点按从上层到下结点按层编号层中编号：将树中结点按从上层到下层，同层从左到右的次序排成一个线性序列，依

6、次给层，同层从左到右的次序排成一个线性序列，依次给他们编以延续的自然数。他们编以延续的自然数。祖辈上层：层号比结点祖辈上层：层号比结点x小的结点，称为小的结点，称为x的祖辈。的祖辈。后辈下层：层号比结点后辈下层：层号比结点x大的结点，称为大的结点，称为x的后辈。的后辈。有序树：假设一棵树中一切子树从左到右的排序是有顺有序树：假设一棵树中一切子树从左到右的排序是有顺序的，不能颠倒次序。称该树为有序树。序的，不能颠倒次序。称该树为有序树。 无序树：假设一棵树中一切子树的次序无关紧要，那么无序树：假设一棵树中一切子树的次序无关紧要，那么称为无序树。称为无序树。森林森林(forest)：m(m 0)棵

7、互不相交的树。棵互不相交的树。三、树的根本术语三、树的根本术语1层2层4层3层height= 4ACGBDEFKLHMIJABCDEFGHIJKLM结点结点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、祖先8.2 二叉树二叉树 (Binary Tree)定义定义:五种形状五种形状:一棵二叉树是结点的一个有限集合，该一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互上两棵分别称为左子树和右子树的、互不相交的二叉树组成。不相交的二叉树组成。LLRR特点特点:每个结点至多只需两棵子树二叉树中每个结点至多只需两棵子树二叉树中不存在度大于不存在度大于2的结点的结点二叉树的根本操作二叉树的根本操作1creat_tree(bt,str) 根据二叉树的括号表示法根据二叉树的括号表示法str建立一棵二叉树建立一棵二叉树bt。

9、2disptree(bt) 以凹入法显示一棵二叉树以凹入法显示一棵二叉树bt。3depth_bttree(bt) 求一棵二叉树求一棵二叉树bt的深度。的深度。4count_bttree(bt) 求一棵二叉树求一棵二叉树bt的结点个数。的结点个数。5leafcount_bttree(bt) 求一棵二叉树求一棵二叉树bt的叶子结点个数。的叶子结点个数。6nleafcount_bttree(bt) 求一棵二叉树求一棵二叉树bt 的非叶子结点个数。的非叶子结点个数。性质性质1 在二叉树的第在二叉树的第 i 层上至多有层上至多有 2i 1个个结点。结点。(i 1) 证明用归纳法证明用归纳法证明：当证明：

10、当i=1时，只需根结点，时，只需根结点，2 i-1=2 0=1。假设对一切假设对一切j，ij1，命题成立，即第，命题成立，即第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)。证明：由性质证明：由性

11、质1可见，深度为可见，深度为k的二叉树的最的二叉树的最大结点数为大结点数为 kii112kii1(层上的最大结点数）第性质性质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 -

12、1 n0 = n2 + 1 定义定义1 满二叉树满二叉树 (Full Binary Tree) 一棵深度为一棵深度为k且有且有2k -1个结点的二叉树称为个结点的二叉树称为满二叉树。满二叉树。两种特殊形状的二叉树两种特殊形状的二叉树621754389 10 1113 14 1512满二叉树满二叉树215436 7216543非完全二叉树非完全二叉树定义定义2 完全二叉树完全二叉树 (Complete Binary Tree) 假设设二叉树的高度为假设设二叉树的高度为h，那么共有，那么共有h层。层。除第除第 h 层外，其它各层层外，其它各层 (0 h-1) 的结点数的结点数都到达最大个数，第都到

13、达最大个数，第 h 层从右向左延续缺假层从右向左延续缺假设干结点，这就是完全二叉树。设干结点，这就是完全二叉树。621754389 10 11 12完全二叉树完全二叉树性质性质4 具有具有 n (n 0) 个结点的完全二叉个结点的完全二叉树的深度为树的深度为log2(n) 1 证明：证明：设完全二叉树的深度为设完全二叉树的深度为 h，那么根据，那么根据性质性质2和完全二叉树的定义有和完全二叉树的定义有2h1 - 1 n 2h - 1或或 2h1 n 2h取对数取对数 h1 1, 那么那么 i 的双亲为的双亲为(i /2) 假设假设2*i n, 那么那么 i 无左孩子无左孩子,否那么其左孩子是否

14、那么其左孩子是结点结点2i.假设假设2*i+1n,那么结点那么结点i无右孩子无右孩子,否那么其右孩否那么其右孩子为结点子为结点2*i+118234567910完全二叉树完全二叉树 普通二叉树普通二叉树的顺序表示的顺序表示 的顺序表示的顺序表示8.3 二叉树的存储构造二叉树的存储构造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含两个指针域的结点构含两个指针域的结

15、点构造造lChild data parent rChild含三个指针域的结点构造含三个指针域的结点构造parentdatalChildrChild三叉链表三叉链表二叉树链表表示的例如二叉树链表表示的例如ABCDFEroot ABCDFEroot ABCDFEroot二叉树二叉树 二叉链表二叉链表 三叉链表三叉链表typedef struct btnode struct btnode *lchild; int data; struct btnode *rchild;bitnode,*bitree; 二叉链表的定义二叉链表的定义假设一个二叉树含有假设一个二叉树含有n个结点，那么它的二叉链表个结点，

16、那么它的二叉链表中必含有中必含有2n个指针域，其中必有个指针域，其中必有n+1个空链域。个空链域。证明：边数证明：边数e=n-1;即非空链域为即非空链域为n-1个，那么空链个，那么空链域为域为2n-(n-1)=n+1个。个。三、二叉链表的递归创建及其根本操作的实现三、二叉链表的递归创建及其根本操作的实现 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

17、)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 二叉树遍历二叉树遍历树的遍历就是按某种次序访问树中的结点，树的遍历就是按某种次序访问树中的结点，要求每个结点访问一次且仅访问一次。要求每个结点访问一次且仅访问一次。 设访问根结点记作设访问根结点记作 V 遍历根的左子树记作遍历根的左子树记作 L 遍历根的右子树记作遍历根的右子树记作 R 那么能够的遍历次序有那么能够的遍历次序有 前序前序 VLR 中序中序 LVR 后序

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

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

20、eorder (bt-rchild ); 后序遍历二叉树算法的定义：后序遍历二叉树算法的定义：假设二叉树为空，那么空操作；假设二叉树为空，那么空操作；否那么否那么后序遍历左子树后序遍历左子树 (L)；后序遍历右子树后序遍历右子树 (R)；访问根结点访问根结点 (V)。遍历结果遍历结果 a b c d - * + e f / -后序遍历后序遍历 (Postorder Traversal)后序遍历二叉树的递归算法：后序遍历二叉树的递归算法：void postorder (bitree bt) if ( bt != NULL ) postorder ( bt-lchild ); postorder

21、( bt-rchild ); printf(“ %c,bt-data); 非递归实现先序遍历二叉树非递归实现先序遍历二叉树 利用一个一维数组作为栈，来存储二叉链表利用一个一维数组作为栈，来存储二叉链表中结点，算法思想为：中结点，算法思想为：1、从二叉树根结点开场，先将根结点入栈。、从二叉树根结点开场，先将根结点入栈。2、然后将栈顶结点出栈，输出结点的值，同、然后将栈顶结点出栈，输出结点的值，同时判别该结点有没有右子树，有那么将右子时判别该结点有没有右子树，有那么将右子树的根结点入栈；再判别有没有左子树，有树的根结点入栈；再判别有没有左子树，有那么将左子树的根结点入栈。假设栈不空那那么将左子树的

22、根结点入栈。假设栈不空那么反复第么反复第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); if(p-rchild!=NULL) stack+top=p-rchlid; /压右子树压右子树 if(p-lchild!=NULL) stack+top=p-lc

23、hild; /压左子树压左子树 非递归实现中序遍历二叉树非递归实现中序遍历二叉树 同样利用一个一维数组作栈，来存贮二叉链同样利用一个一维数组作栈，来存贮二叉链表中结点，算法思想为：表中结点，算法思想为：1、将所指的结点的左子树入栈，其下面的左、将所指的结点的左子树入栈，其下面的左子树也入栈子树也入栈2、弹出一个结点并输出，判别其能否有右子、弹出一个结点并输出，判别其能否有右子树，有那么入栈，再转到第树，有那么入栈，再转到第1步，没有右子步，没有右子树那么判别栈能否为空，不空那么弹出一个树那么判别栈能否为空，不空那么弹出一个结点，转回第结点，转回第2步，为空那么终了。步，为空那么终了。void

24、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); 非递归实现后序遍历二叉树非递归实现后序遍历二叉树 在后序遍历中，当搜索指针指向某一个结在后序遍历中，当搜索指针指向某一个结点时，不能马上进展访问，而先要遍历左子点时，不能

25、马上进展访问，而先要遍历左子树，所以此结点应先进栈保管，当遍历完它树，所以此结点应先进栈保管，当遍历完它的左子树后，再次回到该结点，还不能访问的左子树后，再次回到该结点，还不能访问它，还需先遍历其右子树它，还需先遍历其右子树,所以该结点还必需所以该结点还必需再次进栈，只需等它的右子树遍历完后，再再次进栈，只需等它的右子树遍历完后，再次退栈时，才干访问该结点。次退栈时，才干访问该结点。 为了区分同一结点的三次进栈及出栈，引为了区分同一结点的三次进栈及出栈，引入一个栈次数的标志，一个元素第一次进栈入一个栈次数的标志，一个元素第一次进栈标志为标志为1，第二次进标志为，第二次进标志为2，第三次进栈标，

26、第三次进栈标志为志为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) top-; p=stacktop; if(p.treenode!=NULL) if(p.si

27、gn=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); 线索二叉树的引入：线索二叉树的引入： 对二叉树遍历的过程本质上是对一个非线性构造

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

29、ee)ltag=0, lchild为左孩子指针为左孩子指针ltag=1, lchild为前驱线索为前驱线索rtag=0, rchild为右孩子指针为右孩子指针rtag=1, rchild为后继线索为后继线索ltagrtag结点构造结点构造typedef struct bithrnode elemtype data; /*数据域数据域*/ struct bithrnode *lchild，*rchild; /*左右指针左右指针*/ ptrtag ltag,rtag;/*左右标志左右标志*/ bithrnode,*bithrtree;线索二叉树线索二叉树 中结点的定义中结点的定义线索二叉树的创建和

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

31、结点的的lchild域指针和最后一个结点域指针和最后一个结点rchild域的指域的指针均指向头结点。针均指向头结点。 A D C B 0 A 0 1 B 1 0 C 1 root 1 D 1 A D C B NULL (a) 二二叉叉树树 (b)先先序序线线索索二二叉叉树树 (c)先先序序线线索索二二叉叉链链表表 先序序列为：先序序列为：ABCD A D C B NULL NULL （a）中中序序二二叉叉树树 （b） 中中序序线线索索二二叉叉链链表表 0 A 0 root 1 D 1 0 C 1 1 B 1 中序序列为：中序序列为：BADC C 0 A 0 1 B 1 0 C 1 1 D 1

32、root D B A NULL (a)后后序序线线索索二二叉叉树树 (b)后后序序线线索索二二叉叉链链表表 后序序列为：后序序列为：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-rtag=1; pre-rchild=p;/产生后继产生后继 pre=p;/坚持坚持pre指向指向p的前驱的前驱 inthread(p-rchild

33、,pre);/右子树线索化右子树线索化 遍历中序线索二叉树算法思想：遍历中序线索二叉树算法思想： 先判别指针域是用作线索还是指向子树，再决议能先判别指针域是用作线索还是指向子树，再决议能否进展递归调用。否进展递归调用。 bithrtree inorder_thread(bithrtree t) bithrtree thrt,pre,p; thrt=(bithrtree)malloc(sizeof(bithrnode); thrt-ltag=0;thrt-rtag=1; thrt-rchild=thrt; if(t=NULL) thrt-lchild=thrt; else p=thrt-lchi

34、ld=t; thrt-ltag=0; pre=thrt; inthread(p,pre); pre-rtag=1; thrt-rchild=pre; thrt-rtag=1; return thrt;8.6 二叉排序树二叉排序树 二叉排序树二叉查找树是一种特殊的二叉二叉排序树二叉查找树是一种特殊的二叉树，普通二叉树中只区分左、右子树，但不区树，普通二叉树中只区分左、右子树，但不区分结点的顺序，在二叉排序树中，一切结点都分结点的顺序，在二叉排序树中，一切结点都是有序的。是有序的。 特征：特征： 1假设它左子树非空，那么左子树上的一假设它左子树非空，那么左子树上的一切结点的关键字均小于根结点的关键

35、字。切结点的关键字均小于根结点的关键字。 2假设它右子树非空，那么右子树上一切假设它右子树非空，那么右子树上一切结点的关键字均大于根结点的关键字。结点的关键字均大于根结点的关键字。 3左、右子树本身各又是一个二叉排序树。左、右子树本身各又是一个二叉排序树。利用二叉排序树进展查找，算法比较简单利用二叉排序树进展查找，算法比较简单如想查找数据如想查找数据6，先和根，先和根5比较，转到右子树上比较，转到右子树上查找，再比较查找，再比较7，转左子树上，就找到了，转左子树上，就找到了6。即为查找算法中的二分查找法。即为查找算法中的二分查找法。二叉查找树的查找二叉查找树的查找 bitree binary_

36、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(“请输入要查找的结点的值：请输入要查找的结点的值：n); scanf(“%d,&v); p=binary_traverse_sear

37、ch(root,v); if(p=NULL) printf(“没有找到！没有找到！n); else printf(“找到了数据找到了数据%d,v);8.7 哈夫曼树哈夫曼树 (Huffman Tree)一、哈夫曼一、哈夫曼 (Huffman)树树,又称最优树又称最优树,是一类带权途径是一类带权途径长度最短的树长度最短的树1途径和途径长度途径和途径长度在一棵树中，从一个结点往下可以到达的孩子或子孙在一棵树中，从一个结点往下可以到达的孩子或子孙结点之间的通路，称为途径。通路中分支的数目称为结点之间的通路，称为途径。通路中分支的数目称为途径长度。途径长度。假设规定根结点的层数为假设规定根结点的层数为

38、1，那么从根结点到第，那么从根结点到第L层结层结点的途径长度为点的途径长度为L-1。2结点的权及带权途径长度结点的权及带权途径长度假设将树中结点赋予一个有着某种含义的数值，那么假设将树中结点赋予一个有着某种含义的数值，那么这个数值称为该结点的权。这个数值称为该结点的权。结点的带权途径长度为：从根结点到该结点之间的途结点的带权途径长度为：从根结点到该结点之间的途径长度与该结点的权的乘积。径长度与该结点的权的乘积。 3树的带权途径长度树的带权途径长度树的带权途径长度规定为一切叶子结点的带权途径长树的带权途径长度规定为一切叶子结点的带权途径长度之和，度之和，记为记为wpl= ，其中，其中n 为叶子结

39、点数目，为叶子结点数目，wi为第为第i 个叶子结点的权值，个叶子结点的权值，li 为第为第i 个叶子结点的途径长度。个叶子结点的途径长度。niiilw110niiilwWPLWPL = 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带权途径长度到带权途径长度到达最小达最小哈夫曼树哈夫曼树树的带权途径长度到达最小的二叉树即为哈夫曼树。树的带权途径长度到达最小的二叉树即为哈夫曼树。在哈夫曼树中，权值大的结点离根最近。在哈夫曼树中，权值大的结点离根最近。二、哈夫

40、曼树的构造算法二、哈夫曼树的构造算法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 23148715292914871529113581923421135819234229148715295811358192342291487152958100三、哈

41、夫曼树的运用三、哈夫曼树的运用-哈夫曼编码哈夫曼编码 在传送电文时在传送电文时,总是希望传送的时间尽能够短，总是希望传送的时间尽能够短，假设每个字符设计长度不等的编码，且能让出假设每个字符设计长度不等的编码，且能让出现频率高的采用尽能够短的编码，那么传送的现频率高的采用尽能够短的编码，那么传送的电文长度就会缩短。电文长度就会缩短。 例如：需求传送的电文为例如：需求传送的电文为“ABACCDA,假设假设设计设计A、B、C、D的编码分别为的编码分别为0 、00、1和和01，那么上述，那么上述7个字符的电文就转换成为长度个字符的电文就转换成为长度为为9个字符串个字符串“000011010。前缀编码：

42、设计长短不等的编码，必需使任何一个字符前缀编码：设计长短不等的编码，必需使任何一个字符都不是另一个字符的前缀，这样保证译码的独一性。都不是另一个字符的前缀，这样保证译码的独一性。 哈夫曼编码哈夫曼编码主要用途是实现数据紧缩。主要用途是实现数据紧缩。 假设按各个字符出现的概率不同而给予不等假设按各个字符出现的概率不同而给予不等长编码，尽能够减少总编码长度。长编码，尽能够减少总编码长度。 各字符出现概率为各字符出现概率为 2, 7, 4, 5 。以它们为。以它们为各叶结点上的权值各叶结点上的权值, 建立哈夫曼树。左分支建立哈夫曼树。左分支赋赋 0，右分支赋，右分支赋 1，得哈夫曼编码，得哈夫曼编码

43、(变长编码变长编码)。7254010011 CAST CAST SAT 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 : 111110011110

44、 11001111011101001001001110等长编码等长编码: A : 00 T : 10 C : 01 S : 110100111001001110110010001000100011000001112457 #define MAX 50 typedef struct 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&a

45、mp;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; 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

47、表示该编码表示该编码在数组在数组cd中的开场位置。对于第中的开场位置。对于第i个字符，它的编码个字符，它的编码存放在存放在huffcodei.cd中的从中的从huffcodei.start到到n的分量上。的分量上。typedef struct char cdMAX; int start;huffcode; huffcode hcdMAX; 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

48、=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(“输出哈夫曼编码：输出哈夫曼编码：n); for(i=0;in;i+) printf(“%c:,hti.data); for(k=hcdi.start;k=n;k+) printf(“%c,hcdi.cdk); printf(“n); 一、树的

49、存储构造一、树的存储构造1 1、双亲表示：以一组延续空间存储树、双亲表示：以一组延续空间存储树的结点，同时在结点中附设一个指针，的结点，同时在结点中附设一个指针，存放双亲结点在链表中的位置。该方法存放双亲结点在链表中的位置。该方法利用每个结点只需一个双亲的特点，可利用每个结点只需一个双亲的特点，可以很方便求结点的双亲，但不方便求结以很方便求结点的双亲，但不方便求结点的孩子。点的孩子。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

50、char data; int parent;ptnode; typedef struct ptnode nodesMAXSIZE; int nodenum; pttree; ABCDEFG2、孩子表示法、孩子表示法(多重链表多重链表)第一种处理方案第一种处理方案 等数量的链域等数量的链域 (d为树的度为树的度) data child1child2 child3childdABCDEFG 第二种处理方案第二种处理方案 孩子链表孩子链表将每个结点的孩子链在该结点之后组成链表，再将一切头结点组成一个线性表。ABCDEFG0 A1 B2 C 3 D4 E 5 F6 G 123 45 6 孩子表示法的存

51、储构造类型定义孩子表示法的存储构造类型定义typedef struct cnode int child; struct cnode *next;childlink;typedef struct char data; childlink *headptr;ctnode; /*表头向量中结点构造表头向量中结点构造*/typedef struct ctnode nodesMAXSIZE; /*表头向量表头向量*/ int nodenum,rootset;/*树中结点个数和根结点所在位置序号树中结点个数和根结点所在位置序号*/cttree;结点构造结点构造 dataFirstchildnextsibl

52、ingABCDEFG空链域空链域n+1个个3、树的孩子兄弟表示法二叉链表表示、树的孩子兄弟表示法二叉链表表示BCDGFE A 用孩子兄弟表示法实现的优缺陷用孩子兄弟表示法实现的优缺陷 这种树的存储构造的最大优点是结点构造一这种树的存储构造的最大优点是结点构造一致，和二叉树的表示完全一样，因此可利用致，和二叉树的表示完全一样，因此可利用二叉树的算法来实现对树的操作。二叉树的算法来实现对树的操作。 在这个构造上，易于实现查找某结点孩子的在这个构造上，易于实现查找某结点孩子的操作。操作。 在这个构造上查找某结点的双亲结点的算法在这个构造上查找某结点的双亲结点的算法不很方便，假设为每一个结点增设一个不很方便，假设为每一个结点增设一个parent域，那么查找某结点的双亲的操作也域，那么查找某结点的双亲的操作也很方便。很方便。1、将树转换成二叉树、将树转换成二叉树 对于一棵无序树，树中结点的各孩子次序是对于一棵无序树，树中结点的各孩子次序是无关紧要的，而二叉树中结点的左、右孩子无关紧要的，而二叉树中结点的左、右孩子是有区别的。为了防止混淆，我们商定树中是有区别的。为了防止混淆，我们商定树中每一个结点的孩子结点按从左到右的顺序编每一个结点的孩子结点按从左到右的顺序编号，也就是说，把树作为有序树对待。号，也就是说，把树作为有序树对