第五章 树优秀PPT.ppt

《第五章 树优秀PPT.ppt》由会员分享，可在线阅读，更多相关《第五章 树优秀PPT.ppt（65页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第五章 树第一页，本课件共有65页树形结构树形结构全校学生档案管理的组织方式全校学生档案管理的组织方式现实世界中，能用树的结构表示的例子：现实世界中，能用树的结构表示的例子：学校的行政关系、书的层次结构、人类的家族血缘关系等。学校的行政关系、书的层次结构、人类的家族血缘关系等。2022/12/62第二页，本课件共有65页ABCDEFGH树形结构 结点间具有分层次的连接关系HBCDEFGA2022/12/63第三页，本课件共有65页由一个或多个结点组成的有限集合由一个或多个结点组成的有限集合。仅有一个根结点，结点间有仅有一个根结点，结点间有明显的层次结构关系。除根结点外明显的层次结构关系。除根结

2、点外,其余结点又可构成其余结点又可构成互不相交若干个子树若干个子树.ACGT2DHIT3JMBELKT1F5.1树的定义：树的定义：2022/12/64第四页，本课件共有65页空树E F G H I J B C DAA只有一个根结点的树K L M树的若干形式：树的若干形式：一棵树结构非树结构2022/12/65第五页，本课件共有65页B C D AE F G H I JK LMT1 T2T3基本术语：基本术语：结点的度：子树的个数。叶结点：度为0的结点。分枝结点：度不为0的结点。左孩子、右孩子、双亲路径、路径长度祖先、子孙 结点的层数：树中根结点的层次为1，根结点子树的根为第2层，以此类推。树

3、的深度：树中所有结点层次的最大值。树的度：树中所有结点度的最大值。2022/12/66第六页，本课件共有65页n(1)Initiate(t）初始化一棵树）初始化一棵树t;n(2)Root(x）求结点）求结点x所在树的根结点；所在树的根结点；n(3)Parent(t,x）求树）求树t中结点中结点x的双亲结点；的双亲结点；n(4)Child(t,x,i)求树求树t中结点中结点x的第的第i个孩子结点；个孩子结点；n(5)RightSibling（t，x）求树求树t中结点中结点x的第一个右边兄弟的第一个右边兄弟结点结点n(6)Insert(t,x,i,s）把以）把以S为结点的树插人到树为结点的树插人到

4、树t中作中作为结为结点点x的第的第i棵子树棵子树n(7)Delete(t,x,i）在树）在树t中删除结点中删除结点x的第的第i棵子树；棵子树；5.1.3树的基本操作树的基本操作2022/12/67第七页，本课件共有65页1、二叉树的定义和基本操作、二叉树的定义和基本操作(1)二叉树的定义二叉树的定义二叉树的五种基本形态二叉树的五种基本形态二叉数是二叉数是n(n=0)个结点的有限集合。它或为空数个结点的有限集合。它或为空数(n=0),或由一或由一个根结点和两棵分别称为根的左子树和右子树的互不相交的个根结点和两棵分别称为根的左子树和右子树的互不相交的二叉数组成二叉数组成,子树间有子树间有次序关系次

5、序关系。二叉树的基本形态有下图：。二叉树的基本形态有下图：空二叉树空二叉树仅有仅有根结点根结点右子树右子树为空为空左子树左子树为空为空左右子树左右子树均非空均非空5.2二叉树二叉树2022/12/68第八页，本课件共有65页 特别要注意：特别要注意：二叉数不是树的特殊情况。是一二叉数不是树的特殊情况。是一类类与树不同的树形结构与树不同的树形结构.a aa ab bb b两棵不同的二叉数两棵不同的二叉数2022/12/69第九页，本课件共有65页满二叉树满二叉树423167891011121314155特点：特点：是一棵二叉树是一棵二叉树所有叶子结点都在同一层，所有叶子结点都在同一层，除叶子结点

6、外其余结点的度都为除叶子结点外其余结点的度都为2 2。2022/12/610第十页，本课件共有65页4231678910 11125 非完全二叉树非完全二叉树完全二叉树完全二叉树4231678910 11125 完全二叉树完全二叉树在一棵深度为在一棵深度为K K的满二叉树上删去第的满二叉树上删去第K K层上层上最右最右边起的连续边起的连续j j个结点，就得到深度为个结点，就得到深度为K K的完全二叉的完全二叉树。树。满二叉树也是完全二叉树满二叉树也是完全二叉树,但完全二叉树未必但完全二叉树未必是满二叉树。是满二叉树。2022/12/611第十一页，本课件共有65页树与二叉树的区别树与二叉树的区

7、别树中结点的最大度数没有限制，二叉树结点最大度数为树中结点的最大度数没有限制，二叉树结点最大度数为2。树树的的结结点点子子树树无无左左、右右之之分分，二二叉叉树树的的结结点点子子树树有有明明确确的的左左、右右之分。之分。二二叉叉树树树树2022/12/612第十二页，本课件共有65页性质性质1、二叉树的第i层上至多有2 i-1（i 1）个结点。二叉树的基本性质二叉树的基本性质423167891011121314155第三层上第三层上(i=3)(i=3)，有，有2 23-13-1=4=4个节点。个节点。第四层上第四层上(i=4)(i=4)，有，有2 24-14-1=8=8个节点。个节点。2022

8、/12/613第十三页，本课件共有65页性质性质2、深度为k的二叉树中至多含有2k -1个结点。423167891011121314155此树的深度此树的深度k=4k=4，共有，共有2 24 4-1=15-1=15个节点。个节点。二叉树的基本性质二叉树的基本性质2022/12/614第十四页，本课件共有65页性质性质性质性质3 3：对于任意一棵二叉树BT，如果度为0的结点个数为n0，度为2的结点个数为n2，则n0=n2+1。证明：假设度为1的结点个数为n1，结点总数为n，B为二叉树中的分支数。因为在二叉树中，所有结点的度均小于或等于2，所以结点总数为：n=n0+n1+n2 （1）再查看一下分支

9、数。在二叉树中，除根结点之外，每个结点都有一个从上向下的分支指向，所以，总的结点个数n与分支数B之间的关系为：Bn-1。二叉树的基本性质二叉树的基本性质2022/12/615第十五页，本课件共有65页又因为在二叉树中，度为1的结点产生1个分支，度为2的结点产生2个分支，所以分支数B可以表示为：B=n1+2n2。将此式代入上式，得：n=n1+2n2+1 （2）用（1）式n=n0+n1+n2减去（2）式，并经过调整后得到：n0=n2+1。二叉树的基本性质二叉树的基本性质2022/12/616第十六页，本课件共有65页若在任意一棵二叉树中，有n0个叶子结点，有n2个度为2的结点，则：n0=n2+14

10、23167891011121314155n n0 0=8=8n n2 2=7=7二叉树的基本性质二叉树的基本性质2022/12/617第十七页，本课件共有65页 性质性质4：具有n个结点的完全二叉树的深度为 log2n+1。其中，log2n 的结果是不大于log2n的最大整数。2k-1-1n=2k-1对不等式取对数对不等式取对数有有:K-1=log2nn，则结点i没有左孩子；否则其左孩子结点的编号为2i。n（3）如果2i+1n，则结点i没有右孩子；否则其右孩子结点的编号为2i+1。二叉树的基本性质二叉树的基本性质2022/12/619第十九页，本课件共有65页如果i=1，则结点i是这棵完全二叉

11、树的根如果2in，则结点i没有左孩子111234567891012如果2i+1n，则结点i没有右孩子对一棵对一棵完全完全二叉树：二叉树：二叉树的基本性质二叉树的基本性质2022/12/620第二十页，本课件共有65页5.2.3二叉树的存储二叉树的存储二二叉叉树树的的顺顺序序存存储储:按按二二叉叉树树从从左左到到右右、从从上到下的顺序存储。上到下的顺序存储。一一般般以以完完全全二二叉叉树树和和满满二二叉叉树树采采用用顺顺序序存存储储比比较较合合适适。数数组组下下标标序序号号可可以以惟惟一一反反映映出结点间的逻辑关系。出结点间的逻辑关系。对对非非完完全全二二叉叉树树，则则通通过过添添加加虚虚拟拟结

12、结点点构构造出完全二叉树后进行顺序存储。造出完全二叉树后进行顺序存储。1.顺序存储顺序存储2022/12/621第二十一页，本课件共有65页(2)链式存储结构链式存储结构若父结点在数组中若父结点在数组中i下标处，其左孩子在下标处，其左孩子在2*i处，右孩子在处，右孩子在2*i+1处。处。(1)顺序存储结构顺序存储结构1.顺序存储结构顺序存储结构2h-1=24-1=15用用一一组组连连续续的的存存储储单单元元存存放放二二叉叉树树的的数数据据元元素素。结结点点在在数数组组中中的的相相对对位位置置蕴蕴含含着着结结点点之之间间的的关关系。系。一般二叉树必须按完全二叉树的形式存储，将造成存储的浪费。一般

13、二叉树必须按完全二叉树的形式存储，将造成存储的浪费。二叉树的存储结构二叉树的存储结构1 2 3 4 4 6 7 8 9 10 11 12 13 12 34 5 6 78 9 10 11 12 132022/12/622第二十二页，本课件共有65页二叉树的顺序存储表示可描述为：二叉树的顺序存储表示可描述为：#defineMAXNODE100/*二二叉叉树树的的最最大大结点数结点数*/typedefelemtypeSqBiTreeMAXNODE/*0号单元存放根结点号单元存放根结点*/SqBiTreebt;即将即将btbt定义为含有定义为含有MAXNODEMAXNODE个个elemtypeelem

14、type类型类型元素的一维数组元素的一维数组。2022/12/623第二十三页，本课件共有65页n2.链式存储结构n 在顺序存储结构中，利用编号表示元素的位置及元素之间孩子或双亲的关系，因此对于非完全二叉树，需要将空缺的位置用特定的符号填补，若空缺结点较多，势必造成空间利用率的下降。在这种情况下，就应该考虑使用链式存储结构。n 常见的二叉树结点结构如下所示：LchildDataRchild2022/12/624第二十四页，本课件共有65页 其中，Lchild和Rchild是分别指向该结点左孩子和右孩子的指针，Data是数据元素的内容。在C语言中的类型定义为：typedef struct BiT

15、Node elemtype data;struct BiTNode*lchild;*rchild;/*左右孩子指针*/BiTNode,*BiTree;下面是一棵二叉树及相应的链式存储结构。2022/12/625第二十五页，本课件共有65页2.二叉链式存储结构二叉链式存储结构lchildDatarchild每个结点由数据域、左指针域和右指针域组成。每个结点由数据域、左指针域和右指针域组成。二叉链式存储结构为：2022/12/626第二十六页，本课件共有65页三叉链式存储结构三叉链式存储结构每个结点由数据域、左指针域和右指针域和指向父亲结每个结点由数据域、左指针域和右指针域和指向父亲结点的指针组成

16、。点的指针组成。三叉链式存储结构为：2022/12/627第二十七页，本课件共有65页Initiate（bt）建立一棵空二叉树。建立一棵空二叉树。Create（x，lbt，rbt）生成一棵以生成一棵以x为根结点的数据域信息，以二为根结点的数据域信息，以二叉树叉树lbt和和rbt为左子树和右子树的二叉树。为左子树和右子树的二叉树。InsertL（bt，x，parent）将数据域信息为将数据域信息为x的结点插入到二叉的结点插入到二叉树树bt中作为结点中作为结点parent的左孩子结点。如果结点的左孩子结点。如果结点parent原来有左原来有左孩子结点，则将结点孩子结点，则将结点parent原来的左

17、孩子结点作为结点原来的左孩子结点作为结点x的左孩子结的左孩子结点。点。InsertR（bt，x，parent）将数据域信息为将数据域信息为x的结点插入到二叉的结点插入到二叉树树bt中作为结点中作为结点parent的右孩子结点。的右孩子结点。DeleteL（bt，parent）在二叉树）在二叉树bt中删除结点中删除结点parent的左子树。的左子树。DeleteR（bt，parent）在二叉树）在二叉树bt中删除结点中删除结点parent的右子树。的右子树。Search（bt，x）在二叉树在二叉树bt中查找数据元素中查找数据元素x。Traverse（bt）按某种方式遍历二叉树按某种方式遍历二叉树

18、bt的全部结点。的全部结点。5.2.4二叉树基本操作的算法实现二叉树基本操作的算法实现2022/12/628第二十八页，本课件共有65页（1）二叉树是一种非线性的数据结构，在对它进行操作时，总是需要逐一对每个数据元素实施操作，这样就存在一个操作顺序问题，由此提出了二叉树的遍历操作。所谓遍历二叉树就是按某种顺序访问二叉树中的每个结点一次且仅一次的过程。这里的访问可以是输出、比较、更新、查看元素内容等等各种操作。n二叉树的遍历方式分为两大类：一类按根、左子树和右子树三个部分进行访问；另一类按层次访问。下面我们将分别进行讨论。5.2.5遍历二叉树遍历二叉树2022/12/629第二十九页，本课件共有

19、65页（1）先序遍历若二叉树为空，则结束遍历操作；否则n访问根结点；n先序遍历左子树；n先序遍历右子树。二叉树的遍历二叉树的遍历按根、左子树和右子树三部分进行遍历.根据根访问的位置不同分别被称为:先序遍历TLR 中序遍历LTR 后序遍历LRT。递归算法如下：void PreOrder（BiTree bt）if(bt=NULL)return;Visite（bt-data）;PreOrder（bt-lchild）;PreOrder（bt-rchild）;2022/12/630第三十页，本课件共有65页（3）后序遍历若二叉树为空，则结束遍历操作；否则n后序遍历左子树；n后序遍历右子树；n访问根结点。

20、（2）中序遍历若二叉树为空，则结束遍历操作；否则 中序遍历左子树；访问根结点；中序遍历右子树。void InOrder（BiTree bt）if(bt=NULL)return;InOrder（bt-lchild）;Visite（bt-data）;InOrder（bt-rchild）;void PostOrder（BiTree bt）if(bt=NULL)return;PostOrder（bt-lchild）;PostOrder（bt-rchild）;Visite（bt-data）;2022/12/631第三十一页，本课件共有65页pre(D R);pre(A R);voidPreOrder（B

21、iTreebt）if(bt=NULL)return;/*递归调用的结束条件递归调用的结束条件*/Visit（bt-data）;PreOrder（bt-lchild）;PreOrder（bt-rchild）;主程序主程序Pre(T)返回返回pre(C R);返回返回ACBDTBprintf(B);pre(B L);BTAprintf(A);pre(A L);ATDprintf(D);pre(D L);DTCprintf(C);pre(C L);C返回T左是空返回左是空返回pre(B R);T左是空返回左是空返回T右是空返回右是空返回T左是空返回左是空返回T右是空返回右是空返回2022/12/63

22、2第三十二页，本课件共有65页void InOrder（BiTree bt）if(bt=NULL)return;InOrder（bt-lchild）;Visit（bt-data）;InOrder（bt-rchild）;遍历顺序为:BDACpre(D L);pre(B R);pre(A L);主程序主程序InOrder(T)printf(A);返回Dpre(A R);BADC返回Tpre(B L);printf(B);printf(D);返回Dpre(D R);返回Tpre(C L);printf(C);pre(C R);返回T2022/12/633第三十三页，本课件共有65页(4)层次编历层次

23、编历二叉树的层次遍历(Level-Order Traversal)，是指从二叉树的第一层（根结点）开始，从上至下逐层遍历，在同一层中，则按从左到右的顺序对结点逐个访问。如下图,按层次编历结果序列为:ABCDEFG.编历算法编历算法:设置一个队列结构，遍历从二叉树的根结点开始，首先将根结点指针入队列，然后从对头取出一个元素，每取一个元素，执行下面两个操作：访问该元素所指结点；若该元素所指结点的左、右孩子结点非空，则将该元素所指结点的左孩子指针和右孩子指针顺序入队。此过程不断进行，当队列为空时，二叉树的层次遍历结束。2022/12/634第三十四页，本课件共有65页第一次经过的第一次经过的区间区间

24、第二次经过的区间第二次经过的区间第三次经过第三次经过的区间的区间将二叉树通过补充虚拟的左孩子右孩子，构造成满二叉树。将每一个结点划分为如下三个区间：5.2.6二叉树遍历的非递归实现二叉树遍历的非递归实现-栈结构实现栈结构实现2022/12/635第三十五页，本课件共有65页n则任何一棵二叉树都可以将它的外部轮廓用一条线绘制出来，我们将它称为二叉树的包线，这条包线对于理解二叉树的遍历过程很有用。G HD E FB CA二叉树遍历的非递归实现二叉树遍历的非递归实现-栈结构实现栈结构实现2022/12/636第三十六页，本课件共有65页n沿着包线第一次经过时记录的结点序列称为先序遍历序列，n沿着包线

25、第二次经过进记录的结点序列称为中序遍历序列；n沿着包线第三次经过时记录的序列称为后序遍历序列；二叉树遍历的非递归实现二叉树遍历的非递归实现-栈结构实现栈结构实现2022/12/637第三十七页，本课件共有65页G HD E FB CA先序序列：先序序列：ABDGCEFH中序序列：中序序列：DGBAECHF后序序列：后序序列：GDBEHFCA二叉树遍历的非递归实现二叉树遍历的非递归实现-栈结构实现栈结构实现2022/12/638第三十八页，本课件共有65页已知结点的前序和中序遍历，求二叉树：前序序列为：A B C D E F G中序序列为：C B E D A F GABCDEFG由中序遍历有BD

26、EC由前序遍历确定结点BCDE中B为根结点,再由中序遍历得到上图DE由前序遍历确定结点 DE中 D为根结点,再由中序遍历可知E为D的左子树由前序遍历确定结点 DE中 D为根结点,再由中序遍历可知E为D的左子树FG5.2.7由遍历序列恢复二叉树由遍历序列恢复二叉树2022/12/639第三十九页，本课件共有65页5.35.3 树和森林n5.3.1树的表示直观表示法嵌套表示法广义表示法凹入表示法2022/12/640第四十页，本课件共有65页1.双亲表示：以一组连续空间存储树的结点，同时双亲表示：以一组连续空间存储树的结点，同时在结点中附设一个指针，存放双亲结点在链表中的在结点中附设一个指针，存放

27、双亲结点在链表中的位置。位置。双亲表示法5.3.2 树的存储结构1.双亲表示法2022/12/641第四十一页，本课件共有65页双亲表示法定义：#define MAXNODE typedef struct elemtype data;int parent;NodeType;NodeType tMAXNODE;这种存储方法的特点是寻找结点的双亲很容易，但寻找结点的孩子比较困难。2022/12/642第四十二页，本课件共有65页n孩子表示法主要描述的是结点的孩子关系。由于每个结点的孩子个数不定，所以利用链式存储结构更加适宜。n结点的指针域个数的设置有两种方法：每个结点指针域的个数等于该结点的度数；

28、每个结点指针域的个数等于树的度数。结点指针域的个数以树的度数设置为例：2.2.孩子表示法孩子表示法2022/12/643第四十三页，本课件共有65页对于左图，树的度为3，则结点的指针域的个数为3孩子表示法孩子表示法-多重链表表示法多重链表表示法2.孩子表示法孩子表示法-多重链表表示法多重链表表示法2022/12/644第四十四页，本课件共有65页2.孩子表示法孩子表示法-孩子链表表示法孩子链表表示法2022/12/645第四十五页，本课件共有65页孩子链表表示法孩子链表表示法存储形式定义如下：#define MAXNODE typedef struct ChildNodeint childco

29、de;struct ChildNode*nextchild;typedef struct elemtype data;struct ChildNode*firstchild;NodeType;NodeType tMAXNODE;2022/12/646第四十六页，本课件共有65页3.双亲表示法双亲孩子表示法2022/12/647第四十七页，本课件共有65页n这是一种常用的存储结构。其方法是这样的：在树中，每个结点除其信息域外，再增加两个分别指向该结点的第一个孩子结点和下一个兄弟结点的指针。在这种存储结构下，树中结点的存储表示可描述为：typedef struct TreeNode elemtyp

30、e data;struct TreeNode *son;struct TreeNode *next;NodeType;n sondatanext指向孩指向孩子结点子结点指向兄指向兄弟结点弟结点4.孩子兄弟表示法 2022/12/648第四十八页，本课件共有65页孩子兄弟表示法4.孩子兄弟表示法 2022/12/649第四十九页，本课件共有65页5.3.3树、森林与二叉树的转换树、森林与二叉树的转换n1.树转换成二叉树n 将一棵树转换成二叉树的方法：对每个孩子进行从左到右的排序；在兄弟之间加一条连线；对每个结点，除了第一个孩子外，去除其与其余孩子之间的联系；以根结点为轴心，将整个树顺时针转一定角

31、度。特点：一棵树转换成二叉树后，根结点没有右孩子。2022/12/650第五十页，本课件共有65页 I A B C DE F G H(b)A B CD E G H FI(a)树转换为二叉树树转换为二叉树ABEFCDGHI(d)ABCDEFGHI(c)2022/12/651第五十一页，本课件共有65页n将森林转换成二叉树的方法与一棵树转换成二叉树的方法类似，只是把森林中所有树的根结点看作兄弟关系，并对其中的每棵树依次地进行转换。方法：n将各棵树分别转成二叉树；n把每棵树的根结点用线连起来；n以第一棵树的根结点作为二叉树的根结点，按顺时针方向旋转。（2）森林转换为一棵二叉树森林转换为一棵二叉树20

32、22/12/652第五十二页，本课件共有65页（2）森林转换为二叉树森林转换为二叉树ADCBEFHIGJEFADCBHIGJADCBEFHIGJADCBEFHIGJ方法：方法：将各棵树分别转成二叉树；将各棵树分别转成二叉树；把把每每棵棵树树的的根根结结点点用用线线连连起起来来,将将后后一一棵棵二二叉叉树树的的根根结结点点作作为为前前一一棵棵二二叉树的右子树；叉树的右子树；以以第第一一棵棵树树的的根根结结点点作作为为二二叉叉树树的的根根结点，按顺时针方向旋转。结点，按顺时针方向旋转。2022/12/653第五十三页，本课件共有65页将二叉树转换成树或森林的方法如下：1.若某结点是其双亲的左孩子左

33、孩子,则把该结点的右孩子、右孩子的右孩子都与该结点的双亲双亲结点用线连起来;2.删除原二叉树中所有的双亲结点与右孩子结点的连线.3.整理步骤1、2所得到的树或森林,使结构层次分明.（3）将二叉树转换为树或森林将二叉树转换为树或森林2022/12/654第五十四页，本课件共有65页ABEFCDGHI(a)ABEFCDGHI(b)（3）将二叉树转换为树或森林将二叉树转换为树或森林ABEFCDGHI(c)若某结点是其双亲的左左孩孩子子,则把该结点的右孩子、右孩子的右孩子都与该结点的双双亲亲结点用线连起来;删除原二叉树中所有的双亲结点与右孩子结点的连线.2022/12/655第五十五页，本课件共有65

34、页5.3.4树和森林的遍历树和森林的遍历1树的遍历树的遍历通常有以下两种方式。(1)先根遍历先根遍历先根遍历的定义为：访问根结点；按照从左到右的顺序先根遍历根结点的每一棵子树。按照树的先根遍历的定义，对右图的树进行先根遍历，得到的结果序列为：A B E F C D G(2)后根遍历后根遍历后根遍历的定义为：按照从左到右的顺序后根遍历根结点的每一棵子树。访问根结点；按照树的后根遍历的定义，对右图的树进行后根遍历，得到的结果序列为：E F B C G D A2022/12/656第五十六页，本课件共有65页森林的遍历有前序遍历和中序遍历两种方式。(1)前序遍历前序遍历前序遍历的定义为：访问森林中第

35、一棵树的根结点；前序遍历第一棵树的根结点的子树；前序遍历去掉第一棵树后的子森林。对于右图的森林进行前序遍历，得到的结果序列为：A B C D E F G H J I K(2)中序遍历中序遍历中序遍历的定义为：中序遍历第一棵树的根结点的子树；访问森林中第一棵树的根结点；中序遍历去掉第一棵树后的子森林。对于右图的的森林进行中序遍历，得到的结果序列为：B A D E F C J H K I G2森林的遍历2022/12/657第五十七页，本课件共有65页5.4哈夫曼树和判定树哈夫曼树和判定树n哈哈夫夫曼曼树树定定义义：由由n个个结结点点组组成成二二叉叉树树有有多多种种构构造造方方式式,其其中中加加权

36、权路路径径长长度度最小的二叉树就是哈夫曼树。最小的二叉树就是哈夫曼树。n几个术语几个术语n路径路径：两个结点之间的路径。：两个结点之间的路径。n路径长度：路径上的分支数。路径长度：路径上的分支数。n树的路径长度：从树的根到每一结点的路径长度之和。树的路径长度：从树的根到每一结点的路径长度之和。n结点的权：树中结点的一个有某种意义的实数。结点的权：树中结点的一个有某种意义的实数。n带权路径长度带权路径长度(WPL)从树的根结点到该结点之间的路径从树的根结点到该结点之间的路径长度与该结点上权的乘积称为该结点的带权路径长度。长度与该结点上权的乘积称为该结点的带权路径长度。2022/12/658第五十

37、八页，本课件共有65页树的带权路径长度记作：树的带权路径长度记作：其中：其中：Wk为树中每个叶子结点的权；为树中每个叶子结点的权；Lk为每个叶子结点到根的路径长度。为每个叶子结点到根的路径长度。7524WPL=7*2+5*2+2*2+4*2=36WPL最小的二叉树就称作最优二叉树或哈夫曼树最小的二叉树就称作最优二叉树或哈夫曼树。2022/12/659第五十九页，本课件共有65页1 12 245367WPL=3*1+4*2+6*3+7*3=52树的带权路径长度用树的带权路径长度用WPLWPL表示。表示。共共有有四四个个叶叶子子结结点点,权权值值分分别别为为3、4、6、7，各各对对应应叶子结点的路

38、径长度分别为：叶子结点的路径长度分别为：1、2、3、32022/12/660第六十页，本课件共有65页abcd7524WPL=7*2+5*2+2*2+4*2=36dcab2475WPL=7*3+5*3+2*1+4*2=46abcd7524WPL=7*1+5*2+2*3+4*3=35权植分别为2、4、5、7的叶子结点可构造出如下二叉树，其中加权路径长度最加权路径长度最小的二叉树就是哈夫曼树。小的二叉树就是哈夫曼树。公式：公式：2022/12/661第六十一页，本课件共有65页2、哈夫曼树的构造、哈夫曼树的构造例：给定权值例：给定权值7，5，2，4，构造哈夫曼树。，构造哈夫曼树。675cd(b)1

39、1b57cd(c)18a711cdb5624(d)abcd7524(a)方法：方法：（1）由原始数据生成森林；）由原始数据生成森林；(2)在在森森林林中中选选取取两两棵棵根根结结点点权权值值最最小小的的和和次次小小的的二二叉叉树树作作为为左左右右子子树树构构造造一一棵棵新新的的二二叉叉树树，其其根根结结点点的的权权值值为为左左右右子子树树根根结结点点权权值值之之和和。规规定定左左子子树树根根结结点点的的权权值值小小于于右子树根结点的权值。右子树根结点的权值。（3）将将新新的的二二叉叉树树加加入入到到森森林林F中中，去去除除原原两两棵棵权权值值最最小的树；小的树；（4）重复）重复2、3步骤，直至

40、步骤，直至F中只剩一棵树为止。中只剩一棵树为止。2022/12/662第六十二页，本课件共有65页3、哈夫曼树的应用、哈夫曼树的应用（1）判定树）判定树在解决某些判定问题时，利用哈夫曼树可以得到最佳判在解决某些判定问题时，利用哈夫曼树可以得到最佳判定算法。定算法。例例1将学生百分成绩按分数段分级的程序。将学生百分成绩按分数段分级的程序。若学生成绩分布是均匀的，可用图（若学生成绩分布是均匀的，可用图（a)二叉树结构来实二叉树结构来实现。现。a60a70a80a90不及格不及格中等中等良好良好优秀优秀及格及格YNYNYNYN(a)输入输入10000个数个数据，则需进行据，则需进行31500次比较。

41、次比较。2022/12/663第六十三页，本课件共有65页分数分数0596069707980899099比例比例0.050.150.40.30.1070a80a60及格及格中等中等良好良好80a9060a70不及格不及格优秀优秀YNYYYNNN(b)不及格不及格Ya90a80a70a60优秀优秀中等中等及格及格良好良好YNNN(c)YYY学生成绩分布不是均匀的情况：学生成绩分布不是均匀的情况：以以比比例例数数为为权权构构造造一一棵棵哈哈夫夫曼曼树树，如如（b)判断树所示。判断树所示。再再将将每每一一比比较较框框的的两两次次比比较较改改为为一一次次，可得到（可得到（c)判定树。判定树。输入输入1

42、0000个数个数据，仅需进行据，仅需进行22000次比较。次比较。2022/12/664第六十四页，本课件共有65页146833442200001111T;ACS各字符编码是各字符编码是T；ACS000110110111上述电文编码：上述电文编码：11010111011101000011111000011000方法：方法：（1）用用2，4，2，3，3作作为为叶叶子子结结点点的的权权值值生生成成一一棵棵哈哈夫夫曼曼树树，并将对应权值并将对应权值wi的叶子结点注明对应的字符；的叶子结点注明对应的字符；（2）约定左分支表示字符）约定左分支表示字符“0”，右分支表示字符，右分支表示字符1（3）从从叶叶

43、子子结结点点开开始始，顺顺着着双双亲亲反反推推上上去去，直直到到根根结结点点，路路径径上上的的0或或1连接的序列就是结点对应的字符的二进制编码的连接的序列就是结点对应的字符的二进制编码的逆序逆序。（2）哈夫曼编码哈夫曼编码-利用哈夫曼树构造通讯中电文编码（前缀码）利用哈夫曼树构造通讯中电文编码（前缀码）例例2：要传输的电文是要传输的电文是CAS；CAT；SAT；AT要传输的字符集是要传输的字符集是D=C，A，S，T，；每个字符出现的频率是每个字符出现的频率是W=2，4，2，3，3注意：编码的总长度恰好为哈夫曼树的带权路径长。注意：编码的总长度恰好为哈夫曼树的带权路径长。2022/12/665第六十五页，本课件共有65页