ch树实用学习教程.pptx

《ch树实用学习教程.pptx》由会员分享，可在线阅读，更多相关《ch树实用学习教程.pptx（104页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第六章 树 树是一类重要的非线性数据结构，是以分支关系定义的层次结构。6.1 树的定义和基本术语一、树的定义定义：树(Tree)是n(n=0)个结点的有限集T，其中：有且仅有一个特定的结点，称为树的根(Root)；当n1时，其余结点可分为m(m0)个互不相交的有限集T1,T2,Tm，其中每一个集合本身又是一棵树，称为根的子树(Subtree)；当n=0时，称这棵树为空树。非空树的特点：树中至少有一个结点根树中各子树是互不相交的集合一棵有n个结点的树有n-1条边树的其它表示法第1页/共104页A只有根结点的树ABCDEFGHIJKLM有子树的树根子树第2页/共104页 A BCEDFHGIA B

2、 D E H F C G I(A(A(B B(E E(K,LK,L),F,F),C,C(G G),D,D(H H(M M),I,J,I,J)广义表表示法 嵌套集合表示法 凹入表示法 第3页/共104页家谱结构图家谱结构图Lineal TreePedigree Tree(binary tree)第4页/共104页磁盘目录文件系统第5页/共104页UNIXUNIX文件系统的系统结构图文件系统的系统结构图第6页/共104页某高校院系结构图某高校院系结构图第7页/共104页二、基本术语结点(Node)表示树中的元素，包括数据项及若干指向其子树的分支结点的度(Degree)树的结点所拥有的子树数叶子(L

3、eaf)度为0的结点，也称为终端结点孩子(Child)结点子树的根称为该结点的孩子双亲(Parents)孩子结点的上层结点叫该结点的兄弟(Sibling)同一双亲的孩子堂兄弟其双亲在同一层的结点祖先(Ancestor)从根到该结点所经分支上的所有结点子孙(Descendant)以某结点为根的子树中的任一结点都称为该结点的树的度 树内各结点的度的最大值结点的层次(Level)从根结点算起，根为第一层，它的孩子为第二层若某结点在第L层，则其子树的根就在第L+1层。深度(Depth)树中结点的最大层次数森林(Forest)m(m0)棵互不相交的树的集合有序树(Ordered Tree)将树中结点的各

4、子树看成是从左至右有次序的（即不能互换）；反之，则是无序树(Unordered Tree)。第8页/共104页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的祖先第9页/共104页6.2 二叉树(Binary Tree)一、二叉树的定义定义（递归定义）二叉树是n(n0)个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为左子树和

5、右子树的互不相交的二叉树构成。特点每个结点至多有二棵子树(即不存在度大于2的结点)二叉树的子树有左、右之分，且其次序不能任意颠倒基本形态思考：二叉树是树的特殊情况吗？二叉树是度为2的有序树吗？A只有根结点的二叉树空二叉树AB右子树为空AB左子树为空ABC左、右子树均非空第10页/共104页二叉树与2度树的区别(1)二叉树(2)树DABC T2 2度树ABC T3 1度树 T42度树A T1 0度树CABT4CBBABT3T2CT5AT1CBAAACDD第11页/共104页ABCBBCBBCCCAAAABBCCAAu问题：一棵具有问题：一棵具有3 3个结点的二叉树个结点的二叉树总共有多少种不同的

6、形态？总共有多少种不同的形态？u问题：一棵具有问题：一棵具有3 3个结点的个结点的一般一般树树总共有多少种不同的形态？总共有多少种不同的形态？n个结点可构成多少种不同形态的二叉树：第12页/共104页二、二叉树的性质性质1：v性质2：深度为k的二叉树至多有 个结点(k1)证明：由性质1，可得深度为k 的二叉树最大结点数是证明：用归纳法证明之 i=1时，只有一个根结点，是对的 假设对所有j(1j1，则其双亲是i/2 如果2in，则结点i无左孩子；如果2in，则其左孩子是2i 如果2i+1n，则结点i无右孩子；如果2i+1n，则其右孩子是2i+1第19页/共104页课堂练习（1）一个深度为4的二叉

7、树至多有（）个结点。(A)15(B)12(C)17(D)20（2）下列说法正确的是（）(A)二叉树中任何一个结点的度都为2(B)二叉树的度为2(C)一棵二叉树的度可小于2 (D)任何一棵二叉树中至少有一个结点的度为2（3）在一个二叉树中，叶结点个数为50，仅有一个孩子的结点个数为30，那么总结点数为多少个？()（A）100 （B）128 （C）129 （D）130Practice能力培养：加深对二叉树性质的理解。能力培养：加深对二叉树性质的理解。Engineering第20页/共104页将一棵有将一棵有100个结点的完全二叉树从上到下，从左到个结点的完全二叉树从上到下，从左到右依次对结点进行排

8、序，根为右依次对结点进行排序，根为1号，则号，则49号结点的左孩号结点的左孩子编号为子编号为_二叉树有二叉树有50个叶子结点，则二叉树的总结点数至少个叶子结点，则二叉树的总结点数至少有有_个个完全二叉树的第完全二叉树的第8层有层有8个结点，则该树的叶子结点个结点，则该树的叶子结点数为数为_个个完全二叉树的第完全二叉树的第7层有层有10个叶子结点，则整个树的结个叶子结点，则整个树的结点数最多是点数最多是_个个课外练习：对二叉树性质的应用Practice第21页/共104页三、二叉树的存储结构顺序存储结构：以层次顺序存储二叉树的数据元素实现：按满二叉树的结点层次编号，依次存放二叉树中的数据元素特点

9、：结点间关系蕴含在其存储位置中浪费空间，但适于存储满二叉树和完全二叉树一个深度为K且只有K个结点的单支树却需要长度为2K1的一维数组。abcdefga b c d e 0 0 0 0 f g 0 1 2 3 4 5 6 7 8 9 10可以看出，数组下标和结点的编号相对应，即结点在数组中的位置隐含了结点之间的关系。ABC第22页/共104页完全二叉树的顺序存储结构第23页/共104页右单支二叉树的顺序存储结构若是右单枝树，空间利用率为:k k =2 2k k-1-1 k=3,=3/7；k=4,k=4,=4/15=4/15；k=10,k=10,=10/1023=10/1023 0.00980.0

10、098 第24页/共104页课堂练习设有一棵二叉树的顺序存储表示如上图所示。试问：画出这棵二叉树的逻辑结构。哪个结点是根结点？哪个结点是D的双亲结点？C的左、右孩子分别是什么结点？A C BDGEFH第25页/共104页链式存储结构二叉链表typedef struct BiTNode TElemType data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;lchild data rchild ABCDEFG在n个结点的二叉链表中，有n+1个空指针域 AB C D E F G第26页/共104页l三叉链表typedef struct BiTNo

11、de TElemType data;struct BiTNode *lchild,*rchild,*parent;BiTNode,*BiTree;lchild data parent rchildABCDEFG A B C D E F G第27页/共104页6.3 遍历二叉树和线索二叉树一、遍历二叉树（Traversing Binary Tree）定义：按某种规则访问二叉树的每一个结点且每一结点仅被访问一次。遍历的目的：得到二叉树中各结点的一种线性顺序，使非线性的二叉树线性化，从而简化有关的运算和处理。规则：先序遍历：访问根结点；先序遍历左子树；先序遍历右子树中序遍历：中序遍历左子树；访问根结

12、点；中序遍历右子树后序遍历：后序遍历左子树；后序遍历右子树；访问根结点按层次遍历：从上到下、从左到右按层次依次访问各个结点DLR、LDR、LRDDRL、RDL、RLD第28页/共104页ADBCD L RAD L RD L RBDCD L R先序遍历序列：A B D C先序遍历:DLRPreorder Traversal第29页/共104页ADBCL D RBL D RL D RADCL D R中序遍历序列：B D A C中序遍历:LDRInorder Traversal第30页/共104页ADBC L R DL R DL R DADCL R D后序遍历序列：D B C A后序遍历:LRDPo

13、storder TraversalB第31页/共104页前序遍历：A B D G C E 中序遍历：D G B A E C后序遍历：G D B E C AABEDCGABDCEG结论：三种遍历过程中经过结点的路线一 样，只是访问各结点的时机不同。第32页/共104页先序遍历：中序遍历：后序遍历：层次遍历：A B D C E FD B A E C FA B C D E FD B E F C A课堂练习第33页/共104页先序遍历：中序遍历：后序遍历：层次遍历：A B E F C D GE B F A C G DA B C E F D GE F B G D C ACDGFEAB课堂练习第34页/共

14、104页先序遍历：中序遍历：后序遍历：层次遍历：A B C D E G FC B E G D F AA B C D E F GC G E F D B AABCDEFG课堂练习第35页/共104页-+/a*b-efcd先序遍历：先序遍历：中序遍历：中序遍历：后序遍历：后序遍历：-+a*b-c d/e f-+a*b-cd/ef-+a*b-c d/e f例：表达式a+b*(c d)e/f前缀表示（波兰式）前缀表示（波兰式）前缀表示（波兰式）前缀表示（波兰式）中缀表示中缀表示中缀表示中缀表示后缀表示（逆波兰式）后缀表示（逆波兰式）后缀表示（逆波兰式）后缀表示（逆波兰式）课堂练习第36页/共104页 在

15、一棵二叉树的先序遍历、中序遍历，后序遍历所产生在一棵二叉树的先序遍历、中序遍历，后序遍历所产生的序列中，所有叶结点的先后顺序（的序列中，所有叶结点的先后顺序（）（A A）都不相同）都不相同（B B）完全相同）完全相同（C C）先序和中序相同，而与后序不同）先序和中序相同，而与后序不同 （D D）中序和后序相同，而与先序不同）中序和后序相同，而与先序不同 如果一棵二叉树中任一结点的值都大于其左子树中所有如果一棵二叉树中任一结点的值都大于其左子树中所有结点的值，且小于其右子树中所有结点的值，现欲得到结点的值，且小于其右子树中所有结点的值，现欲得到各结点值的递增序列，试问应采用的遍历的方法是什么各结

16、点值的递增序列，试问应采用的遍历的方法是什么（）（A A）先序遍历）先序遍历 （B B）中序遍历（）中序遍历（C C）后序遍历（）后序遍历（D D）层次）层次遍历遍历 课堂练习第37页/共104页课堂练习【练习1】分别写出该二叉树的前序、中序和后序序列。【练习2】已知一棵二叉树的先序序列与中序序列分别为：ABCDEFGHI和BCAEDGHFI，画出这棵二叉树。【练习3】已知二叉树的中序序列和后序序列分别为：BDCEAFHG和DECBHGFA，画出这棵二叉树。第38页/共104页void PreOrder(BiTree bt)/二叉树的前序遍历算法二叉树的前序遍历算法 if (t)visit(b

17、t-data);/*访问根结点访问根结点*PreOrder(bt-lchild);/*递归遍历左子树递归遍历左子树*/PreOrder(bt-rchild);/*递归遍历右子树递归遍历右子树*/思考如何得到二叉树的中序和后序遍历的递归算法？思考：1.visit 函数能做什么？2.visit(bt-data)这条语句执行次数？3.改变visit(bt-data)这条语句的位置会产生 什么效果?前序遍历二叉树的递归算法？第39页/共104页中序遍历和后序遍历二叉树的递归算法中序遍历递归算法void InOrder(BiTree bt)if(bt)InOrder(bt-lchild);visit(b

18、t-data);InOrder(bt-rchild);后序遍历递归算法void PostOrder(BiTree bt)if(bt)PostOrder(bt-lchild);PostOrder(bt-rchild);visit(bt-data);第40页/共104页算法：先序遍历递归算法void PreOrder(BiTree bt)if(bt!=NULL)printf(“%Ct,bt-data);PreOrder(bt-lchild);PreOrder(bt-rchild);主程序主程序Pre(T)返回返回pre(T R);返回返回pre(T R);ACBDTBprintf(B);pre(T

19、 L);BTAprintf(A);pre(T L);ATDprintf(D);pre(T L);DTCprintf(C);pre(T L);C返回T左是空返回pre(T R);T左是空返回T右是空返回T左是空返回T右是空返回pre(T R);先序序列：A B D C第41页/共104页l每遇到一个结点就把它推入栈，然后去周游其每遇到一个结点就把它推入栈，然后去周游其左子树；算法执行过程中，空结点也需入栈；左子树；算法执行过程中，空结点也需入栈；l周游完该结点的左子树后，从栈顶删除这个结周游完该结点的左子树后，从栈顶删除这个结点并访问之；点并访问之；l然后按照二叉链表存储结构中该结点右链接指然后

20、按照二叉链表存储结构中该结点右链接指示的地址再去周游该结点的右子树。示的地址再去周游该结点的右子树。二叉树的中序遍历的非递归算法（使用堆栈）二叉树的中序遍历的非递归算法（使用堆栈）第42页/共104页Status InorderTraverse(Bitree T)InitStacks(S);Push(S,T);/根指针进栈 while(!StackEmpty(S)while(GetTop(S,p)&p)Push(S,p-lchild);/向左走到尽头 Pop(S,p);/空指针退栈 if(!StackEmpty(S)/访问结点，向右一步 Pop(S,p);if(!Visit(p-data)re

21、turn ERROR;Push(S,p-rchild);return OK;二叉树的中序遍历的非递归算法ADBC第43页/共104页怎样实现二叉树的前序遍历的非递归算法？怎样实现二叉树的前序遍历的非递归算法？怎样实现二叉树的后序遍历的非递归算法？怎样实现二叉树的后序遍历的非递归算法？课堂思考与讨论l思考是使用栈来处理访问的结点还是使用队思考是使用栈来处理访问的结点还是使用队列来处理访问的结点？列来处理访问的结点？第44页/共104页l每遇到一个结点，先访问该结点，并把该结点每遇到一个结点，先访问该结点，并把该结点的非空右子结点推入栈中，然后周游其左子树；的非空右子结点推入栈中，然后周游其左子树

22、；l左子树周游不下去时，从栈顶托出待访问的结左子树周游不下去时，从栈顶托出待访问的结点，继续周游。算法执行过程中，只有非空结点点，继续周游。算法执行过程中，只有非空结点入栈。入栈。l为了算法的简洁，最开始压入一个空指针作为为了算法的简洁，最开始压入一个空指针作为监视哨；当这个空指针被弹出来时，周游就结束监视哨；当这个空指针被弹出来时，周游就结束了。了。二叉树的前序遍历的非递归算法的主要思想二叉树的前序遍历的非递归算法的主要思想第45页/共104页l每遇到一个结点，先把它推入栈中，去周游它的每遇到一个结点，先把它推入栈中，去周游它的左子树；左子树；l周游完它的左子树后，应继续周游该结点的右子周游

23、完它的左子树后，应继续周游该结点的右子树；算法执行过程中，只有非空结点入栈。树；算法执行过程中，只有非空结点入栈。l周游完它的右子树之后，才从栈顶输出该结点并周游完它的右子树之后，才从栈顶输出该结点并访问它。访问它。二叉树的后序遍历的非递归算法的主要思想二叉树的后序遍历的非递归算法的主要思想第46页/共104页l首先访问第首先访问第1 1层，也就是根结点所在的层；层，也就是根结点所在的层；l然后从左到右依次访问第二层两个结点；然后从左到右依次访问第二层两个结点；l以此类推，当第以此类推，当第i i层的所有结点访问完之后，再层的所有结点访问完之后，再从左至右依次访问第从左至右依次访问第i+1i+

24、1层的各个结点。层的各个结点。二叉树按层次遍历的算法主要思想二叉树按层次遍历的算法主要思想思考是使用栈来处理访问的结点还是使用队思考是使用栈来处理访问的结点还是使用队列来处理访问的结点？列来处理访问的结点？第47页/共104页Status Levelorder(Bitree T)if(T)InitQueue(Q);/初始化队列初始化队列 EnQueue(Q,T);/入队操作入队操作 while(!QueueEempty(Q)/队列非空队列非空 DeQueue(Q,p);/出队操作出队操作 printf(p-data);if(p-lchild)EnQueue(Q,p-lchild);/左孩子入队

25、左孩子入队 if(p-rchild)Enqueue(Q,p-rchild);/右孩子入队右孩子入队 return OK;二叉树按层次遍历的算法ADBC第48页/共104页v二叉树遍历算法的应用l按先序遍历序列建立二叉树的二叉链表，已知先序序列为：A B C#D E#G#F#ABCDEFG A B C D E F G 第49页/共104页l按先序遍历序列建立二叉树的二叉链表算法Status CreateBT(BiTree&T)scanf(“%c”,&ch);if(ch=#)T=NULL;else if (!(T=(BiTNode*)malloc(sizeof(BiTNode)exit(OVERF

26、LOW);T-data=ch;CreateBT(T-lchild);CreateBT(T-rchild);return OK;ABCDEFG思考：思考：1.如何输入？如何输入？2.能否中序建树和后序建树？能否中序建树和后序建树？第50页/共104页v二叉树遍历算法的典型应用l求二叉树深度算法l统计二叉树中叶子结点个数算法l求二叉树结点总数算法ABCDEFG第51页/共104页1编写程序任意输入二叉树的结点个数和结点值，构编写程序任意输入二叉树的结点个数和结点值，构造一棵二叉树，采用三种递归遍历算法造一棵二叉树，采用三种递归遍历算法(前序、中序、前序、中序、后序后序)对这棵二叉树进行遍历并计算出

27、二叉树的高度。对这棵二叉树进行遍历并计算出二叉树的高度。2编写程序生成下面所示的二叉树，并采用中序遍历编写程序生成下面所示的二叉树，并采用中序遍历的非递归算法对此二叉树进行遍历。的非递归算法对此二叉树进行遍历。上机上机作业作业55二叉树的建立及遍历（二叉树的建立及遍历（2 2学学时）时）能力培养：学会利用递归方法编写对二叉树这种能力培养：学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。在栈的基本操递归数据结构进行处理的算法。在栈的基本操作支撑下，验证非递归算法。作支撑下，验证非递归算法。PracticeEngineering第52页/共104页二、线索二叉树(Threaded Bi

28、nary Tree)v定义：l前驱与后继：在二叉树的先序、中序或后序遍历序列中两个相邻的结点互称为l线索：指向结点前驱或后继的指针称为l线索二叉树：加上线索的二叉链表表示的二叉树叫l线索化：对二叉树按某种次序遍历使其变为线索二叉树的过程叫v实现l在有n个结点的二叉链表中必定有n+1个空链域l在线索二叉树的结点中增加两个标志域LTag和RTaguLTag:若标志为0,lc 域指向左孩子;若标志为1,lc域指向其前驱uRTag:若标志为0,rc 域指向右孩子;若标志为1,rc域指向其后继l结点定义：typedef struct BiThrNode TElemType data;int ltag,r

29、tag;struct BiThrNode*lc,*rc;BiThrNode;lc lt data rt rc第53页/共104页ABCDE A B D C ET先序序列：ABCDE先序线索二叉树00001111 11第54页/共104页ABCDE A B D C ET中序序列：BCAED中序线索二叉树0000111111第55页/共104页ABCDE A B D C ET后序序列：CBEDA后序线索二叉树0000111111第56页/共104页6.4 树和森林一、树的存储结构1、双亲表示法实现：定义结构数组存放树的结点，每个结点含两个域数据域：存放结点本身信息双亲域：指示本结点的双亲结点在数组

30、中位置特点：找双亲容易，找孩子难typedef struct PTNode TElemType data;int parent;PTNode;PTNode tM;第57页/共104页abcdefhgiacdefghib012235551096012345789dataparent0号单元不用或存结点个数如何找孩子结点第58页/共104页2、孩子表示法多重链表：每个结点有多个指针域，分别指向其子树的根结点同构：结点的指针个数相等，为树的度D结点不同构：结点指针个数不等，为该结点的度ddata child1 child2 .childDdata degree child1 child2 .chil

31、ddl孩子链表：每个结点的孩子结点用单链表存储，再用含n个元素的结构数组指向每个孩子链表孩子结点：typedef struct CTNode int child;/该结点在表头数组中下标 struct CTNode *next;/指向下一孩子结点 *ChildPtr;表头结点：typedef struct TElemType data;/数据域 ChildPtr firstchild;/指向第一个孩子结点 CTBox;CTBox tM;/t0不用第59页/共104页abcdefhgi6012345789acdefghibdatafc 2 3 4 5 9 7 8 6如何找双亲结点第60页/共10

32、4页l带双亲的孩子链表612345789acdefghibdatafc 2 3 4 5 9 7 8 6012235551parentabcdefhgi第61页/共104页3、孩子兄弟表示法（二叉树表示法）实现：用二叉链表作树的存储结构，链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点特点操作容易破坏了树的层次typedef struct CSNode ElemType data;struct CSNode *fch,*nsib;CSNode;abcdefhgi a b c d e f g h i第62页/共104页二、树与二叉树转换ACBED树ABCDE二叉树 A B C D

33、 E A B C D E A B C D E 对应存储存储解释解释第63页/共104页v树转换成二叉树l加线：在所有兄弟结点之间连一条线；l抹线：对每个结点，除了保留与其长子的连线外，去除该结点与其余孩子之间的连线；l旋转：以树的根结点为轴心，将整树顺时针转45即可。ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI注意：树转换成的二叉树其右子树一定为空第64页/共104页森林转换成二叉树将森林中的各棵树分别转换成二叉树将每棵树的根结点视为兄弟从左至右用线相连在一起将第一棵树的根结点视为二叉树的根，再以该根结点为轴心，顺时针旋转，构成二叉树型结构ABCD

34、EFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ第65页/共104页v将二叉树转换成树或森林l加线：若某结点p是其双亲结点的左孩子，则将结点p的右孩子，右孩子的右孩子，沿分支找到的所有右孩子，都与结点p的双亲结点用线连起来；l抹线：抹掉原二叉树中所有双亲与右孩子之间的连线；l调整：将结点按层次排列，形成树或森林结构。ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI例：二叉树转换成树第66页/共104页例：二叉树转换成森林ABCDEFGHIJABCDEFGHIJABCDEFGHIJ第67页/共104页 三、树和森林的遍历树的遍历遍

35、历按一定规律走遍树的各个结点，且使每一结点仅被访问一次，即找一个完整而有规律的走法，以得到树中所有结点的一个线性排列。常用方法先根（次序）遍历树：先访问树的根结点，然后依次先根遍历根的每棵子树；先根遍历树等价于先根遍历该树对应的二叉树！后根（次序）遍历树：先依次后根遍历每棵子树，然后访问根结点；后根遍历树等价于中根遍历该树对应的二叉树！按层次遍历：先访问第一层上的结点，然后依次遍历第二层，第n层的结点。第68页/共104页先根遍历结果：先根遍历结果：A B EFI G DABDEFGI第69页/共104页ABDEFGI后根遍历结果：后根遍历结果：E I F GB D A第70页/共104页AB

36、CDEFGHIJKLMNO先序遍历：后序遍历：层次遍历：ABE F I GCDHJ KL NOME I F G B C J K N O L M H D AAB C DE F GH I J KL MNOABCDEFGHIJKLMNO第71页/共104页森林的遍历两种遍历方法先序遍历森林：若森林非空,则可按下述规则遍历之：访问森林中第一棵树的根结点；先序遍历第一棵树中根结点的子树森林；先序遍历除去第一棵树之后剩余的树构成的森林。先序遍历森林等价于先序遍历该森林对应的二叉树！中序遍历森林：若森林非空,则可按下述规则遍历之：中序遍历森林中第一棵树的根结点的子树森林；访问第一棵树的根结点；中序遍历除去第

37、一棵树之后剩余的树构成的森林。中序遍历森林等价于中序遍历该森林对应的二叉树！第72页/共104页先序遍历：中序遍历：ABCDE F G H I JBC DAF E H J I GABCDEFGHIJ第73页/共104页二叉树的典型应用平衡树排序树字典树判定树带权树最优树由字符串构成的二叉排序树特点：分支查找树（例如1212个球如何只称3 3次便分出轻重）特点：路径带权值（例如长度）是带权路径长度最短的树，又称 HuffmanHuffman树，用途之一是通信中的压缩编码。特点：所有结点左右子树深度差的绝对值1 1特点：所有结点“左小右大”第74页/共104页6.6哈夫曼树及其应用问题的提出：在通

38、信系统中，要发送由A，B，C，D四个字符组成的信息，A出现的概率为0.5，B出现的概率为0.25，C出现的概率为0.1，D出现的概率为0.15。如何对A、B、C、D 四个字符进行编码，能使总的编码长度最短？思路第75页/共104页另一种编码方案类似38译码器第76页/共104页第二种编码方案优于第一种编码方案第二种编码方案优于第一种编码方案是否有规律可循？第77页/共104页最优二叉树（哈夫曼树）定义结点之间的路径：由树中一个结点到另一个结点之间的分支构成路径长度：路径上的分支数目称做树的路径长度：从树根到每一个结点的路径长度之和叶子结点的带权路径长度：从该结点到树根之间的路径长度lk与结点上

39、的权值Wk的乘积 lk*wk树的带权路径长度：树中所有叶子结点的带权路径长度之和lHuffman树(最优二叉树)设有n个权值w1,w2,wn，构造一棵有n个叶子结点的二叉树，每个叶子的权值为wi，则WPL最小的二叉树叫debacf gWeighted Path LengthHuffman常译为赫夫曼、霍夫曼、哈夫曼等带权路径长度最短的树第78页/共104页a(00)b(01)c(10)d(11)电报码长为电报码长为 34=2*(7+5+2+3)a(010)b(011)c(1)d(00)电报码长为电报码长为 44=3*(7+5)+1*2+2*3a(0)b(10)c(110)d(111)电报码长为

40、电报码长为 32=1*7+2*5+3*(2+3)735201010175230101017523010101例1 1：电文总长为1717个字符，电文由a a、b b、c c、d d四个字符构成，其每个字符出现的次数分别为（7 7、5 5、2 2、3 3），制定各字符的编码。第79页/共104页构造Huffman树的方法Huffman算法（是贪心算法(Greedy Algorithm)的一个例子）根据给定的n个权值w1,w2,wn，构造n棵只有根结点的二叉树，令其权值为wj；在森林中选取两棵根结点权值最小的树作为左、右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左、右子树根结点权值之和；在

41、森林中删除这两棵选过的树，同时将新得到的二叉树加入森林中；重复上述两步，直到只含一棵树为止，这就是哈夫曼树。第80页/共104页a7b5c2d4a7b5c2d46a7b5c2d4611a7b5c2d461118例例2 2：有：有4 4个结点，权值分别为个结点，权值分别为7 7，5 5，2 2，4 4，构造一棵哈夫曼树。，构造一棵哈夫曼树。WPL=7*1+5*2+2*3+4*3=35第81页/共104页例例3：w=5,29,7,8,14,23,3,11，构造哈夫曼树。构造哈夫曼树。51429782331114297823 1135887151429233581111358191429238715

42、113581929 23148715292914871529113581923421135819234229148715295811358192342291487152958100WPL=(23+29)*2+(11+14)*3+(3+5+7+8)*4=271第82页/共104页哈夫曼树的特点特点1：哈夫曼树是严格的二叉树，即哈夫曼树中没有度为1的结点。特点2：若给定权值的叶子结点个数为n，则所构造的哈夫曼树中的结点数是2n1。特点3：通过给定权值的叶子构造一棵哈夫曼树，其哈夫曼树的形态不唯一，但带权路径长度WPL值一定。特点4：任一棵哈夫曼树的带权路径长度等于所有分支结点值的累加和。特点4：哈

43、夫曼树是一类带权路径长度最短的树。注意：注意：对于结点个数相同的二叉树，对于结点个数相同的二叉树，完全二叉树是路径长度最短的二叉树。完全二叉树是路径长度最短的二叉树。注意：注意：完全二叉树不一定是哈夫曼树，完全二叉树不一定是哈夫曼树，哈夫曼树有时可能是完全二叉树。哈夫曼树有时可能是完全二叉树。debacf g第83页/共104页vHuffman树应用最佳判定树等级分数段比例ABCDE05960697079 8089 901000.050.150.400.300.10a60a90a80a70EYNDYNCYNBYNA70a80a60CYNBYNDYNEYNA80a9060a70EADBCa80a

44、70a60a90EYNDYNCYNBYNA第84页/共104页哈夫曼编码哈夫曼编码v编码的定义：将文件中的每个字符均转换为编码的定义：将文件中的每个字符均转换为一个惟一的二进制串一个惟一的二进制串等长编码（例）：优点易于翻译，缺点利用等长编码（例）：优点易于翻译，缺点利用率不高率不高不等长编码（不等长编码（例）：优点存储容量例）：优点存储容量 小，缺点小，缺点不易翻译，不好断句不易翻译，不好断句v前缀编码：设计长短不等的编码，任一字符前缀编码：设计长短不等的编码，任一字符的编码都不是另一个字符的编码的前缀。的编码都不是另一个字符的编码的前缀。最优前缀编码（赫夫曼编码）：平均码长最最优前缀编码（

45、赫夫曼编码）：平均码长最小的前缀编码。由赫夫曼树求得最优前缀码。小的前缀编码。由赫夫曼树求得最优前缀码。第85页/共104页lHuffman编码：数据通信用的二进制编码u思想：根据字符出现频率编码，使电文总长最短u编码：根据字符出现频率构造Huffman树，然后将树中结点引向其左孩子的分支标“0”，引向其右孩子的分支标“1”；每个字符的编码即为从根到每个叶子的路径上得到的0、1序列例：要传输的字符集 D=C,A,S,T,;字符出现频率 w=2,4,2,3,3CS3364224814T;A00110110T:00;:01A:10C:110S:111 前缀编码方式，能实现一组指定出现频率字符编码长

46、度之和最小。总编码长度：2*3+4*2+2*3+3*2+3*2=32，若等长编码，则总编码长度为（2+4+2+3+3）*3=42第86页/共104页u译码：从Huffman树根开始，从待译码电文中逐位取码。若编码是“0”，则向左走；若编码是“1”，则向右走，一旦到达叶子结点，则译出一个字符；再重新从根出发，直到电文结束。例：电文是CAS;CAT;SAT;AT 其编码 “11010111011101000011111000011000”电文为“1101000”译文只能是“CAT”CS3364224814T;A00110110T:00;:01A:10C:110S:111第87页/共104页哈夫曼树

47、的构造算法哈夫曼树的构造算法weightparentlchildrchild判定结点是否判定结点是否已加入已加入设置一个结构体数组设置一个结构体数组HuffNodeHuffNode保存赫夫曼树保存赫夫曼树中各结点的信息。数组大小设置为中各结点的信息。数组大小设置为2 2n-1n-1。typedef structunsigned int weight;unsigned int parent,lchild,rchild;HTNode,*HuffmanTree;/动态分配数组存储HTtypedef char*HuffmanCode;/动态分配数组存储HTCode第88页/共104页哈夫曼树的构造算法

48、哈夫曼树的构造算法将由将由n个字符形成的个字符形成的n个叶结点存放到数组个叶结点存放到数组HuffNodeHuffNode的前的前n n个分量中。个分量中。根据构造赫夫曼树的方法，不断地将两个小子树根据构造赫夫曼树的方法，不断地将两个小子树合并为较大的子树，每次构成的新子树的根结点合并为较大的子树，每次构成的新子树的根结点顺序放入顺序放入HuffNodeHuffNode数组中的前数组中的前n n个分量后面。个分量后面。第89页/共104页【例例】设权设权w=5，29，7，8，14，23，3，11，构造，构造HT下标下标weightparentlchildrchild15000229000370

49、0048000514000623000730008110009-00010-00011-00012-00013-00014-00015-000第90页/共104页【例例】设权设权w=5，29，7，8，14，23，3，11，构造，构造HT下标下标weightparentlchildrchild159002290003700048000514000623000739008110009807110-00011-00012-00013-00014-00015-000第91页/共104页【例例】设权设权w=5，29，7，8，14，23，3，11，构造，构造HT下标下标weightparentlchild

50、rchild159002290003710004810005140006230007390081100098071101503411-00012-00013-00014-00015-000第92页/共104页【例例】设权设权w=5，29，7，8，14，23，3，11，构造，构造HT下标下标weightparentlchildrchild159002290003710004810005140006230007390081111009811711015034111909812-00013-00014-00015-000第93页/共104页【例例】设权设权w=5，29，7，8，14，23，3，11，