第5章 树与二叉树.ppt

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

1、第第5章章 树与二叉树树与二叉树5.1 树的基本概念树的基本概念5.2 二叉树及其基本概念二叉树及其基本概念5.3二叉树的存储结构二叉树的存储结构5.4 遍历二叉树遍历二叉树*5.5 树的存储结构树的存储结构5.6 森林与二叉树的转换森林与二叉树的转换5.7 赫夫曼树及其应用赫夫曼树及其应用 第5章 树与二叉数 第 页 2007-7-29第第5章章 树与二叉树树与二叉树 5.1树的基本概念树的基本概念 树树(tree)是一种简单的是一种简单的非线性结构非线性结构。在树。在树这种数据结构中，所有数据元素之间的关系这种数据结构中，所有数据元素之间的关系具有明显的层次特性，具有明显的层次特性，如图如

2、图5-1所示。所示。在树的图形表示中，通常用一个圆圈表示在树的图形表示中，通常用一个圆圈表示一个结点，结点的名字写在圆圈内或是圆圈一个结点，结点的名字写在圆圈内或是圆圈旁边，以区别于其他的结点并规定在用直线旁边，以区别于其他的结点并规定在用直线连起来的两端结点中，总是认为上端结点是连起来的两端结点中，总是认为上端结点是前件，下端结点是后件。前件，下端结点是后件。树这种数据结构在客观世界中大量存在，例这种数据结构在客观世界中大量存在，例如行政组织机构、家谱等都可用树形象表示。如行政组织机构、家谱等都可用树形象表示。第1层 第2层 第3层 第4层 图图5-15-1 树的图形表示树的图形表示 ACD

3、BEFGHIJMKL第5章 树与二叉数 第 页 2007-7-29 1.1.树的定义树的定义 树（树（TreeTree）是）是n(n0)n(n0)个结点的有限集个结点的有限集T T。当。当n=0n=0时，称为空树；时，称为空树；当当 n n0 0 时时 ，该集合满足如下条件：，该集合满足如下条件：有且仅有一个特定的称为根（有且仅有一个特定的称为根（rootroot）的结点；的结点；其其余余的的结结点点可可分分为为m m（m m 0 0）个个互互不不相相交交的的子子集集T T1 1，T T2 2，.，T Tm m，其其中中每每个个子子集集本本身身又又是是一一棵棵树树，并并称其为根的子树（称其为根

4、的子树（SubTreeSubTree）。）。例如，图例如，图5-15-1是一棵具有是一棵具有1313个结点的树，其中个结点的树，其中 A A是根，是根，余下的余下的1212个结点分成个结点分成3 3个互不相交的子集：个互不相交的子集：T T1 1=B=B，E E，F F，G G，K K，L L，T T2 2=C=C，H H，T T3 3=D=D，I I，J J，M M。T T1 1、T T2 2 、T T3 3都是树，而且是根结点都是树，而且是根结点A A的子树。的子树。第5章 树与二叉数 第 页 2007-7-29 2.2.树的基本术语树的基本术语 1 1）结点的度：）结点的度：一个结点的子

5、树数称为该结一个结点的子树数称为该结点的度点的度 。2 2）树的度：）树的度：树的所有结点中的最大的度称树的所有结点中的最大的度称为树的度。为树的度。3 3）叶子：）叶子：树中度为树中度为0 0的结点称为叶子结点或的结点称为叶子结点或终端结点，简称叶子终端结点，简称叶子 。4 4）分支结点：）分支结点：树中度不为树中度不为0 0的结点称为分支的结点称为分支结点或非终端结点。结点或非终端结点。5 5）双亲和孩子：）双亲和孩子：结点的子树的根称为该结结点的子树的根称为该结点的孩子点的孩子，相应地，该结点称为孩子的双亲。相应地，该结点称为孩子的双亲。第5章 树与二叉数 第 页 2007-7-29 6

6、 6）结点的层：）结点的层：规定树的根结点的层（规定树的根结点的层（LevelLevel）为，为，其余任一结点的层等于它的双亲的层加。其余任一结点的层等于它的双亲的层加。7 7）树的深度：）树的深度：树中各结点的层的最大值称为树的树中各结点的层的最大值称为树的深度（深度（DepthDepth）或高度。或高度。）兄弟和堂兄弟：）兄弟和堂兄弟：同一双亲的孩子之间互称为兄同一双亲的孩子之间互称为兄弟（弟（SiblingSibling）。）。其双亲在同一层的结点互为堂兄弟。其双亲在同一层的结点互为堂兄弟。9 9）祖先和子孙：）祖先和子孙：一个结点的祖先是指从该结点到一个结点的祖先是指从该结点到树的根所

7、经分支上的所有结点。一个结点的子树上的树的根所经分支上的所有结点。一个结点的子树上的所有结点称为该结点的子孙。所有结点称为该结点的子孙。1010）有序树和无序树：）有序树和无序树：如果树中任一结点的各棵子如果树中任一结点的各棵子树规定从左至右是有次序的，即不能互换位置，则称树规定从左至右是有次序的，即不能互换位置，则称该树为有序树，否则称为无序树（如图该树为有序树，否则称为无序树（如图5-35-3所示）。所示）。第5章 树与二叉数 第 页 2007-7-29 1111）森林：）森林：n n（n0n0）棵互不相交的树的集合称为棵互不相交的树的集合称为森林森林 。删去一棵树的根结点便得到一个森林。

8、删去一棵树的根结点便得到一个森林 。图5-3 两棵不同的有序树ABCDBDAC5.2 5.2 二叉树及其基本性质二叉树及其基本性质 1.1.二叉树的定义二叉树的定义第5章 树与二叉数 第 页 2007-7-29 二叉树是二叉树是n n（n0n0）个结点的有限集，它或者是空个结点的有限集，它或者是空集（集（n=0n=0），），或者是由一个根结点和两棵互不相交或者是由一个根结点和两棵互不相交且分别称为根的左子树和右子树的二叉树组成。这是且分别称为根的左子树和右子树的二叉树组成。这是二叉树的递归定义。二叉树的递归定义。二叉树共有种基本形态，如图二叉树共有种基本形态，如图5-45-4所示所示 (a)(

9、b)(c)(d)(e)图图5-45-4 二叉树的五种基本形态二叉树的五种基本形态 (a)空二叉树 (b)仅有根结点的二叉树 (c)右子树为空的二叉树(d)左子树为空的二叉树 (e)左、右子树非空的二叉树AABABABC第5章 树与二叉数 第 页 2007-7-292.2.二叉树的基本性质二叉树的基本性质性质性质:在二叉树的第在二叉树的第i层上层上,最多有最多有2i-1个结点（个结点（i1）性质性质:深度为深度为k的二叉树最多有的二叉树最多有2k-1个结点。个结点。显然将第显然将第1至第至第i层的最多结点数相加，即可得到此层的最多结点数相加，即可得到此结果结果20+21+2k-1=2k-1性质：

10、性质：在任意一棵二叉树中，若度为在任意一棵二叉树中，若度为0的结点（即叶的结点（即叶子结点）数为子结点）数为n0，度为度为2的结点数为的结点数为n2，则，则n0=n2+1。设设n1为二叉树中度为为二叉树中度为1的结点数的结点数，n为二叉树的总结为二叉树的总结点数，因为点数，因为n=n1+2n2+1=n0+n1+n2 可得可得n0=n2+1第5章 树与二叉数 第 页 2007-7-29满二叉树满二叉树：一棵深度为一棵深度为 k 且具有且具有 2k-1 个结点的二叉个结点的二叉数数。（对满二叉树的结点进行顺序编号，约定编号。（对满二叉树的结点进行顺序编号，约定编号从根结点起，自上而下，同层的结点从

11、左至右）从根结点起，自上而下，同层的结点从左至右）完全二叉树完全二叉树：深度为深度为K，有，有n个结点的二叉树，当且个结点的二叉树，当且仅当其每一个结点都与深度为仅当其每一个结点都与深度为K的满二叉树中编号从的满二叉树中编号从1至至n的结点一一对应时。（完全二叉树除最后一层的结点一一对应时。（完全二叉树除最后一层外，每一层上的结点数都达到最大值外，每一层上的结点数都达到最大值，在最后一层，在最后一层上可能缺少右边的若干结点。显然满二叉树是完全上可能缺少右边的若干结点。显然满二叉树是完全二叉树二叉树）。）。非完全二叉树：非完全二叉树：除完全二叉树外的其它二叉树除完全二叉树外的其它二叉树。第5章

12、树与二叉数 第 页 2007-7-29在图在图5-5中，中，(a)为满而叉树为满而叉树(b)为完全二叉树为完全二叉树(c)为为非完全二叉树。非完全二叉树。(a)满二叉树 (b)完全二叉树 (c)非完全二叉树 图图5-5 5-5 特殊形态的二叉树特殊形态的二叉树123456123568741234567第5章 树与二叉数 第 页 2007-7-29性质：性质：具有具有 n n个结点的完全二叉树的深度为个结点的完全二叉树的深度为 log2n +1+1。其中其中 log2n 表示表示不超过不超过log2n的的最大整数。最大整数。事事实实上上，设设完完全全二二叉叉树树的的深深度度为为k k，由由完完全

13、全二二叉叉树树的的定定义义知知，它它的的k-1k-1层层，是是深深度度为为 k-1k-1的的满满二二叉叉树树；由由性性质质2 2知知，一一共共有有2k-1-1个个结结点点；又又因因第第k k层层上上还还有有若若干干结结点点，所所以以该该完完全全二二叉叉树树总总的的结结点点数数n n2 2k-1-1 1，另另外外，总总结结点点数数n2n2k-1-1，从从而而可可得得2 2k-111 n n 22k11，整整理理得得到到 2 2k-1 n n 22k 。对对此此不不等等式式的的各各项项，同同取取以以2 2为为底底的的对对数数后后有有k-1k-1log2nk k 成成立，即立，即k-1=k-1=lo

14、g2n 或或k=log2n +1+1。采用顺序编号的完全二叉树还具有以下性质：采用顺序编号的完全二叉树还具有以下性质：第5章 树与二叉数 第 页 2007-7-29 若若i=1i=1，则则结结点点i i是是二二叉叉树树的的根根，无无双双亲亲；如如果果i i1 1，则该结点的父结点编号为则该结点的父结点编号为 i/2i/2。若若2in2in，则则结结点点i i的的左左孩孩子子是是结结点点2i2i；若若2i2in n，则结点则结点i i无左孩子。无左孩子。若若2i+1n 2i+1n，则则结结点点i i的的右右孩孩子子是是结结点点2i+12i+1；若若2i+12i+1n n，则结点则结点i i无右孩

15、子。无右孩子。根据完全二叉树的这些性质，很容易确定任一根据完全二叉树的这些性质，很容易确定任一结点的双亲、左孩子和右孩子的位置。结点的双亲、左孩子和右孩子的位置。5.35.3二叉树的存储结构二叉树的存储结构 第5章 树与二叉数 第 页 2007-7-291.1.顺序存储结构顺序存储结构 该方法是把二叉树的所有结点，按从上至下、从左该方法是把二叉树的所有结点，按从上至下、从左至右的顺序，存储在一块地址连续的存储单元中。通至右的顺序，存储在一块地址连续的存储单元中。通常，用一维数组作为存储结构。常，用一维数组作为存储结构。0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8

16、9 10 图图5-65-6 完全二叉树的顺序存储结构完全二叉树的顺序存储结构 图图5-75-7 非完全二叉树的顺序存储结构非完全二叉树的顺序存储结构ABCDEHIFG/A B C D E F G H IABCDEF/A B C D E F第5章 树与二叉数 第 页 2007-7-29 对于一般的二叉树来说，为了能够用结点在对于一般的二叉树来说，为了能够用结点在向量中的相对位置来表示结点之间的逻辑关系，向量中的相对位置来表示结点之间的逻辑关系，也必须按完全二叉树的形式来存储树中的结点。也必须按完全二叉树的形式来存储树中的结点。例如，图例如，图5-7所示所示。容易看出，一般的二叉树用顺序存储结构容

17、容易看出，一般的二叉树用顺序存储结构容易造成存储空间的浪费。在最坏的情况下，一易造成存储空间的浪费。在最坏的情况下，一个深度为个深度为k且只有且只有k个结点的右单枝树需要个结点的右单枝树需要2k-1个结点的存储空间，而其中只有个结点的存储空间，而其中只有k个位置上存个位置上存入了结点，空间利用率仅为入了结点，空间利用率仅为k/(2k-1)。第5章 树与二叉数 第 页 2007-7-29abdefc右单支二叉树 为克服顺序存储可能浪费存储空间的缺点，为克服顺序存储可能浪费存储空间的缺点，二叉树采用链式存储结构。二叉树采用链式存储结构。第5章 树与二叉数 第 页 2007-7-29 .链式存储结构

18、链式存储结构 二叉链表二叉链表结点的结构如图结点的结构如图5-8所示。其中所示。其中data域存储结点的值，域存储结点的值，lchild 域及域及rchild域域分别存储指向左孩子和右孩子的指针。若不分别存储指向左孩子和右孩子的指针。若不存在左孩子或右孩子，则其相应的指针域为存在左孩子或右孩子，则其相应的指针域为空指针。此外，为每棵二叉树设立一个指向空指针。此外，为每棵二叉树设立一个指向根结点的指针根结点的指针root。图图5-8 二叉链表结点的二叉链表结点的结构 lchild data rchild若二叉树为空，则若二叉树为空，则rootroot为空指针为空指针。第5章 树与二叉数 第 页

19、2007-7-29 如果需要经常寻找二叉树中某个结点的双亲，如果需要经常寻找二叉树中某个结点的双亲，可以在结点结构中增加一个指向双亲的指针域可以在结点结构中增加一个指向双亲的指针域parentparent。通常，将每个结点带通常，将每个结点带3 3个指针域个指针域lchildlchild、rchildrchild、parentparent的链表称为二叉树的的链表称为二叉树的三叉链表三叉链表。三叉三叉链链表表结结点点结结构如构如图图5-105-10所示。所示。图图5-10 5-10 三叉链表的结点结构三叉链表的结点结构lchild data parent rchild 例如，图例如，图5-75-

20、7所示二叉树的二叉链表表示可所示二叉树的二叉链表表示可见图见图 5-9，三叉链表表示可见图三叉链表表示可见图5-11二叉链二叉链表是二叉树最常用的存储结构，表是二叉树最常用的存储结构，第5章 树与二叉数 第 页 2007-7-29 root root图图5-95-9二叉树二叉树(图图5-75-7)的二叉链表的二叉链表 图图5-11二叉树二叉树(图图5-75-7)的三叉链表的三叉链表 A C E B D F A B C D E F 下面讨论的二叉树的遍历都是以二叉链表下面讨论的二叉树的遍历都是以二叉链表作为二叉树的存储结构。作为二叉树的存储结构。第5章 树与二叉数 第 页 2007-7-29 二

21、叉链表是二叉树最常用的存储结构，下面二叉链表是二叉树最常用的存储结构，下面讨论的二叉树的遍历都是以二叉链表作为二叉讨论的二叉树的遍历都是以二叉链表作为二叉树的存储结构。二叉链表中结点结构类型定义树的存储结构。二叉链表中结点结构类型定义如下：如下：*typedef char TelemType;/*TelemType为字符型，若需要可重新定义为字符型，若需要可重新定义*/typedef struct BiTNode TelemType data;struct BiTNode*lchild,*rchild;BiTNode,*BiTree;第5章 树与二叉数 第 页 2007-7-29 如何按某条搜

22、索路径访问树中的每一个结点，使得每一个结点均被访问一次，而且仅被访问一次。遍历对线性结构是容易解决的，而二叉树是非线性的，每个结点都可能有两个直接后件结点，这将导，每个结点都可能有两个直接后件结点，这将导致存在多条遍历路线。致存在多条遍历路线。因而需要寻找一种规律，以便使二叉树上的结点能排列在一个线性队列上，从而便于遍历。bca(根结点)(右子树)(左子树)由二叉树的递归定义，二叉树的三个基本组成单元是：根结点、左子树和右子树。5.45.4遍历二叉树遍历二叉树 第5章 树与二叉数 第 页 2007-7-29假如以L、N、R分别表示遍历左子树、遍历根结点和遍历右子树，遍历整个二叉树则有NLR、L

23、NR、LRN、NRL、RNL、RLN六种遍历方案。若规定先左后右，则只有前三种情况，分别规定为：NLR先（根）序遍历，LNR中（根）序遍历，LRN后（根）序遍历。1、先序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。2、中序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则（1）中序遍历左子树；（2）访问根结点；第5章 树与二叉数 第 页 2007-7-29（3）中序遍历右子树。3、后序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。第5章 树与二叉数 第 页

24、 2007-7-29例如图（1）所示的二叉树表达式(a+b*(c-d)-e/f)若先序遍历此二叉树,按访问结点的先后次序将结点排列起来,其先序序列为：-+a*b-cd/ef 按中序遍历,其中序序列为：a+b*c-d-e/f按后序遍历,其后序序列为：abcd-*+ef/-*a/b-dcfe第5章 树与二叉数 第 页 2007-7-29练习如图所示二叉树的中序遍历序列是（）。lAabcdgefBdfebagcCdbaefcgDdefbagc第5章 树与二叉数 第 页 2007-7-29补充 根据遍历序列构造二叉树 由一棵给定的二叉树可以获得三种遍历序列，同样，也可以由这些遍历序列来重新构造二叉树。

25、单用一个遍历序列是无法构造二叉树的，因为无法从遍历序列中区分二叉树的左、右子树。但利用中序遍历序列，并结合先序遍历序列或后序遍历序列就能重新构造二叉树。第5章 树与二叉数 第 页 2007-7-29 根据二叉树的遍历定义，先序遍历序列和中序遍历序列的结点分布特点是：l先序遍历序列：l中序遍历序列：第5章 树与二叉数 第 页 2007-7-29 可以得到二叉树的构造步骤：1）从先序遍历序列中取出第一个结点，该结点一定是二叉树的根。然后在中序遍历序列中找到根结点，根结点前面的结点序列就是左子树的中序遍历序列，根结点后面的结点序列就是右子树的中序遍历序列。2）对根的左子树先序遍历序列和中序遍历序列及

26、右子树的先序遍历序列和中序遍历序列，再执行第一步，直到得出所有叶子结点为止。第5章 树与二叉数 第 页 2007-7-29l利用中序遍历序列，并结合先序遍历序列或后序遍历序列重新构造二叉树。例一例一 先序：ABCDEFGHIJ 中序：CBDEAFHIGJ 例二例二 中序：中序：ABCDJEFHGIABCDJEFHGI 后序：后序：BCJDAHIGFEBCJDAHIGFE 第5章 树与二叉数 第 页 2007-7-29练习1)已知一棵二叉树的先根序列为ABDGCFK，中根序列为DGBAFCK，则结点的后根序列为（）。lAACFKDBG BGDBFKCA CKCFAGDBDABCDFKG 2)已知

27、某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是（）。AacbedBdecabCdeabc Dcedba第5章 树与二叉数 第 页 2007-7-29*5.5 树的存储结构树的存储结构 树在计算机内有多种表示方法，下面介绍树在计算机内有多种表示方法，下面介绍三种常用双亲表示法、孩子表示法、孩子兄三种常用双亲表示法、孩子表示法、孩子兄弟表示法。弟表示法。1.1.双亲表示双亲表示法法 用一组连续空间存储数的结点，同时在每用一组连续空间存储数的结点，同时在每一个结点中附设一个指示器，指示其双亲结一个结点中附设一个指示器，指示其双亲结点的位置。图点的位置。图5-12 5

28、-12 树的双亲表示法示例树的双亲表示法示例第5章 树与二叉数 第 页 2007-7-29图图5-12 树的双亲表示法树的双亲表示法第5章 树与二叉数 第 页 2007-7-29 2.2.孩子表示法孩子表示法 由由于于树树中中每每个个结结点点可可能能有有多多个个孩孩子子，因因此此可可用用多多重重链链表表来来存存储储一一棵棵树树。链链表表中中的的结结点点由由一一个个数数据据域域和和若若干干个个指指针针域域组组成成，每每个个指指针针域域指指向向该该结结点点的的一一个个孩孩子子。由由于于树树中中每每个个结结点点的的度度不不同同，所所以以链链表表中中的结点可以采用定长表示，也可以采用不定长表示。的结点

29、可以采用定长表示，也可以采用不定长表示。假假设设树树的的度度数数为为d d，则则在在定定长长表表示示中中，结结点点的的结结构如图构如图5-135-13所示。所示。datach1ch2chd图图5-13 5-13 孩子表示法的定长结点的结构孩子表示法的定长结点的结构 第5章 树与二叉数 第 页 2007-7-29在不定长表示中，结点的结构如图在不定长表示中，结点的结构如图5-145-14所示。所示。datadatad dchch1chch2chchd 这里，这里，datadata表示自身的数据，表示自身的数据，d d表示结表示结点的度，而点的度，而chch1，chch2，chchd 表示第表示第

30、1,2,d1,2,d个孩子的指针。个孩子的指针。图图5-14 5-14 孩子表示法的不定长结点的结构孩子表示法的不定长结点的结构 图图5-15 5-15 就是图就是图5-12 5-12 中树的多重链表表示。中树的多重链表表示。第5章 树与二叉数 第 页 2007-7-29图图5-15 5-15 树的孩子表示法树的孩子表示法 第5章 树与二叉数 第 页 2007-7-29 如如果果把把孩孩子子链链接接成成一一个个带带表表头头结结点点的的单单链链表表，表表头头结结点点中中存存放放双双亲亲的的信信息息，这这些些表表头头结结点点又又组组成成一一个个线线性性表表，那那么么图图5-125-12中中的的树树

31、可可用用图图5-165-16所所示示结结构构表表示示。该方法实际上是把双亲表示法和孩子表示法结合起来该方法实际上是把双亲表示法和孩子表示法结合起来。图图5-16 5-16 树的带双亲的孩子链表表示法树的带双亲的孩子链表表示法 第5章 树与二叉数 第 页 2007-7-29 3.3.孩子兄弟表示法孩子兄弟表示法 孩孩子子兄兄弟弟表表示示法法又又称称二二叉叉链链表表表表示示法法。在在这这种表示法中，结点的结构如图种表示法中，结点的结构如图5-175-17所示。所示。firstchildfirstchilddatadatanextbrothernextbrother图图5-17 5-17 孩子兄弟表

32、示法的结点结构孩子兄弟表示法的结点结构 这里这里,data,data存放结点的有关信息存放结点的有关信息,firstchildfirstchild指向该结点的第一个孩子指向该结点的第一个孩子,nextbrothernextbrother指向下指向下一个兄弟结点。图一个兄弟结点。图5-185-18就是图就是图5-125-12中树的孩子中树的孩子兄弟表示法。兄弟表示法。第5章 树与二叉数 第 页 2007-7-29图图5-18 5-18 树的孩子兄弟表示法树的孩子兄弟表示法 第5章 树与二叉数 第 页 2007-7-29l树或森林与二叉树之间有一个自然的一一对应关系。任何一个森林或一棵树可唯一地对

33、应到一棵二叉树；反之，任何一棵二叉树也能唯一地对应到一个森林或一棵树。l 树和森林的存储结构与算法都很复杂，如果能够将树和森林转换为二叉树，不但可以采用二叉树的存储结构，而且可以利用二叉树的有关算法来实现树的有关操作。5.6 森林与二叉树的转换森林与二叉树的转换第5章 树与二叉数 第 页 2007-7-29 1.1.树转换为二叉树树转换为二叉树 将树转换成二叉树的方法为：将树转换成二叉树的方法为：（1 1）在兄弟之间加一连线；）在兄弟之间加一连线；（2 2）对每个结点，除了其最左孩子外，去）对每个结点，除了其最左孩子外，去除它与其余孩子之间的联系；除它与其余孩子之间的联系；（3 3）将保留下来

34、的边作为左子树的边，兄）将保留下来的边作为左子树的边，兄弟间的连线作为右子树的边（即各兄弟间的弟间的连线作为右子树的边（即各兄弟间的连线依左边的兄弟结点为轴，顺时针旋转连线依左边的兄弟结点为轴，顺时针旋转4545度角）。度角）。以图以图5-195-19（a a）所示的树为例，可转换为如所示的树为例，可转换为如图图5-195-19（d d）所示的二叉树。所示的二叉树。第5章 树与二叉数 第 页 2007-7-29第5章 树与二叉数 第 页 2007-7-29图图5-19 5-19 树转换为二叉树示例树转换为二叉树示例 第5章 树与二叉数 第 页 2007-7-29【例】下面(a)图所示的树可转换

35、为(c)图所示的二叉树。动画演示第5章 树与二叉数 第 页 2007-7-29 从从树树转转换换为为二二叉叉树树的的过过程程可可知知，任任何何一一棵棵树树对对应应的的二二叉叉树树，其其右右子子树树必必空空，也也就就是是说说，所所有有的的树树都都可可以以转转化化为为二二叉叉树树，但但不不是是所所有有的的二二叉叉树树都都可可以以转转化为树。化为树。2.2.森林转换为二叉树森林转换为二叉树 森林是树的集合。将一个森林转换成二叉树的方森林是树的集合。将一个森林转换成二叉树的方法是：先将森林中的每棵树转换为二叉树，然后把法是：先将森林中的每棵树转换为二叉树，然后把各二叉树的根结点看成兄弟，用直线把它们连

36、到一各二叉树的根结点看成兄弟，用直线把它们连到一起，经整理后可得到相应的二叉树。起，经整理后可得到相应的二叉树。下面图图5-205-20（b b）是对是对图图5-205-20（a a）所示的森林进所示的森林进行转换后得到的结果，行转换后得到的结果，图图5-205-20（c c）是经整理后得是经整理后得到的二叉树。到的二叉树。第5章 树与二叉数 第 页 2007-7-29图图5-20(a)森林森林图图5-20(b)中间中间形式形式第5章 树与二叉数 第 页 2007-7-29对对森森林林转转换换成成二二叉叉树树的方法作出以下定义：的方法作出以下定义：设设F=F=T T1,T,T2，T Tn ，是

37、是一一个个由由树树T T1,T,T2，T Tn组组成成的的森森林林，则则森森林林F对对应应的的二二叉叉树树B(T T1,T,T2，T Tn)（也记作也记作B(F)）如下：如下：（1 1）若若F F为为空空（n=0n=0），则则B(F)为空树；为空树；(c)转换结果转换结果 图图5-20森林到二叉树的森林到二叉树的转换转换第5章 树与二叉数 第 页 2007-7-29 （2 2）若若F F非非空空（n n0 0），则则B(F)的的根根就就是是T T1 的的根根W W1，B(F)的的左左子子树树是是B(T11，T12，T1m)，其其中中T11，T12，T1m 是是W W1 的的子子树树；B(F)的

38、右子树是的右子树是B(T T2,T,T3，T Tn)。这是一个递归的定义。由此可知，对树和森林的运这是一个递归的定义。由此可知，对树和森林的运算都可以转换为对相应的二叉树的运算来实现算都可以转换为对相应的二叉树的运算来实现。第5章 树与二叉数 第 页 2007-7-29l【例】下图中，左边包含三棵树的森林可转换为右边的二叉树。动画演示第5章 树与二叉数 第 页 2007-7-295.7 5.7 赫夫曼树及其应用赫夫曼树及其应用 赫夫曼（赫夫曼（HuffmanHuffman）树，又称最优二叉树，是一树，又称最优二叉树，是一类带权路径长度最短的二叉树。类带权路径长度最短的二叉树。常用几个基本术语常

39、用几个基本术语 如下：如下：路路径径与与路路径径长长度度：从从树树中中一一个个结结点点到到另另一一个个结结点点之之间间的的分分支支构构成成这这两两个个结结点点之之间间的的路路径径，路路径径上的分支数目称为路径长度。上的分支数目称为路径长度。树树的的路路径径长长度度：从从树树根根到到树树的的各各个个结结点点的的路路径径长度之和称为树的路径长度，记作长度之和称为树的路径长度，记作 PL PL 。第5章 树与二叉数 第 页 2007-7-29 结点的权与带权路径长度：结点的权与带权路径长度：在实际应用中，常常在实际应用中，常常给树中结点赋予一个具有某种实际意义的实数，该给树中结点赋予一个具有某种实际

40、意义的实数，该实数称为这个结点的权。结点的带权路径长度是该实数称为这个结点的权。结点的带权路径长度是该结点到树根之间的路径长度与结点的权的乘积。结点到树根之间的路径长度与结点的权的乘积。树的带权路径长度：树的带权路径长度：树中所有树中所有叶子结点叶子结点的带权路的带权路径长度之和称为树的带权路径长度，记作径长度之和称为树的带权路径长度，记作 WPLWPL第5章 树与二叉数 第 页 2007-7-29W Wi i为叶子的权为叶子的权；L Li i为根为根结点到叶子之间的路结点到叶子之间的路径长度径长度 图图5-21 5-21 具有不同带权路径的二叉树具有不同带权路径的二叉树 第5章 树与二叉数

41、第 页 2007-7-29 例例如如，上上页页图图5-21中中的的(a)、(b)、(c)3棵棵二二叉叉树树，都都有有5 5个个叶叶子子结结点点，分分别别带带权权 2 2，3 3，4 4，6 6，7 7，它们的路径长度及带权路径长度分别为：它们的路径长度及带权路径长度分别为：PL(a)=1+1+2+2+2+2+3+3=16PL(a)=1+1+2+2+2+2+3+3=16PL(b)=1+1+2+2+3+3+4+4=20PL(b)=1+1+2+2+3+3+4+4=20PL(c)=1+1+2+2+2+2+3+3=16PL(c)=1+1+2+2+2+2+3+3=16WPL(a)=2*(2+3+4)+3*

42、(6+7)=57WPL(a)=2*(2+3+4)+3*(6+7)=57WPL(b)=1*7+2*6+3*4+4*(2+3)=51 WPL(b)=1*7+2*6+3*4+4*(2+3)=51 WPL(c)=2*(4+6+7)+3*(2+3)=49WPL(c)=2*(4+6+7)+3*(2+3)=49第5章 树与二叉数 第 页 2007-7-29 1.1.赫夫曼树赫夫曼树 在在权权值值为为W W1，W W2，W Wn的的 n n个个叶叶子子所所构构成成的的所所有有二二叉叉树树中中，带带权权路路径径长长度度最最小小的的二二叉叉树树称称为为赫赫夫夫曼曼树树。图图5-20(c)5-20(c)所示的二叉树

43、就是一棵赫夫曼树。所示的二叉树就是一棵赫夫曼树。如如何何构构造造权权集集合合WW1，W W2，W Wn 的的赫赫夫夫曼曼树树呢呢？赫夫曼提出了如下算法：？赫夫曼提出了如下算法：1 1）给给定定的的 n n 个个权权值值 为为 W W1，W W2，W Wn 构构成成有有n n棵棵二二叉叉树树的的森森林林F=TF=T1，T T2，T Tn，其其中中每每棵棵二二叉叉树树T Ti 只只有有一一个个权权值值为为W Wi的的根根结结点点，其其左左、右右子子树树均为空。均为空。2 2）森林森林F F中至少还有两棵二叉树时，重复下列步骤中至少还有两棵二叉树时，重复下列步骤第5章 树与二叉数 第 页 2007-

44、7-29 从森林从森林F F中选出两棵根结点的权值最小的二叉树中选出两棵根结点的权值最小的二叉树T T1 1和和T T2 2，如果这样的二叉树不止两棵，可以从中任选如果这样的二叉树不止两棵，可以从中任选两棵，构造一棵新的二叉树两棵，构造一棵新的二叉树T T，使，使T T1和和T T2分别为分别为T T的左的左子树和右子树，子树和右子树，T T的根的权值为的根的权值为T T1 与与T T2 的根的权值之的根的权值之和，然后从森林中删去和，然后从森林中删去T T1 和和T T2。将新二叉树将新二叉树T T叉入森林叉入森林F F中。中。假设有假设有5 5棵，均仅有一个结点的二叉树，其权值分棵，均仅有

45、一个结点的二叉树，其权值分别为别为7 7，8 8，2 2，3 3，4 4构成森林构成森林F F，并依权值从小到大排并依权值从小到大排序的结果，如图序的结果，如图5-22(a)5-22(a)所示；所示；图图5-22(a)5-22(a)第5章 树与二叉数 第 页 2007-7-29 用根为用根为2 2和和3 3的二叉树生成根为的二叉树生成根为5 5的二叉树，并重新的二叉树，并重新排序的结果，如图排序的结果，如图5-22(b)5-22(b)所示；所示；图图5-22(b)5-22(b)用根为用根为4 4和和5 5的二叉的二叉树生成根为树生成根为9 9的二叉树，的二叉树，并重新排序的结果，并重新排序的结

46、果，如图如图5-22(c)5-22(c)所示；所示；图图5-22(c)5-22(c)第5章 树与二叉数 第 页 2007-7-29 用根为用根为7 7和和8 8的二叉树的二叉树生成根为生成根为1515的二叉树，的二叉树，并重新排序的结果，如并重新排序的结果，如图图5-22(d)5-22(d)所示；所示；图图5-22(d)5-22(d)图图5-22(e)5-22(e)用根为用根为9 9和和1515的二叉树生的二叉树生成根为成根为2424的二叉树，并重的二叉树，并重新排序的结果就是一棵哈新排序的结果就是一棵哈夫曼树，如图夫曼树，如图5-22(e)5-22(e)所所示；示；第5章 树与二叉数 第 页

47、 2007-7-29l例如，设给定的权集合为7，8，10，6，3，构成森林F并排序后，如图3（a）所示；用根为3和6的二叉树生成根为9的二叉树，并重新排序后；l如图3（b）所示；重复进行下去，直到F中剩下一棵二叉树为止，便得到哈夫曼树；l如图3（e）所示，其带权路径长度为：WPL=33+63+72+82+102=77第5章 树与二叉数 第 页 2007-7-29第5章 树与二叉数 第 页 2007-7-29l注意：在构造Huffman树的过程中，为了规范起见，我们规定集合F=T1，T2，Tn中权值小的二叉树作为新构造的二叉树的左子树，权值大的二叉树作为新构造的二叉树的右子树；权值相等时，选取深

48、度小的二叉树作为新构造的二叉树的左子树，深度大的二叉树作为新构造的二叉树的右子树。第5章 树与二叉数 第 页 2007-7-29练习l设给定权集w=2,3,4,7,8,9,试构造关于W的一棵Huffman树。l由分别带权为4，8，7，3，5的共五个叶子构成一棵哈夫曼树 第5章 树与二叉数 第 页 2007-7-29 用用赫赫夫夫曼曼算算法法构构造造出出来来的的二二叉叉树树一一定定是是最最优优二二叉叉树树。从从构构造造过过程程可可以以看看出出，权权值值最最大大的的叶叶子子离离根根最最近近，权权值值最最小小的的叶叶子子离离根根最最远远，所所得得二二叉叉树树必然具有最小的带权路径长度。必然具有最小的

49、带权路径长度。2.赫夫曼编码赫夫曼编码 赫夫曼树在通信、编码和数据压缩等技术领域赫夫曼树在通信、编码和数据压缩等技术领域有着广泛的应用。下面讨论在数据编码中的一个有着广泛的应用。下面讨论在数据编码中的一个应用，即数据的最小冗余编码问题。应用，即数据的最小冗余编码问题。在通信业务中，可以用在通信业务中，可以用0 0和和1 1所组成的编码来表所组成的编码来表示一个字符，一个字符序列可以用一个编码序列示一个字符，一个字符序列可以用一个编码序列来表示。来表示。第5章 树与二叉数 第 页 2007-7-29 假定文本中出现的字符集为假定文本中出现的字符集为26个字母，由个字母，由242625知，知，最简

50、单的编码方案是每个字母都最简单的编码方案是每个字母都用固定长度为用固定长度为5的二进制编码来表示。这种编的二进制编码来表示。这种编码不考虑字符在文本中的出现频度码不考虑字符在文本中的出现频度(或次数或次数)在实际应用中，字符集中各个字符的出现频在实际应用中，字符集中各个字符的出现频度或使用次数是不相同的。有些字符经常出现，度或使用次数是不相同的。有些字符经常出现，有些字符却很少见到。我们设计编码的目标是：有些字符却很少见到。我们设计编码的目标是：希望用短的编码来表示那些出现频度大的字符，希望用短的编码来表示那些出现频度大的字符，用长的编码来表示出现频度小的字符，从而使用长的编码来表示出现频度小