树与二叉树.ppt

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

1、第第3 3章章 树树数据结构:线性结构和非线性结构 线性结构(线性表线性表,栈栈,队列队列等)非线性结构:至少存在一个数据元素有不止一个直接前驱或后继(树,图等)树型结构是一类重要的非线性结构。树型结构是结点之间有分支，并且具有层次关系的结构，它非常类似于自然界中的树。树结构在客观世界国是大量存在的，例如家谱、行政组织机构都可用树形象地表示。树在计算机领域中也有着广泛的应用，例如在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织信息；在分析算法的行为时，可用树来描述其执行过程等等。2023/3/31先来看一下有关树的实例（c）书的目录2023/3/32 3 3.1.1树的基

2、本术语树的基本术语树的基本术语树的基本术语 1树的定义 树(Tree)是n(n0)个结点的有限集(记为T)，T为空时称为空树，否则它满足以下两个条件：(1)有且仅有一个结点没有前驱，称该结点为根结点(Root)；(2)除根结点以外，其余结点可分为m(m0)个互不相交的有限集合T0，Tl，Tm-1。其中每个集合又构成一棵树，树T0，Tl，Tm-1被称为根结点的子树(Subree)。每棵子树的根结点有且仅有一个每棵子树的根结点有且仅有一个直接直接前驱，前驱，但可以有但可以有0 0个或多个后继。个或多个后继。树的逻辑结构表示数据之间的关系是一对多，或者多对一的关系。它的结构特点具有明显的层次关系，是

3、一种十分重要的非线性的数据结构。2023/3/33 图图(a)(a)是一棵只有一个根结点的树；是一棵只有一个根结点的树；图图 (b)(b)是是一一棵棵有有1212个个结结点点的的树树，即即T=AT=A，B B，C C，K K，L L 。A A是是棵棵根根，除除根根结结点点A A之之外外，其其余余的的1111个个结结点点分分为为三三个个互互不不相相交交的的集集合合。T1T1，T2T2和和T3T3是是根根A A的的三三棵棵子子树树，且且本本身身又又都都是是一一棵棵树树。所所以以树树的的定义是是递递归的归的。2023/3/342 2 2 2树的基本术语树的基本术语树的基本术语树的基本术语1.结点的度

4、:一个结点拥有的子树个数,度为零的结点称为叶子结点,其余结点称为非叶子节点或非终结结点。2.树的度:树中所有结点的度的最大值。树中最大分支数为树的度。3.结点的层次及树的深度:根为第一层,根的孩子为第二层,若某结点为第k层,则其孩子为k+1层。树中结点的最大层次称为树的深度或高度。2023/3/353.孩子、双亲:结点子树的根称为这个结点的孩子，而这个结点又被称为孩子的双亲。4.子孙:以某结点为根的子树中的所有结点都被称为是该结点的子孙。5.祖先:从根结点到该结点路径上的所有结点。6.兄弟:同一个双亲的孩子之间互为兄弟。7.堂兄弟:双亲在同一层的结点互为堂兄弟。8.有序树、无序树：如果树中每棵

5、子树从左向右的排列拥有一定的顺序，不得互换，则称为有序树，否则称为无序树。9.森林:是m(m=0)棵互不相的树的集合。森林与树概念相近,相互很容 易转换。2023/3/36 3.2.1 3.2.1 二叉树的定义与性质二叉树的定义与性质 二叉树(Binary Tree)是另一种重要的树型结构。是度为2的有序树，它的特点是每个结点至多有两棵子树。和树结构的定义类似，二叉树的定义也可以用递归形式给出。1 1二叉树的递归定义二叉树的递归定义 二叉树(BinaryTree)是n(n0)个结点的有限集。它或者是空集(n=0)，或者同时满足以下两个条件：(1)有且仅有一个根结点；(2)其余的结点分成两棵互不

6、相交的左子树和右子树。3 3 3 3.2 2 2 2 二叉树二叉树二叉树二叉树 例：试分别画出具有3个结点的树和具有3个结点的二叉树的所有不同形态。2023/3/37 二叉树与树有区别：树至少应有一个结点，而二叉树可以为空；树的子树没有顺序，但如果二叉树的根结点只有一棵子树，必须明确区分它是左子树还是右子树，因为两者将构成不同形态的二叉树。因此，二叉树不是树的特例。它们是两种不同的数据结构。二叉树有5种基本形态：图、图、二叉树的五种基本形态二叉树的五种基本形态(a)a)空二叉树空二叉树 (b)b)只有根结点的二叉树只有根结点的二叉树(c)c)右子树为空的二叉树右子树为空的二叉树 (d)d)左子

7、树为空的二叉树左子树为空的二叉树 (e)e)左右子树均不为空的二叉树左右子树均不为空的二叉树 2023/3/38两种特殊形态的二叉树：满二叉树和完全二叉树。满二叉树和完全二叉树。2.满二叉树(FullBinaryTree)深度为k，且有2k-1个结点的二叉树。特点：（1）每一层上结点数都达到最大；（2）度为1的结点n1=0，树叶都在最下一层上。结点层序编号方法：从根结点起从上到下逐层（层内从左到右）对二叉树的结点进行连续编号。1237654k=3n=23-1=7满二叉树2023/3/39 3.完全二叉树(Complete BinaryTree)深度为k，结点数为n的二叉树，当且仅当每个结点的编

8、号都与相同深度的满二叉树中从1到n的结点一一对应时，称为完全二叉树。图图 完全二叉树完全二叉树完全二叉树的特点：（1）每个结点i的左子树的深度Lhi-其结点i的右子树的深度Rhi等于0 或1，即叶结点只可能出现在层次最大或次最大的两层上。（2）完全二叉树结点数n满足2k-1-1n2k-1。（3）满二叉树一定是完全二叉树，反之不成立。452132023/3/3101324653241LH1=3RH1=1LH1-RH1=2非完全二叉树非完全二叉树非完全二叉树非完全二叉树LHLH2 2=0=0RHRH2 2=1=1LH2-RH2=0-1=-12023/3/3114.4.4.4.遍历二叉树遍历二叉树遍

9、历二叉树遍历二叉树 在二叉树的一些应用中，常常要求在树中查找具有某种特征的结点，或者对树中全部结点逐一进行某种处理。这就引入了遍历二叉树的问题，即如何按某条搜索路径访问树中的每一个结点，使得每一个结点仅切仅被访问一次。遍历二叉树：指按一定的规律对二叉树的每个结点，访问且仅访问一次的处理过程。遍历对线性结构是容易解决的。而二叉树是非线性的，因而需要寻找一种规律，使二叉树上的结点能排列在一个线性队列上，从而便于遍历。2023/3/312 访问是一种抽象操作，是对结点的某种处理，例如可以是求结点的度、或层次、打印结点的信息，或做其他任何工作。一次遍历后，使树中结点的非线性排列，按访问的先后顺序变为某

10、种线性排列。遍历的次序：假如以L、D、R分别表示遍历左子树、遍历根结点和遍历右子树，遍历整个二叉树则有DLR、LDR、LRD、DRL、RDL、RLD六种遍历方案。若规定先左后右先左后右，则只有前三种情况，分别规定为：DLR先（根）序遍历，LDR中（根）序遍历，LRD后（根）序遍历。一、遍历方案一、遍历方案 DLR 先序遍历先序遍历；LDR 中序遍历中序遍历；LRD 后序遍历后序遍历2023/3/3132 2）中序遍历二叉树算法思想）中序遍历二叉树算法思想:若二叉树非空，则：若二叉树非空，则：1 1）中序遍历左子树）中序遍历左子树2 2）访问根结点）访问根结点3 3）中序遍历右子树）中序遍历右子

11、树算法描述算法描述:voidInorder(BiTreebt)/bt为根结点指针为根结点指针if(bt)/根非空根非空Inorder(bt-lchild);visit(bt-data)；Inorder(bt-rchild);1 1）先序遍历二叉树算法思想）先序遍历二叉树算法思想:若二叉树非空，则：若二叉树非空，则：1 1）访问根结点）访问根结点2 2）先序遍历左子树）先序遍历左子树3 3）先序遍历右子树）先序遍历右子树算法描述算法描述:voidPreorder(BiTreebt)/bt为根结点指针为根结点指针if(bt)/根非空根非空visit(visit(btbt-data)-data)；P

12、reorder(bt-lchild);Preorder(bt-rchild);2023/3/314例例1 1遍历结果:先序先序:-+:-+a a b-b-cdcd/efef中序中序:a+ba+b c-d-e/f c-d-e/f后序后序:abcdabcd-+efef/-/-acdefb+3 3）后序遍历二叉树算法思想）后序遍历二叉树算法思想:若二叉树非空，则：若二叉树非空，则：1 1）后序遍历左子树）后序遍历左子树 2 2）后序遍历右子树）后序遍历右子树 3 3）访问根结点）访问根结点算法描述算法描述:voidPostorder(BiTreebt)/bt为根结点指针为根结点指针if(bt)Pos

13、torder(bt-lchild);Postorder(bt-rchild);visit(visit(btbt-data)-data)；2023/3/315例例2 2遍历结果:先序先序:+-+*3*xxx/1x5中序中序:3*x*x+x1/x+5后序后序:3xx*x+1x/-5+-+*35x/x*xx1 1例例3 3 已知一棵二叉树的中序遍历序列为BDCEAFHG，其后序 遍 历 序 列 为DECBHGFA，试画出这棵二叉树并写出其 先 序 遍 历 序 列。ABFGHCED先序遍历序列：先序遍历序列：ABCDFGH2023/3/316（1 1 1 1）先序遍历的递归算法如下（假定结点的元素值为

14、字符型）：）先序遍历的递归算法如下（假定结点的元素值为字符型）：）先序遍历的递归算法如下（假定结点的元素值为字符型）：）先序遍历的递归算法如下（假定结点的元素值为字符型）：#includeincludestdio.hstdio.h typedeftypedefcharcharElemTypeElemType;typedeftypedef structstructnode/node/定定定定义链义链义链义链表表表表结结结结构构构构ElemTypeElemTypedata;/data;/定定定定义结义结义结义结点点点点值值值值 structstructnode*node*lchildlchild;

15、/;/定定定定义义义义左子左子左子左子结结结结点指点指点指点指针针针针 structstructnode*node*rchildrchild;/;/定定定定义义义义右子右子右子右子结结结结点指点指点指点指针针针针 BTreeBTree;preorder(BTreepreorder(BTree*root)/*root)/前序遍前序遍前序遍前序遍历历历历if(rootif(root!=NULL)/!=NULL)/如果不是空如果不是空如果不是空如果不是空结结结结点点点点printf(“printf(“%cn”,rootcn”,root-data);/-data);/输输输输出当前出当前出当前出当前结

16、结结结点点点点值值值值preorder(rootpreorder(root-lchildlchild);/);/递归递归递归递归前序遍前序遍前序遍前序遍历历历历左子左子左子左子结结结结点点点点preorder(rootpreorder(root-rchildrchild);/);/递归递归递归递归前序遍前序遍前序遍前序遍历历历历右子右子右子右子结结结结点点点点 return;/return;/结结结结束束束束 二、遍历算法二、遍历算法二、遍历算法二、遍历算法2023/3/317voidvoidinorder(BTreeinorder(BTree*root)/*root)/中序遍中序遍中序遍中序

17、遍历历历历if(rootif(root!=NULL)/!=NULL)/如果不是空如果不是空如果不是空如果不是空结结结结点点点点inorder(rootinorder(root-lchildlchild);/);/递归递归递归递归中序遍中序遍中序遍中序遍历历历历左子左子左子左子结结结结点点点点printf(“printf(“%cn”,rootcn”,root-data);/-data);/输输输输出当前出当前出当前出当前结结结结点点点点值值值值inorder(rootinorder(root-rchildrchild);/);/递归递归递归递归中序遍中序遍中序遍中序遍历历历历右子右子右子右子结结

18、结结点点点点 (3)(3)(3)(3)后序遍历的算法实现后序遍历的算法实现后序遍历的算法实现后序遍历的算法实现 voidvoidpostorder(BTreepostorder(BTree*root)/*root)/后序遍后序遍后序遍后序遍历历历历if(rootif(root!=NULL)/!=NULL)/如果不是空如果不是空如果不是空如果不是空结结结结点点点点postorder(rootpostorder(root-lchildlchild);/);/递归递归递归递归后序遍后序遍后序遍后序遍历历历历左子左子左子左子结结结结点点点点postorder(rootpostorder(root-rc

19、hildrchild);/);/递归递归递归递归后序遍后序遍后序遍后序遍历历历历右子右子右子右子结结结结点点点点printf(“printf(“%cn”,rootcn”,root-data);/-data);/输输输输出当前出当前出当前出当前结结结结点点点点值值值值（2 2 2 2）中序遍历的递归算法如下（假定结点的元素值为字符型）：）中序遍历的递归算法如下（假定结点的元素值为字符型）：）中序遍历的递归算法如下（假定结点的元素值为字符型）：）中序遍历的递归算法如下（假定结点的元素值为字符型）：2023/3/3182 2二叉树的性质二叉树的性质性质1 在二叉树的第i层上至多有2i-1 个结点(i

20、1)。性质2 深度为k的二叉树至多有2k-1个结点(k1)。（深度一定，二叉树的最大结点数也确定）性质3 二叉树中,终端结点数n0与度为2的结点数n2有如下关系:n0=n2+1性质4 结点数为n的完全二叉树，其深度为 log2n+l。性质5 在按层序编号n个结点的完全二叉树中，任意一结点i(1in)有：i=1时，结点i是树的根；否则，结点i的双亲为结点i/2(i1)。2in时，结点i无左孩子，为叶结点；否则结点i的左孩子为结点2i。2i+1n时，结点i无右孩子；否则，结点i的右孩子为结点2i+1。例：若一棵树具有n1个度为1的结点，n2个度为2的结点，,nm个度为m的结点，则这棵树中的叶子结点

21、有多少个。2023/3/3193.2.2 3.2.2 二叉树的存储结构二叉树的存储结构 同线性表一样，二叉树的存储结构也有顺序和链表两种结构。1 1顺序存储结构顺序存储结构 用一组地址连续的存储单元，以层序顺序存放二叉树的数据元素，结点的相对位置蕴含着结点之间的关系。完全二叉树DCGFEBA bt3 的双亲为 3/2=1，即在bt1中；其左孩子在bt2i=bt6中；其右孩子在bt2i+1=bt7中。1234567891011ABCDEFG00002023/3/320 这种存储结构适合于完全二叉树，既不浪费存储空间，又能很快确定结点的存放位置、结点的双亲和左右孩子的存放位置，但对一般二叉树，可能

22、造成存储空间的大量浪费。D二叉树CGFEBA一般二叉树也按完全二叉树形式存储，无结点处用0表示。123456789101112ABCDEABCDE0000FGFG00002023/3/321 例如：深度为k，且只有k个结点的右单枝树(每个非叶结点只有右孩子)，需2k-1个单元，即有2k-1-k个单元被浪费。链式存储结构链式存储结构 （二叉链表）设计不同的结点结构，可以构成不同的链式存储结构。常用的有：二叉链表 三叉链表 线索链表 用空链域存放指向前驱或后继的线索2023/3/322 由于二叉树每个结点至多只有2个孩子，分别为左孩子和右孩子。因此可以把每个结点分成三个域：一个域存放结点本身的信息

23、，另外两个是指针域，分别存放左、右孩子的地址。每个结点的结构表示为：其中左链域lchild为指向左孩子的指针，右链域rchild为指向右孩子的指针，数据域data表示结点的值。若某结点没有左孩子或右孩子，其相应的链域为空指针。对应的结构类型定义如下：对应的结构类型定义如下：typedeftypedef structstructnodenode ElemTypeElemTypedata;data;structstructnode*node*lchildlchild;structstructnode*node*rchildrchild;BTreeBTree,*tree;,*tree;其中，其中，t

24、reetree是指向根结点的指针。是指向根结点的指针。2023/3/323二叉链表的结点结构lchilddatarchildD 二叉树二叉树CEBAACBDE二叉链表二叉链表说明：说明：一一个个二二叉叉链链表表由由根根指指针针rootroot唯唯一一确确定定。若若二二叉叉树树为为空空，则则root=NULLroot=NULL；若结点的某个孩子不存在，则相应的指针为空。若结点的某个孩子不存在，则相应的指针为空。具具有有n n个个结结点点的的二二叉叉链链表表中中，共共有有2 2n n个个指指针针域域。其其中中只只有有n-1n-1个个用来指示结点的左、右孩子，其余的用来指示结点的左、右孩子，其余的n

25、+1n+1个指针域为空。个指针域为空。2023/3/324 和线性表一样，树可以用顺序和链式两种存储结构。树的顺序存储结构适合树中结点比较“满”的情况。根据树的非线性结构特点，常用链式存储方式来表示树。树常用的存储方法有：双亲存储表示法、孩子链表表示法和孩子兄弟链表表示法。特点：求结点的双亲很容易，但求结点的孩子需要遍历整个向量。3.3 3.3 树的存储结构树的存储结构 一般采用顺序存储结构实现。用一组地址连续的存储单元来存放树的结点，每个结点有两个域：data域-存放结点的信息；parent域-存放该结点双亲结点的位置1 1双亲存储表示法双亲存储表示法ABCFGDEHI(a)树 A -1 B

26、 0 C 0 D 1 E 1 F 1 G 2 H 4 I 4(b)树 的 双 亲 存 储 结 构序 号 data parent0123456782023/3/325存储结构描述为：存储结构描述为：#defineMaxTreeSize100/定定义义数数组组空空间间的大小的大小typedefcharDataType；/定定义义数据数据类类型型typedefstructDataTypedata；/结结点数据点数据intparent；/双双亲亲指指针针，指示，指示结结点的双点的双亲亲在数在数组组中的位置中的位置PTreeNode；typedefstructPTreeNodenodesMaxTreeS

27、ize;intn；/结结点点总总数数PTree；PTreeT；/T是双亲链表是双亲链表2023/3/326 2 2孩子链表表示法孩子链表表示法 这是树的链式存储结构。每个结点的孩子用单链表存储，称为孩子链表。n个结点可以有n个孩子链表（叶结点的孩子链表为空表）。n个孩子链表的头指针用一个向量表示。图、图、树的孩子链表结构树的孩子链表结构 头指针向量孩子链表头指针向量孩子链表特点：与双亲相反，求孩子易，求双亲难。A B C D E F G (b)树的孩子存储结构01234561234 56ABCFGDE(a)树2023/3/327存储结构描述为：存储结构描述为：存储结构描述为：存储结构描述为：t

28、ypedefstructCTNodeintchild;/孩子孩子链链表表结结点点structCTNode*next;*ChildPtr;typedefstruct/孩子孩子链链表表头结头结点点ElemTypedata;/结结点的数据元素点的数据元素ChildPtrfirstchild;/孩子孩子链链表表头头指指针针CTBox;typedefstructCTBoxnodesMaxTreeSize;intn,r,/数的数的结结点数和根点数和根结结点的位置点的位置CTree;2023/3/328孩子孩子孩子孩子链链链链表表示法的表表示法的表表示法的表表示法的类类类类型型型型说说说说明明明明 type

29、defstructCnode/DataType和和MaxTreeSize由用由用户户定定义义/孩子孩子链链表表结结点点intchild;/孩子孩子结结点在数点在数组组中中对应对应的下的下标标structCNode*next;Cnode;typedefstruct/孩子孩子链链表表头结头结点点DataTypedata;/存放存放树树中中结结点数据点数据CNode*firstchild;/孩子孩子链链表的表的头头指指针针PTNode;typedefstructPTNodenodesMaxTreeSize;Intn,root;/树树的的结结点数和根点数和根结结点的位置点的位置Ctree;CtreeT

30、;/T的孩子链表表示的孩子链表表示 2023/3/329 孩子兄弟链表表示法也是树的一种链式存储结构。用二叉链表作为树的存储结构，每个结点的左链域指向该结点的第一个孩子，右链域指向下一个兄弟结点。由于结点中的两个指针指示的分别为“孩子”和“兄弟”，故称为“孩子-兄弟链表”。这种结构也称为二叉链表。图、图、树的孩子树的孩子-兄弟存储结构兄弟存储结构 特点：双亲只管长子，长子连接兄弟 3 3孩子兄弟链表表示法孩子兄弟链表表示法ABCFGDE(a)树2023/3/330树的孩子兄弟链表的存储结构描述为：树的孩子兄弟链表的存储结构描述为：typedeftypedef structstruct CSNo

31、deCSNodeElemTypeElemTypedata;data;structstruct CSNodeCSNode*firstchildfirstchild,*,*nextsiblingnextsibling;CSNodeCSNode,*,*CSTreeCSTree;孩孩子子兄兄弟弟存存储储结结构构的的最最大大优优点点是是可可以以方方便便地地实实现现树树和和二二叉叉树树的的相相互互转转换换和和树树的的各各种种操操作作。但但是是，孩孩子子兄兄弟弟存存储储结结构构的的缺缺点点也也是是查查找找当当前前结结点的双亲结点比较麻烦，需要从树根结点开始逐个结点比较查找。点的双亲结点比较麻烦，需要从树根结

32、点开始逐个结点比较查找。2023/3/3313.63.6 树、森林和二叉树的转换树、森林和二叉树的转换图图图图、森林和对应的二叉树森林和对应的二叉树森林和对应的二叉树森林和对应的二叉树（1）加线,在兄弟之间加一连线（2）抹线,对每个结点，除了其第一个孩子外，去除其与其余孩子之间的关系（3）旋转,对于横着的连线，以树的根结点为轴心，将其顺时针转 45。方法：2023/3/3321 1 1 1树的遍历树的遍历树的遍历树的遍历 所所谓谓树树的的遍遍历历，就就是是按按照照某某种种顺顺序序依依次次访访问问树树中中各各个个结结点点，并并使使得得每每个个结结点点只只被被访访问问一一次次。也也就就是是把把非非

33、线线性性结结构构的的树树结结点点变变成成线线性性序序列列的的一种方式一种方式 。树树的的遍遍历历可可以以按按深深度度优优先先遍遍历历，也也可可以以按按照照广广度度优优先先（按按层层次次）遍遍历。深度优先遍历通常有两种方式：历。深度优先遍历通常有两种方式：前序前序遍历和遍历和后序后序遍历。遍历。(1)(1)前序遍历的递归定义：前序遍历的递归定义：若树若树T T非空，则：非空，则：访问根结点访问根结点R R；按照从左到右的顺序依次前序遍历根结点按照从左到右的顺序依次前序遍历根结点R R的各子树的各子树T T1 1，T T2 2，T Tk k。2023/3/333(2)(2)后序遍历的递归定义：后序

34、遍历的递归定义：若树若树T T非空，则：非空，则：按照从左到右的顺序依次后序遍历根按照从左到右的顺序依次后序遍历根T T的各子树的各子树T Tl l，T T2 2，T Tk k；访问根结点访问根结点R R。(3)(3)广度优先（按层）遍历广度优先（按层）遍历广广度度优优先先（按按层层次次）遍遍历历定定义义为为：先先访访问问第第一一层层结结点点（即即树树根根结结点点），再再从从左左至至右右访访问问第第二二层层结结点点，依依次次按按层层访访问问，直直到到树树中中结结点点全全部部被被访访问问为为止止。对对图图(a)a)中中的的树树进进行行按按层层次次遍遍历历得得到到树树的的广广度度优优先先遍遍历历序

35、序列列为为：ABCDEFGABCDEFG。说明：说明：前序遍历一棵树恰好等价于前序遍历该树所对应的二叉树。前序遍历一棵树恰好等价于前序遍历该树所对应的二叉树。后序遍历树恰好等价于中序遍历该树所对应的二叉树。后序遍历树恰好等价于中序遍历该树所对应的二叉树。2023/3/3342森林的遍历森林的深度优先遍历通常也有两种方式：前序遍历和后序遍历。(1)前序遍历森林 若森林非空，则：访问森林中第一棵树的根结点；前序遍历第一棵树中根结点的各子树所构成的森林前序遍历去掉第一棵树外其它树构成的森林。(2)后序遍历森林 若森林非空，则:后序遍历森林中第一棵树中根结点的各子树所构成的森林；访问第一棵树的根结点；

36、后序遍历去掉第一棵树外其它树构成的森林。当用二叉链表作为树和森林的存储结构时，树和森林的前序遍历和后序遍历可用二叉树的前序遍历和中序遍历算法来实现。2023/3/3353.7.3 树的应用哈夫曼树1.哈夫曼树的基本概念 哈夫曼树（Huffman）又称最优二叉树，是一类带权路径长度最短的树，有着广泛的应用。基本概念：树中两个结点之间的路径由一个结点到另一结点的分支构成。两结点之间的路径长度是路径上分支的数目。树的路径长度是从根结点到每一个结点的路径长度之和。在应用中，将树中结点赋予一个有某种意义的实数，称为该结点的权。结点的带权路径长度，是指该结点到树根之间的路径长度与结点上权的乘积。树的带权路

37、径长度（Weighted Path Length of Tree）定义为树中所有叶子结点的带权路径长度之和，记为：其中，n表示叶子结点的数目，Wi和Ni分别表示叶子结点Ki的权值和根到叶子结点Ki之间的路径长度。2023/3/3362023/3/3372023/3/3382023/3/3392023/3/3402023/3/3412023/3/3422023/3/3432023/3/3442023/3/3452023/3/346习题：1、对给定的一组权W=14，15，7，4，20，3，确定哈夫曼树，并求出其带权路长。2、假设用于通讯的电文仅由8个字母组成，字母在英文中出现的频率分别为7，19，2，6，32，3，21，10。试为这8个字母设计哈夫曼编码。3、假设字符a、b、c、d、e、f出现的概率分别为0.07、0.09、0.12、0.22、0.23、0.27，求最优哈夫曼编码，并画出哈夫曼树，试问编码的平均长度是多少？2023/3/347