数据结构与算法分析 第5章.ppt

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

1、第第5 5章章 树树 5.1 5.1 树的概念树的概念 5.2 5.2 二叉树的定义二叉树的定义5.3 5.3 二叉树的性质二叉树的性质5.4 5.4 二叉树的存储结构二叉树的存储结构5.5 5.5 二叉树的遍历二叉树的遍历5.6 5.6 线索二叉树线索二叉树 5.7 5.7 树和二叉树的转换及树的存储结构树和二叉树的转换及树的存储结构 5.8 5.8 哈夫曼树及其应用哈夫曼树及其应用5.1 5.1 树的概念树的概念5.1.1 5.1.1 树的定义树的定义 树是一种数据结构，表示为TREE=（D，R）；其中：D是具有相同特性的数据元素的集合；R是元素集合D上的关系集合，如果D中只含有一个数据元

2、素，则R为空集。或者用递归定义为：树是N（N0）个结点的有限集合，其唯一关系具有下列属性：集合中存在唯一的一个结点，称为树根，该结点没有前驱；除根结点外，其余结点分为M（M0）个互不相交的集合，其中每一个集合都是一棵树，并称其为根的子树。5.1 5.1 树的概念树的概念5.1.2 5.1.2 基本术语基本术语一个结点的子树个数称为该结点的度（一个结点的子树个数称为该结点的度（degree）一棵树中结点度的最大值称为该树的度一棵树中结点度的最大值称为该树的度度为零的结点称为叶子（度为零的结点称为叶子（leafleaf）或者终端结点或者终端结点 度不为零的结点称为分支结点或者非终端结点度不为零的结

3、点称为分支结点或者非终端结点除根结点之外的分支结点统称为内部结点除根结点之外的分支结点统称为内部结点 树中结点的后继结点称为儿子（树中结点的后继结点称为儿子（childchild）或者儿子结点，或者儿子结点，简称儿子简称儿子 结点的前驱结点称为儿子的双亲（结点的前驱结点称为儿子的双亲（parents）或者父亲结或者父亲结点，简称父亲点，简称父亲同一个父亲的儿子互称为兄弟（同一个父亲的儿子互称为兄弟（sibling）5.1 5.1 树的概念树的概念若树中存在一个结点序列若树中存在一个结点序列k k1 1k k2 2k k3 3k kj j，使得使得k ki i是是k ki i+1+1的父亲的父亲

4、（11i ij j），），则称该结点序列是从则称该结点序列是从k k1 1到到k kj j的一条路径的一条路径（pathpath）或者道路或者道路 路径的长度等于路径的长度等于j-1j-1，它是该路径所经过的边（即连接两它是该路径所经过的边（即连接两个结点的线段）的数目个结点的线段）的数目若树中结点若树中结点k k到到k ks s存在一条路径，则称存在一条路径，则称k k是是k ks s的祖先的祖先（AncestorAncestor），），k ks s是是k k的子孙（的子孙（DescendantDescendant）结点的层数（结点的层数（levellevel）是从根开始算起的。设根结点的层

5、是从根开始算起的。设根结点的层数为数为1 1，其余结点的层数等于其父亲结点的层数加，其余结点的层数等于其父亲结点的层数加1 1树中结点的最大层数称为树的高度（树中结点的最大层数称为树的高度（HeightHeight）或者深度或者深度（DepthDepth）5.1 5.1 树的概念树的概念若把树中每个结点的各子树看成从左到右有次序的（即若把树中每个结点的各子树看成从左到右有次序的（即不能互换），则称该树为有序树（不能互换），则称该树为有序树（OrderedTree）；）；否则否则称为无序树（称为无序树（UnorderedTree）森林（森林（ForestForest）是是m m（m0m0）棵互不

6、相交树的集合棵互不相交树的集合 树形结构是非线性结构树形结构是非线性结构 祖先与子孙的关系则是对父子关系的延伸，其定义了树祖先与子孙的关系则是对父子关系的延伸，其定义了树中结点的纵向次序中结点的纵向次序 如果规定如果规定k1和和k2是兄弟，且是兄弟，且k1在在k2的左边，则的左边，则k1的任一子的任一子孙都在孙都在k2的任一子孙的左边，则定义了树中结点的横向的任一子孙的左边，则定义了树中结点的横向次序次序 5.2 5.2 二叉树的定义二叉树的定义 二叉树是由n（n0）结点的有限集合，此集合或者为空，或者由一个根结点加上两棵分别称为左、右子树的，互不相交的二叉树组成二叉树可以为空集，因此根可以有

7、空的左子树或者右子树，亦或者左、右子树皆为空 从二叉树定义中可以看出，二叉树结构与一般树结构区别如下：（1）二叉树可以为空树，即不包含任何结点；一般树至少应有一个结点。（2）二叉树区别于度数为2的有序树，在二叉树中允许某些结点只有右子树而没有左子树；而有序树中，一个结点如果没有第一子树就不可能有第二子树的存在。5.3 5.3 二叉树的性质二叉树的性质 5.3.1 5.3.1 二叉树性质二叉树性质性质1二叉树第i（i1）层上的结点数最多为2i-1 性质2高度为k的二叉树最多有2k-1个结点 性质3对任何二叉树T，设n0、n1、n2分别表示度数为0、1、2的结点个数，则n0=n2+1 5.3 5.

8、3 二叉树的性质二叉树的性质性质4具有n个结点的完全二叉树（包括满二叉树）的高度为（或者）性质5满二叉树原理非空满二叉树的叶结点数等于其分支结点数加1性质6一棵非空二叉树空子树的数目等于其结点数目加1 5.3 5.3 二叉树的性质二叉树的性质5.3.2 5.3.2 二叉树的抽象数据类型二叉树的抽象数据类型 下列给出一个二叉树结点的JAVA接口，称之为BinNode。BinNode类中存储了指向Object类的引用。创建二叉树时，可以根据需要而采用实际的数据类型。成员函数包括返回元素的值，返回左、右结点指针，设置元素的值，以了标志该结点是否为叶结点。interface BinNode /二叉树结

9、点的抽象数据类型/返回并设置元素值public Object element();public Object setElement(Object v);5.3 5.3 二叉树的性质二叉树的性质/返回并设置左孩子publicBinnodeleft();publicBinnodesetLeft(BinNodep);/返回并设置右孩子publicBinnoderight();publicBinnodesetRight(BinNodep);/判断是否为叶结点publicbooleanisLeaf();/interfaceBinNode5.4 5.4 二叉树的存储结构二叉树的存储结构 5.4.1 5.4

10、.1 二叉树顺序存储结构二叉树顺序存储结构 二叉树的顺序存储结构是把二叉树的所有结点按照一定的次序顺序存储到一组包含n个存储单元的空间中 二叉树顺序存储的原则是：不管给定的二叉树是不是完全二叉树，都看作完全二叉树，即按完全二叉树的层次次序（从上到下，从左到右）把各结点依次存入数组中 5.4 5.4 二叉树的存储结构二叉树的存储结构在顺序存储结构中，由某结点的存储单元地址可以推出其父亲、左儿子、右儿子及兄弟的地址，假设给定结点的地址为I，则：（1）若I1，则该结点是为根结点，无父亲。（2）若I1，则该结点的父亲结点地址为I2的整数部分。（3）若2In，则该结点的左儿子结点地址为2I，否则该结点无

11、左儿子。（4）若2I+1n，则该结点的右儿子结点地址为2I+1，否则该结点无右儿子。（5）若I为奇数（不为1），则该结点的左兄弟为I-1。（6）若I为偶数（不为n），则该结点的右兄弟为I+1。5.4 5.4 二叉树的存储结构二叉树的存储结构5.4.2 5.4.2 二叉树的链接存储结构二叉树的链接存储结构 二叉树的链接存储中每个结点由数据域和指针域两部分组成 二叉树每个结点的指针域有两个，一个指向左儿子，一个指向右儿子 还需一个链表的头指针指向根结点 二叉树的链接存储结构也称为二叉链表 若二叉树为空，则根结点为NULL 5.4 5.4 二叉树的存储结构二叉树的存储结构5.4.3 5.4.3 二叉

12、树的实现举例二叉树的实现举例1以数组方式实现二叉树以数组方式实现二叉树 先依次序输入元素值，一一建立二叉树数组，其中根结先依次序输入元素值，一一建立二叉树数组，其中根结点的下标为点的下标为1，其余结点的建立则遵循左小（，其余结点的建立则遵循左小（level*2）右右大（大（level*2+1）的原则，最后输出所建立二叉树的结点的原则，最后输出所建立二叉树的结点内容。内容。importConsoleReader.*;/引入数据输入类引入数据输入类publicclassbitree01publicstaticvoidmain(Stringargs)5.4 5.4 二叉树的存储结构二叉树的存储结构i

13、nti；/循环变量intIndex=1;/数组下标变量intData;/读取输入值的临时变量BiTreeArrayBiTree=newBitreeArray();/声明二叉树数组System.out.printin(“请输入二叉树数据元素（输入0退出！）:”);ConsoleReaderconsole=newConsoleReader(System.in);do/依次序读取结点值System.out.print(“Data”+Index+”:”);Data=console.readInt();Bitree.Create(Data);/建立二叉树Index+;while(Data!=0);5.4

14、 5.4 二叉树的存储结构二叉树的存储结构BiTree.PrintAll();/输出二叉树的结点值classBiTreeArrayintMaxSize=16;intABiTree=newintMaxSize;publicvoidBiTreeArray()inti;for(i=0;iMaxSize;i+)ABiTreei=0;5.4 5.4 二叉树的存储结构二叉树的存储结构/建立二叉树publicvoidCreate(intData)inti;intLevel;/树的层数Level=1;/从层1开始建立while(ABiTreeLevel!=0)/判断是否存在子树ifDataABiTreeLev

15、el)/判断是左子树？还是右子树？Level=Level*2;/左子树elseLevel=Level*2+1;/右子树ABiTreeLevel=Data;/将元素值插入结点 5.4 5.4 二叉树的存储结构二叉树的存储结构/输出二叉树结点值publicvoidPrintAll()inti;System.out.println(“二叉树结点值依次是：”)；for(i=1;iMaxSize;i+)System.out.print(“Node”+i);System.out.println(“:“+ABiTreei+”);5.4 5.4 二叉树的存储结构二叉树的存储结构2数组方式实现二叉树的链接存储数

16、组方式实现二叉树的链接存储 以下示例为以结点数组方式建立二叉树，并输出结点内容。依次序输入结点值，并存入数组中，再一一建立成二叉树数组，其中根结点的下标为0，其余结点的建立则遵守左字段存左子结点的下标，右字段存右子结点下标的原则，最后输出所建立二叉树的结点值。importConsoleReader.*;/引入己定义的数据输入类publicclassbitree02publicstaticvoidmain(StringargS)5.4 5.4 二叉树的存储结构二叉树的存储结构inti;/循环变量intindex=l;/数组下标变量intdata;/输入值所使用的临时变量BiTreeArrayBi

17、Tree=newBiTreeArray();/声明二叉树数组System.out.println(请输入二叉树结点值(输入0退出0)：”);ConsolReaderconsole=newConsoleReader(SyStem.in)；System.out.print(“Data“+index+”：“);Data=console.readInt();BiTree.TreeData0=data；index+；5.4 5.4 二叉树的存储结构二叉树的存储结构while(true)/读取输入值System.out.print(“Data“+index+”：“);data=console.readIn

18、t()；if(data=0)break;BiTree.Create(data);/建立二叉树index+；BiTree.PrintAll();/输出二叉树的内容5.4 5.4 二叉树的存储结构二叉树的存储结构classBiTreeArrayintMaxSize=16;intTreeData=newintMaxSize;intRightNode=newintMaxSize;intLeftNode=newintMaxSize;publicBiTreeArray()inti;/循环变量for(i=0;iTreeDataLevel)/右子树是否有下一层if(RightNodelevel!=-1)lev

19、el=RightNodelevel;5.4 5.4 二叉树的存储结构二叉树的存储结构elsePosition=-1;/设置为右子树break；else/左子树是否有下一阶层if(LeftNodelevel!=-1)level=LeftNodelevel;elsePosition=1;/设置为左子树break;5.4 5.4 二叉树的存储结构二叉树的存储结构if(Position=1)/建立结点的左右连结LeftNodelevel=i;/连结左子树elseRightNodelevel=i;/连结右子树/打印所有二叉树结点值publicvoidPrintAll()inti;System.out.p

20、rintln(“二叉树结点值：”);System.out.println(“lchilddatarchild”);for(i=0；ileft)(3)往右走，递归处理preorder(root-right)Java语言实现示例：voidpreorder(BinNodert)/rt是子树的根if(rt=null)return;/空子树visit(rt);preorder(rt.left();preorder(rt.right();5.5 5.5 二叉树的遍历二叉树的遍历5.5.2 5.5.2 二叉树的中序遍历二叉树的中序遍历 中序遍历(Inordertraversal)是先遍历左子树，再遍历根结点

21、，最后才遍历右子树 若二叉树非空，则依次序进行如下操作：(1)中序遍历左子树；(2)访问根结点；(3)中序遍历右子树。5.5 5.5 二叉树的遍历二叉树的遍历中序遍历(inorder)的递归算法如下：if指向根结点的指针=NULLthen此为空树，遍历结束else(1)往左走，递归处理inorder(root-left)(2)处理当前的结点(3)往右走，递归处理inorder(root-right)Java语言实现示例：voidinorder(BinNodert)/rt是子树的根if(rt=null)return;/空子树inorder(rt.left();visit(rt);inorder(

22、rt.right();5.5 5.5 二叉树的遍历二叉树的遍历5.5.3 5.5.3 二叉树的后序遍历二叉树的后序遍历 后序遍历(Postordertraversal)是先遍历左子树，再遍历右子树，最后才遍历根结点 若二叉树非空，则依次序进行如下操作：（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。5.5 5.5 二叉树的遍历二叉树的遍历后序遍历(postorder)的递归算法如下：if指向根结点的指针=NULLthen此为空树，遍历结束else(1)往左走，递归处理postorder(root-left)(2)往右走，递归处理postorder(root-right)(3)处理

23、目前的结点Java语言实现示例：voidpostorder(BinNodert)/rt是子树的根if(rt=null)return;/空子树postorder(rt.left();postorder(rt.right();visit(rt);5.5 5.5 二叉树的遍历二叉树的遍历5.5.4 5.5.4 二叉树的层次遍历二叉树的层次遍历 层次遍历是指从二叉树的第一层（根结点）开始，从上至下逐层遍历，在同一层中，则按从左到右的顺序对结点逐个访问。对一棵非空的二叉树进行层次遍历，可按照如下步骤进行：1初始化一个队列；2二叉树的根结点放入队列；3重复步骤47直至队列为空；4从队列中取出一个结点x；5

24、访问结点x；6如果x存在左子结点，将左子结点放入队列；7如果x存在右子结点，将右子结点放入队列。5.6 5.6 线索二叉树线索二叉树 5.6.1 5.6.1 二叉树的线索化二叉树的线索化当我们对二叉树以某种方式遍历后，就可以得到二叉树中所有结点的一个线性序列，在这种意义下，二叉树中的结点就有了前趋结点和后继结点。在大多数情况下，寻找结点的前趋结点或后继结点都需要遍历二叉树。为方便寻找二叉树中结点的前趋结点或后继结点，可以通过一次遍历记下各结点在遍历所得的线性序列中的相对位置 可以设法利用空指针域来存放结点的前驱结点和后继结点的指针信息，这种附加的指针称为“线索”。加上了的二叉链表称为线索链表，

25、相应的二叉树称为线索二叉树（ThreadedBinaryTree）。5.6 5.6 线索二叉树线索二叉树为了区分一个结点的指针是指向其儿子的指针、还是指向其前趋或者后继的线索，可以在每个结点上增加两个线索标志域ltag和rtag 这样线索链表的结点结构为：其中：左线索标志ltag=0；/lchild是指向结点的左儿子的指针ltag=1；/lchild是指向结点的前趋结点的左线索右线索标志rtag=0；/rchild是指向结点的右儿子的指针rtag=1；/rchild是指向结点的后继结点的右线索每个标志位令其只占一个bit，这样就只需增加很少的存储空间 一棵二叉树以某种方式遍历并使其变成线索二叉

26、树的过程称为二叉树的线索化 lchild ltag data rtag rchild 5.6 5.6 线索二叉树线索二叉树对同一棵二叉树遍历的方式不同，所得到的线索树也不同，二叉树有前序、中序和后序三种遍历方式，所以线索树也有前序线索二叉树、中序线索二叉树和后序线索二叉树三种通常在二叉树中增加一个与树中结点相同类型的头结点，令头结点的信息域为空，其lchild域指向二叉树的根结点，当二叉树为空时，lchild域值为空；其rchild域指向以某种方式遍历二叉树时最后访问的结点，当二叉树为空时，rchild域指向该结点本身，同时令原来指向二叉树根结点的头指针指向该头结点，以某种方式遍历二叉树时第一

27、个被访问结点的左指针域和最后一个被访问结点的右指针域的值如果是线索，也指向该头结点。5.6 5.6 线索二叉树线索二叉树5.6.2 5.6.2 线索二叉树上的运算线索二叉树上的运算 下面以中序线索二叉树为例,讨论线索二叉树的运算 1建立一棵中序线索二叉树 2在中序线索二叉树上寻找任意结点的中序前驱结点 3在中序线索二叉树上寻找任意结点的中序后继结点。4在中序线索二叉树中查找值为x的结点。5在中序线索二叉树上插入结点。5.7 5.7 5.7 5.7 树和二叉树的转换及树的存储结构树和二叉树的转换及树的存储结构树和二叉树的转换及树的存储结构树和二叉树的转换及树的存储结构 5.7.1 5.7.1 树

28、转换为二叉树树转换为二叉树 将一棵树转换为二叉树的方法是：1树中所有相邻兄弟之间加一条连线；2对树中的每个结点，只保留它与第一个儿子结点之间的连线，删去它与其它儿子结点之间的连线。3以树的根结点为轴心，将整棵树顺时针转动一定的角度，使之结构层次分明。5.7 5.7 5.7 5.7 树和二叉树的转换及树的存储结构树和二叉树的转换及树的存储结构树和二叉树的转换及树的存储结构树和二叉树的转换及树的存储结构5.7.2 5.7.2 二叉树还原为树二叉树还原为树 树转换为二叉树这一转换过程是可逆的，可以依据二叉树的根结点有无右儿子结点，将一棵二叉树还原为树，具体方法如下：1若某结点是其双亲的左儿子，则把该

29、结点的右儿子、右儿子的右儿子、都与该结点的双亲结点用线连起来；2删掉原二叉树中所有的双亲结点与右儿子结点的连线；3整理由(1)、(2)两步所得到的树，使之结构层次分明。5.7 5.7 5.7 5.7 树和二叉树的转换及树的存储结构树和二叉树的转换及树的存储结构树和二叉树的转换及树的存储结构树和二叉树的转换及树的存储结构5.7.3 5.7.3 森林转换为二叉树森林转换为二叉树森林是若干棵树的集合，森林亦可用二叉树表示。森林是若干棵树的集合，森林亦可用二叉树表示。森林转换为二叉树的方法如下：森林转换为二叉树的方法如下：1将森林中的每棵树转换成相应的二叉树；将森林中的每棵树转换成相应的二叉树；2第第

30、一一棵棵二二叉叉树树不不动动，从从第第二二棵棵二二叉叉树树开开始始，依依次次序序将将后后一一棵棵二二叉叉树树的的根根结结点点作作为为前前一一棵棵二二叉叉树树根根结结点点的的右右孩孩子子，当当所所有有的的二二叉叉树树连连在一起后，这样所得到的二叉树就是由森林转换得到的二叉树。在一起后，这样所得到的二叉树就是由森林转换得到的二叉树。设设F=T1，T2，Tn是是森森林林，其其所所对对应应的的二二叉叉树树为为B(T1，T2，Tn)，有：有：1若若n=0，即即F为空，那么为空，那么B亦为空；亦为空；2若若n0，则则二二叉叉树树的的根根结结点点为为树树T1的的根根结结点点，其其左左子子树树为为B(T11，

31、T12，T1m)，其其中中T11，T12，T1m是是根根结结点点T1的的子子树树，而而其其右右子树为子树为B(T2，T3，Tn)。5.7 5.7 5.7 5.7 树和二叉树的转换及树的存储结构树和二叉树的转换及树的存储结构树和二叉树的转换及树的存储结构树和二叉树的转换及树的存储结构5.7.4 5.7.4 树的遍历树的遍历 1先根遍历先根遍历的定义为：(1)访问根结点；(2)按照从左到右的顺序先根遍历根结点的每一棵子树。2后根遍历后根遍历的定义为：(1)按照从左到右的顺序后根遍历根结点的每一棵子树；(2)访问根结点。5.7 5.7 5.7 5.7 树和二叉树的转换及树的存储结构树和二叉树的转换及

32、树的存储结构树和二叉树的转换及树的存储结构树和二叉树的转换及树的存储结构5.7.5 5.7.5 森林的遍历森林的遍历 1前序遍历前序遍历的定义为：(1)访问森林中第一棵树的根结点；(2)前序遍历第一棵树的根结点的子树森林；(3)前序遍历剩余的其他子森林。2中序遍历中序遍历的定义为：(1)中序遍历第一棵树的根结点的子树森林；(2)访问森林中第一棵的根结点；(3)中序遍历剩余的其他子森林。5.7 5.7 5.7 5.7 树和二叉树的转换及树的存储结构树和二叉树的转换及树的存储结构树和二叉树的转换及树的存储结构树和二叉树的转换及树的存储结构5.7.6 5.7.6 树的存储结构树的存储结构 1双亲链表

33、表示法2孩子链表表示法3双亲孩子链表表示法 4孩子兄弟链表表示法 5.8 5.8 哈夫曼树及其应用哈夫曼树及其应用 5.8.1 5.8.1 哈夫曼树的基本概念哈夫曼树的基本概念1 1路径和路径长度路径和路径长度在在一一棵棵树树中中，从从一一个个结结点点往往下下可可以以达达到到的的孩孩子子或或子子孙孙结结点点之之间间的的通通路，称为路径。通路中分支的数目称为路径长度。路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为若规定根结点的层数为1 1，则从根结点到第，则从根结点到第L L层结点的路径长度为层结点的路径长度为L-1L-1。2 2结点的权及带权路径长度结点的权及带权路径长度若若

34、将将树树中中结结点点赋赋给给一一个个有有着着某某种种含含义义的的数数值值，则则这这个个数数值值称称为为该该结结点的权。点的权。结结点点的的带带权权路路径径长长度度为为：从从根根结结点点到到该该结结点点之之间间的的路路径径长长度度与与该该结结点的权的乘积。点的权的乘积。3 3树的带权路径长度树的带权路径长度树树的的带带权权路路径径长长度度规规定定为为所所有有叶叶子子结结点点的的带带权权路路径径长长度度之之和和，记记为为WPLWPL。5.8 5.8 哈夫曼树及其应用哈夫曼树及其应用4 4给给定定n n个个权权值值作作为为n n个个叶叶子子结结点点，构构造造一一棵棵二二叉叉树树，若若带带权权路路径径

35、长长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树。度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树。5 5哈夫曼树的构造哈夫曼树的构造假假设设有有n n个个权权值值，则则构构造造出出的的哈哈夫夫曼曼树树有有n n个个叶叶子子结结点点。n n个个权权值值分分别别设为设为W W1 1、W W2 2、W Wn n,则哈夫曼树的构造规则为：则哈夫曼树的构造规则为：(1)(1)将将W W1 1、W W2 2、W Wn n看成是有看成是有n n棵树的森林棵树的森林(每棵树仅有一个结点每棵树仅有一个结点)；(2)(2)在在森森林林中中选选出出两两个个根根结结点点的的权权值值最最小小的的树树合

36、合并并，作作为为一一棵棵新新树树的的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；(3)(3)从森林中删除选取的两棵树，并将新树加入森林；从森林中删除选取的两棵树，并将新树加入森林；(4)(4)重复重复(2)(2)、(3)(3)步，直到森林中只剩一棵树为止，该树即为我们所步，直到森林中只剩一棵树为止，该树即为我们所求得的哈夫曼树。求得的哈夫曼树。5.8 5.8 哈夫曼树及其应用哈夫曼树及其应用5.8.2 5.8.2 哈夫曼树在编码问题中的应用哈夫曼树在编码问题中的应用 哈夫曼树可用于构造使电文的编码总长最短的编码方案 具

37、体作法如下：设需要编码的字符集合为d1，d2，dn，而它们在电文中出现的次数或频率集合为w1，w2，wn，以d1，d2，dn作为叶结点，w1，w2，wn作为它们的权值构造一棵哈夫曼树，规定哈夫曼树中的左分支代表“0”，右分支代表“1”，则从根结点到每个叶结点所经过的路径分支组成的0或1序列便为该结点对应字符的编码，称之为哈夫曼编码。5.8 5.8 哈夫曼树及其应用哈夫曼树及其应用在哈夫曼编码树中，树的带权路径长度的含义是各个字符的码长与其出现次数的乘积和，也就是电文的代码总长 因为哈夫曼算法构造的是带权路径长度最小的二叉树，所以采用哈夫曼树构造的编码是一种能使电文代码总长最短的不等长编码 在哈夫曼树中，由于每个字符结点都是叶结点，它们不可能在根结点到其它字符结点的路径上，所以一个字符的哈夫曼编码不可能是另一个字符的哈夫曼编码的前缀，从而保证了译码的非二义性。实现哈夫曼编码的算法可分为两大部分，构造哈夫曼树和在哈夫曼树上求叶结点的编码。