数据结构第六章幻灯片.ppt

《数据结构第六章幻灯片.ppt》由会员分享，可在线阅读，更多相关《数据结构第六章幻灯片.ppt（39页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构第六章1第1页，共39页，编辑于2022年，星期六主要讨论的问题：树的定义；二叉树的定义与性质主要讨论的问题：树的定义；二叉树的定义与性质,二二叉树的遍历叉树的遍历,线索二叉树线索二叉树,树与森林哈夫曼树及应用树与森林哈夫曼树及应用.6.1树的定义与基本术语树的定义与基本术语.回忆线性结构的特点回忆线性结构的特点.非线性结构的特点非线性结构的特点:至少存在一个数据元素有两个至少存在一个数据元素有两个或两个以上的直接前驱（或直接后继）元素的数据结或两个以上的直接前驱（或直接后继）元素的数据结构构.人类的族谱、各种社会关系、各类分类编码；人类的族谱、各种社会关系、各类分类编码；操作系统的文

2、件系统、编译程序的语法树；操作系统的文件系统、编译程序的语法树；Internet中的中的DNS（域名系统）（域名系统）-层次结构层次结构第2页，共39页，编辑于2022年，星期六.树的定义树的定义(递归定义递归定义)是是n(n0)个结点的有限集合个结点的有限集合T，对于任意一棵非空，对于任意一棵非空树，它满足：树，它满足：(1)有且仅有一个特定的称为根的结点。有且仅有一个特定的称为根的结点。(2)当当n1时，其余结点可分为时，其余结点可分为m(m0)个互不个互不相交的有限集相交的有限集T1，T2，.，Tm，其中每个集，其中每个集合本身又是一棵树，称为根的合本身又是一棵树，称为根的子树子树。显然

3、：上述树的定义是一个递归定义。显然：上述树的定义是一个递归定义。3第3页，共39页，编辑于2022年，星期六.常用术语与基本概念常用术语与基本概念.结点的度、树的度、叶子结点、分支结点结点的度、树的度、叶子结点、分支结点.内部结点、结点的孩子、兄弟、结点的祖先、结内部结点、结点的孩子、兄弟、结点的祖先、结点的子孙、结点的层次点的子孙、结点的层次.树的深度、无序树、有序树、森林树的深度、无序树、有序树、森林.4第4页，共39页，编辑于2022年，星期六6.2二叉树二叉树.二叉树的定义二叉树的定义 是由是由n(n=0)个结点的有限集合，它或为空树个结点的有限集合，它或为空树(n=0),或由一个根结

4、点和至多两棵称为根的左子或由一个根结点和至多两棵称为根的左子树和右子树的互不相交的二叉树组成树和右子树的互不相交的二叉树组成.结论结论:二叉树中不存在度大于二叉树中不存在度大于2的结点，并且二叉的结点，并且二叉树的子树有左子树和右子树之分树的子树有左子树和右子树之分.即二叉树是度不即二叉树是度不大于大于2的有序树的有序树.二叉树的五种形态二叉树的五种形态.5第5页，共39页，编辑于2022年，星期六.二叉树的性质二叉树的性质性质性质1:在二叉树的第在二叉树的第i层上至多有层上至多有2i-1个结个结(i=1).性质性质2:高度为高度为k的二叉树中至多有的二叉树中至多有2k-1个结点个结点(k=1

5、).性质性质3:在任意一棵二叉树中在任意一棵二叉树中,若其叶子结点数为若其叶子结点数为n0,度为度为2的结点数为的结点数为n2,则有：则有：n0=n2+1.性质性质4:具有具有n个结点的个结点的完全二叉树完全二叉树的深度为的深度为6第6页，共39页，编辑于2022年，星期六.满二叉树满二叉树 是指高度为是指高度为k且有且有2k-1个结点的二叉树个结点的二叉树.特点：每一层上都有含有最大结点数特点：每一层上都有含有最大结点数.结点编号结点编号:从上到下从上到下,从左到右按自然数编号从左到右按自然数编号.完全二叉树完全二叉树 高度为高度为k，有，有n个结点的二叉树是一棵完全二叉树，个结点的二叉树是

6、一棵完全二叉树，当且仅当其每个结点都与高度为当且仅当其每个结点都与高度为k的满二叉树中层次的满二叉树中层次编号编号1-n相对应相对应.7第7页，共39页，编辑于2022年，星期六.完全二叉树的特点完全二叉树的特点1)除最后一层外，每一层都取最大结点数，最后一除最后一层外，每一层都取最大结点数，最后一层结点都有集中在该层层结点都有集中在该层最左边的若干位置最左边的若干位置.2)叶子结点叶子结点只可能在层次最大的两层出现只可能在层次最大的两层出现.3)对任一结点，若其右分支下的子孙的最大层次为对任一结点，若其右分支下的子孙的最大层次为k，则其左分支下的子孙的最大层次为则其左分支下的子孙的最大层次为

7、k或或k+1.性质性质4:具有具有n个结点的个结点的完全二叉树完全二叉树的深度为的深度为8第8页，共39页，编辑于2022年，星期六性质性质5:对有对有n个结点的完全二叉树的结点按层序个结点的完全二叉树的结点按层序编号编号(从上到下从上到下,自左到右自左到右)对任一结点对任一结点i(1=in)，若若in/2，则，则i无左孩子。无左孩子。(3)若若i(n-1)/2，结点，结点i的或孩子是结点的或孩子是结点2i+1;否则否则(即即2i+1n),结点结点i无右孩。无右孩。9第9页，共39页，编辑于2022年，星期六性质性质5的证明的证明:对对i=1,由完全二叉树定义知，其左孩为结由完全二叉树定义知，

8、其左孩为结2，右孩为，右孩为结点结点3；若若2n(即即2in)，显然结点，显然结点2不存在，即此时不存在，即此时i无左孩；无左孩；若若3n（即（即2i+1n），则结点），则结点3不存在。不存在。由此：对于由此：对于i=1时，上述性质时，上述性质(2),(3)成立。成立。后续证明i1的情形10第10页，共39页，编辑于2022年，星期六性质性质5的证明的证明(续续):对对i1,将结点将结点i处于处于某层某层第一个结点和该层任意一个第一个结点和该层任意一个结点两种情形分别证明结点两种情形分别证明:情况一：设结点情况一：设结点i为第为第j层层()的第一个结的第一个结点点.j-1 j j+1i=2j-

9、1-1i=2j-12j=2i2j+1=2i+12j-1.k k-1 .?+1续证i1的情形11第11页，共39页，编辑于2022年，星期六性质性质5的证明（续）：的证明（续）：?j-1 j j+1i=2j-1-1i=2j-12j=2i2j+1=2i+12j-1.k k-1 .?+1 由二叉树的性质二可得由二叉树的性质二可得:第第j-1层最后一个结点为层最后一个结点为2j-1-1;又根据又根据完全二叉树的特点知完全二叉树的特点知:第第j层的第一个结点应为层的第一个结点应为i=2j-1-1+1=2j-1.又又因为因为i的左孩必为第的左孩必为第j+1层的第一个结点，显然其编号应为层的第一个结点，显然

10、其编号应为（2j-1）+1即即2j.因为因为2j=2*2j-1=2i（i为为2j-1）续证i1的情形12第12页，共39页，编辑于2022年，星期六 j-1 j j+1i=2j-1-1i=2j-12j=2i2j+1=2i+12j-1.k k-1 .?+1所以当所以当2jn（即（即2in）时，编号为）时，编号为2j的结点不存在，即：此时的结点不存在，即：此时i必无左孩必无左孩(因为最多只有因为最多只有n个结点个结点).同理：结点同理：结点i如有右孩，则其如有右孩，则其右孩必为第右孩必为第j+1层上的第二个结点，其编号为层上的第二个结点，其编号为2i+1(即即2j+1)否则否则,若若2i+1n,则

11、则i必无右孩必无右孩.续证i1的情形二性质性质5的证明（续）：的证明（续）：13第13页，共39页，编辑于2022年，星期六 对于第对于第j层的任意第层的任意第k个结点，设上述个结点，设上述(2),(3)的断言成立，即对于任意的的断言成立，即对于任意的i=k,当当2j-1k2j-1时，若结点时，若结点k有左孩，则必为有左孩，则必为2k；若结点；若结点k有右孩，则必为有右孩，则必为2k+1.由此：当由此：当i=k+1(2j-1k2j-1)时，由于时，由于k+1是是k的右兄弟的右兄弟(若堂兄弟若堂兄弟)，若，若k+1有有左孩，则应为左孩，则应为2(k+1)，同理，如，同理，如(k+1)结点有右孩，

12、则应为结点有右孩，则应为2(k+1)+1.而由完全而由完全二叉树的特点知，这显然是正确的，由此性质五二叉树的特点知，这显然是正确的，由此性质五(2),(3)完全成立完全成立.2k 2k+1 2k+2 j-1 j ji=2j-1-1i=2j-12j=2i2j+1=2i+12j-1.k k-1 .k+1 2k+3性质性质5的证明（续）：的证明（续）：14第14页，共39页，编辑于2022年，星期六例例1:任意一个有任意一个有n个结点的二叉树，已知它有个结点的二叉树，已知它有m个个叶子结点，试证明非叶子结点有叶子结点，试证明非叶子结点有(m-1)个度为个度为2，其余度为其余度为1.例例2:已知完全二

13、叉树的第七层有已知完全二叉树的第七层有10个叶子结点，个叶子结点，则整个二叉树的结点数最多是多少则整个二叉树的结点数最多是多少.15第15页，共39页，编辑于2022年，星期六.二叉树的存储结构二叉树的存储结构顺序存储结构顺序存储结构用一组地址连续的存储单元依次自上而下，用一组地址连续的存储单元依次自上而下，自左至右存储完全二叉树上的结点元素自左至右存储完全二叉树上的结点元素结论：完全二叉树适合于顺序存储结构结论：完全二叉树适合于顺序存储结构链式存储结构链式存储结构二叉链表表示法二叉链表表示法16第16页，共39页，编辑于2022年，星期六例例3.有有n个结点的完全二叉树存放在一维数组个结点的

14、完全二叉树存放在一维数组A1.n中中,试据此建立一棵用二叉链表表示的试据此建立一棵用二叉链表表示的二叉树二叉树,根由根由tree指向指向.分析：分析：1)树的递归定义树的递归定义2)树由几部分组成？树由几部分组成？BiTree Creat(ElemType A,int i)BiTree tree;if(idata=Ai;if (2*in)tree-lchild=null；else tree-lchild=Creat(A,2*i)；if (2*i+1n)tree-rchild=null；else tree-rchild=Creat(A,2*i+1)；return tree；17第17页，共39页

15、，编辑于2022年，星期六例例4要求二叉树按要求二叉树按二叉链表二叉链表形式存储，形式存储，(1)写一个建立二叉树的算法写一个建立二叉树的算法.(2)写一个判别给定的二叉树是否是完全二叉树的写一个判别给定的二叉树是否是完全二叉树的算法算法.BiTree Creat()ElemType x；BiTree bt;scanf(“%d”,&x);/本题假定结点数据域为整型本题假定结点数据域为整型if(x=0)bt=null;else if(x0)bt=(BiNode*)malloc(sizeof(BiNode);bt-data=x;bt-lchild=creat();bt-rchild=creat()

16、;else error(“输入错误输入错误”)；return bt;18第18页，共39页，编辑于2022年，星期六6.3遍历遍历二叉树和线索二叉树二叉树和线索二叉树.遍历二叉树遍历二叉树按按某条搜索路径某条搜索路径访问二叉树中的每个结点，使访问二叉树中的每个结点，使得每个结点均被访问一次，而且仅被访问一次得每个结点均被访问一次，而且仅被访问一次.先左后右先左后右的搜索路径的搜索路径/先右后左的搜索路径先右后左的搜索路径.先左后右先左后右的搜索路径有三种：先序遍历，中序遍历的搜索路径有三种：先序遍历，中序遍历和后序遍历和后序遍历19第19页，共39页，编辑于2022年，星期六.按按先序遍历先序

17、遍历/中序遍历中序遍历/后序遍历把非线性的二后序遍历把非线性的二叉树结构变为了线性结构叉树结构变为了线性结构.那么，变换后的线性结构能否恢复为原来的二叉树？那么，变换后的线性结构能否恢复为原来的二叉树？NO.先序遍历与中序遍历中序遍历和后序遍历能唯一确先序遍历与中序遍历中序遍历和后序遍历能唯一确定该二叉树定该二叉树20第20页，共39页，编辑于2022年，星期六例例5.设一棵二叉树的先序遍历序列设一棵二叉树的先序遍历序列:A B D F C E G H,中序遍历序列中序遍历序列:B F D A G E H C，画出这棵二，画出这棵二叉树叉树.二叉树层次遍历二叉树层次遍历(广度优先遍历广度优先遍

18、历).按以上的搜索路径遍历一棵二叉树称之为按以上的搜索路径遍历一棵二叉树称之为二叉树的二叉树的深度优先遍历深度优先遍历搜索路径搜索路径：从二叉树的根开始，自顶向下，同一：从二叉树的根开始，自顶向下，同一层从左向右层从左向右21第21页，共39页，编辑于2022年，星期六.二叉树遍历递归算法二叉树遍历递归算法.先序遍历的递归算法先序遍历的递归算法void preorder(BiTree tree)if(tree!=null)visit(tree-data);/访问二叉树的结点访问二叉树的结点 preorder(tree-lchild);preorder(tree-rchild);.同理同理,可写

19、出中序遍历和后序遍历的递归算法可写出中序遍历和后序遍历的递归算法22第22页，共39页，编辑于2022年，星期六.二叉树遍历是二叉树应用的基础二叉树遍历是二叉树应用的基础.例例5.二叉树采用链式存储结构二叉树采用链式存储结构,设计递归算法求给定二设计递归算法求给定二叉树的所有结点数叉树的所有结点数.int size(BiTree tree)if(tree=null)return 0;else return size(tree-lchild)+size(tree-rchild)+1;分析分析:二叉树后序遍历的应用二叉树后序遍历的应用.查阅资料查阅资料:求二叉树高度求二叉树高度,度为度为0/1/2

20、结点个数结点个数,判断二判断二叉树相等叉树相等,实现二叉树复制等实现二叉树复制等.(检查检查)23第23页，共39页，编辑于2022年，星期六.二叉树遍历非递归算法二叉树遍历非递归算法.先序遍历的非递归算法先序遍历的非递归算法分析：各阶段栈的内容及输出情况分析：各阶段栈的内容及输出情况void preorder(BiTree p)BiTree sMaxsize;int top=0;while(p!=NULL|top)while(p!=NULL)visit(p-data);s+top=p;p=p-lchild;/左孩子进栈左孩子进栈 if(top!=0)p=stop-;p=p-rchild;/右

21、孩子进栈右孩子进栈 24第24页，共39页，编辑于2022年，星期六例例6要求二叉树按要求二叉树按二叉链表二叉链表形式存储，形式存储，(1)写一个建立二叉树的算法写一个建立二叉树的算法.(2)写一个判别给定的二叉树是否是完全二叉树的算写一个判别给定的二叉树是否是完全二叉树的算法法.同理同理,模仿上例查阅资料写出中序遍历与后序遍历模仿上例查阅资料写出中序遍历与后序遍历的非递归算法的非递归算法.(检查检查)分析分析:判定是否是完全二叉树，可以使用队列，在判定是否是完全二叉树，可以使用队列，在遍历中利用完全二叉树遍历中利用完全二叉树“若某结点无左子女就不若某结点无左子女就不应有右子女应有右子女”的原

22、则进行判断。的原则进行判断。25第25页，共39页，编辑于2022年，星期六即即:1.当检查当某个接点只有右孩子时当检查当某个接点只有右孩子时,则退出则退出.2.当检查到某个接点只有左孩子或没有孩子结点当检查到某个接点只有左孩子或没有孩子结点,这时要保证队列中后面的结点都没有孩子这时要保证队列中后面的结点都没有孩子,才是完才是完全二叉树全二叉树,所以要设置一个所以要设置一个flag标记标记.一旦发现这种一旦发现这种情况，就标记该结点情况，就标记该结点.根据根据flag判断是否有孩子，判断是否有孩子，如果有，那么就不是完全二叉树如果有，那么就不是完全二叉树;如果队列取空时，如果队列取空时，没有出

23、现有孩子的结点，那么就是完全二叉树。没有出现有孩子的结点，那么就是完全二叉树。26第26页，共39页，编辑于2022年，星期六int JudgeComplete(BiTree bt)int tag=0;BiTree p=bt,Q;/根结点不标记根结点不标记 if(p=null)return 1;QueueInit(Q);QueueIn(Q,p);while(!QueueEmpty(Q)p=QueueOut(Q);/出队出队 if(p-lchild&!tag)QueueIn(Q,p-lchild);/左子女入队左子女入队 else if(p-lchild)return 0;/前面有结点无右孩子前

24、面有结点无右孩子 else tag=1;if(p-rchild&!tag)QueueIn(Q,p-rchild);/右子女入队右子女入队 else if(p-rchild)/前面有结点无左孩子前面有结点无左孩子 return 0;else tag=1;return 1;27第27页，共39页，编辑于2022年，星期六.线索二叉树线索二叉树.对于任意的二叉树，采用二叉链表表示，有多对于任意的二叉树，采用二叉链表表示，有多少个空的指针域？少个空的指针域？.在遍历二叉树的过程中，利用这些空的指针域将在遍历二叉树的过程中，利用这些空的指针域将遍历产生的线性序列的前驱与后继保留下来遍历产生的线性序列的前

25、驱与后继保留下来.改进二叉链表的结构改进二叉链表的结构28第28页，共39页，编辑于2022年，星期六.线索二叉树线索二叉树:加上线索的二叉树加上线索的二叉树.线索：在线索链表中指向结点前驱和后继的指针线索：在线索链表中指向结点前驱和后继的指针.线索化：对二叉树以某种次序遍历使其变为线索线索化：对二叉树以某种次序遍历使其变为线索二叉树的过程二叉树的过程.画线索化二叉树画线索化二叉树.二叉树线索化算法二叉树线索化算法29第29页，共39页，编辑于2022年，星期六例例6.设有二叉树设有二叉树BT，每个结点包括，每个结点包括ltag，lchild，data，rchild，rtag五个字段，依次为左

26、标志、左儿子，数据，右五个字段，依次为左标志、左儿子，数据，右儿子，右标志给出将二叉树儿子，右标志给出将二叉树BT建成前序（即先序）线索建成前序（即先序）线索二叉树的递归算法二叉树的递归算法.分析：对每个结点线索化时，应知道其前驱和后继的指针分析：对每个结点线索化时，应知道其前驱和后继的指针值对于前驱结点的值，可设置一变量值对于前驱结点的值，可设置一变量pre来记录对于其来记录对于其后继结点的值，由于是按遍历次序来进行的因此，在线后继结点的值，由于是按遍历次序来进行的因此，在线索化该结点时还不知道，因而设置了也没有意索化该结点时还不知道，因而设置了也没有意义义.存在一个问题存在一个问题即：线索

27、化时只能进行前趋线索化，后继线索化即：线索化时只能进行前趋线索化，后继线索化无法进行无法进行.线索化分线索化分2步进行：当步进行：当T为当前结点时，可进行前驱线索化，为当前结点时，可进行前驱线索化，当的后继为当前结点时再对进行后继线索化当的后继为当前结点时再对进行后继线索化30第30页，共39页，编辑于2022年，星期六.线索化分线索化分2步步进行：当进行：当T为当前结点时，可进行前驱线索化，为当前结点时，可进行前驱线索化，当的后继为当前结点时再对进行后继线索化当的后继为当前结点时再对进行后继线索化.从另一角度从另一角度:当当T为当前结点时要完成两个操作为当前结点时要完成两个操作:T的前驱线索

28、的前驱线索化化(需要判断条件需要判断条件),T的前驱结点的前驱结点(由由pre指示指示)的后继线索化和的后继线索化和并为并为后继结点的线索化做准备后继结点的线索化做准备.31第31页，共39页，编辑于2022年，星期六BiThrTree pre=null;/设置前驱设置前驱void PreOrderThreat(BiThrTree BT)if(BT!=null)if(BT-lchild=null)BT-ltag=1;BT-lchild=pre;if(pre!=null&pre-rtag=1)pre-rchild=BT;if(BT-rchild=null)BT-rtag=1;pre=BT;/前驱

29、后移前驱后移 if(BT-ltag=0)PreOrderThreat(BT-lchild);PreOrderThreat(BT-rchild)32第32页，共39页，编辑于2022年，星期六例例7.设计算法求先序线索二叉树中指针设计算法求先序线索二叉树中指针p所指结点的先所指结点的先序后继结点的指针序后继结点的指针.分析分析:若某一结点若某一结点p有左孩子有左孩子,则该结点的左孩子便是则该结点的左孩子便是p的的后继后继;否则否则,p的的右孩子右孩子便是它的后继便是它的后继.BiTNode*PreNext(BiTNode*p)BiTNode*q;if(p-ltag=0)q=p-lchild;el

30、se q=p-rchild;33第33页，共39页，编辑于2022年，星期六.树的存储树的存储.双亲表示法双亲表示法(自学自学)，孩子表示法，孩子表示法(自学自学)，孩子兄弟孩子兄弟表示法表示法(二叉树表示法二叉树表示法)6.4树和森林树和森林.孩子兄弟表示法存储示意图孩子兄弟表示法存储示意图.森林与二叉树的转换森林与二叉树的转换.树与二叉树的转换树与二叉树的转换.方法：方法：1)对每个孩子进行自左至右的排序；对每个孩子进行自左至右的排序；2)在兄弟之间加一条虚线；在兄弟之间加一条虚线；3)对每个结点，除了左孩子外，去除其与其余孩子之间的联系；对每个结点，除了左孩子外，去除其与其余孩子之间的联

31、系；4)以根结点为轴心，将整个树顺时针转以根结点为轴心，将整个树顺时针转45度度(实线在左，虚线在右实线在左，虚线在右)。34第34页，共39页，编辑于2022年，星期六.树由几部分组成？树由几部分组成？.树由根与去除根外的子树森林两部分组成树由根与去除根外的子树森林两部分组成.树的遍历树的遍历.树的遍历：先序遍历与后序遍历树的遍历：先序遍历与后序遍历.森林的遍历森林的遍历.森林由几部分组成？森林由几部分组成？.森林由三部分组成：第一棵树的根，第一树去除根森林由三部分组成：第一棵树的根，第一树去除根后的子树森林，其它树组成的森林三部分组成后的子树森林，其它树组成的森林三部分组成.森林的遍历：先

32、序遍历，中序遍历与后序遍历森林的遍历：先序遍历，中序遍历与后序遍历.二叉树遍历，树遍历，森林的遍历之间的关系二叉树遍历，树遍历，森林的遍历之间的关系35第35页，共39页，编辑于2022年，星期六.为什么要建立为什么要建立哈夫曼哈夫曼树？树？.Huffman.Huffman编码编码(前缀编码前缀编码)6.6哈夫曼树及其应用哈夫曼树及其应用.电文：电文：ABACCDA,若若A,B,C,D的编码分别为的编码分别为:00,01,10,11.报文总长度为报文总长度为14,为为00010010101100.接接收方接收时二位一分便可译码收方接收时二位一分便可译码.如何在传送电文时使报文的总长度最小如何在

33、传送电文时使报文的总长度最小?.编码长度应不等长编码长度应不等长.若若A,B,C,D的编码分别为的编码分别为:0,00,1,01.报文总长度报文总长度为为9,为为000011010.接收方接收译码呈现接收方接收译码呈现多样性多样性.一个编码是一个编码是另一个编码另一个编码的前缀的前缀.任一字符的编任一字符的编码都不是另一码都不是另一编码的前缀编码的前缀 36第36页，共39页，编辑于2022年，星期六.如何进行如何进行Huffman编码编码?.构造一棵最优二叉树构造一棵最优二叉树(哈夫曼树哈夫曼树).几个名词：路径几个名词：路径,路径长度路径长度,树的路径长度树的路径长度,树的带权路树的带权路

34、径长度径长度.哈夫曼树构造方法哈夫曼树构造方法 (1)给定给定w1,w2,.,wn,构成构成F=T1,T2,.,Tn,每个树只有一个根结点每个树只有一个根结点;(2)选两个根结点最小的树选两个根结点最小的树,作为作为lchild和和rchild,构构成一新的二叉树成一新的二叉树;(3)在在F中删除这两棵树中删除这两棵树,将新二叉树将新二叉树=F (4)重复重复(2)和和(3)37第37页，共39页，编辑于2022年，星期六.得到一棵得到一棵Huffman树后树后,约定左支为约定左支为0(1),右支为右支为1(0).编码过程编码过程:从叶子结点出发从叶子结点出发,走一条从叶子到要的路径走一条从叶子到要的路径.译码过程译码过程:需从根出发走一条从根到叶子的路径需从根出发走一条从根到叶子的路径.38第38页，共39页，编辑于2022年，星期六例例8.给定集合给定集合15,3,14,2,6,9,16,17(1)用用表示外部结点，用表示外部结点，用表示内部结点，构造相表示内部结点，构造相应的应的huffman树树(2)计算它的带权路径长度计算它的带权路径长度(3)写出它的写出它的huffman编码编码(4)huffman编码常用来译码，请用语言叙述写出其编码常用来译码，请用语言叙述写出其译码的过程译码的过程39第39页，共39页，编辑于2022年，星期六