数据结构(CC++语言版)第五章-树和二叉树课件.ppt

《数据结构(CC++语言版)第五章-树和二叉树课件.ppt》由会员分享，可在线阅读，更多相关《数据结构(CC++语言版)第五章-树和二叉树课件.ppt（114页珍藏版）》请在三一办公上搜索。

1、数据结构(CC+语言版)第五章 树和二叉树,2,1.熟练掌握二叉树的结构特性，了解相应的证明方法。2.熟悉二叉树的各种存储结构的特点及适用范围。3.遍历二叉树是二叉树各种操作的基础，掌握各种遍历策略 的递归算法，灵活运用遍历算法实现二叉树的其它操作。4.熟悉树的各种存储结构及其特点，掌握树和森林与二叉树的转换方法。5.学会编写实现树的各种操作的算法。6.了解最优树的特性，掌握建立最优树和哈夫曼编码的方法。,要求：,1、若一棵树中度为1的结点有n1个，度为2的结点有n2个，度为m的结点有nm个，它有多少个叶结点？2、找出所有的二叉树，其结点在下列两种次序下恰好都以同样的顺序出现：（1）先根和中根

2、（2）先根和后根（3）中根和后根3、设计一个算法，根据一个二叉树结点的先根序列和中根序列构造出该二叉树。假设二叉树是链接表示的，并且任意两个结点的info字段值都不同。4、设计一个算法，将一个链接表示的二叉树中每个结点的左、右子女位置交换。5、设计一个算法，按层次顺序输出二叉树中的所有结点，要求同一层上的结点从左到右输出。6、设F是一个森林，B是与F对应的二叉树。试问，F中非叶结点的个数和B中右子树为空的结点的个数之间有什么数量关系？,4,【作业】,树的存储方法主要有哪些？举例说明具体存储结构。,【课堂作业】,已知一棵二叉树的前序遍历序列和中序遍历序列分别为ABCDEFGHI 和BCAEDGH

3、FI，如何构造该二叉树?,5,树的定义,树：n（n0）个结点的有限集合。当n0时，称为空树；任意一棵非空树满足以下条件：有且仅有一个特定的称为根的结点；当n1时，除根结点之外的其余结点被分成m（m0）个互不相交的有限集合T1,T2,Tm，其中每个集合又是一棵树，并称为这个根结点的子树。,5.1 树的逻辑结构,树的定义是采用递归方法,6,树的基本术语,结点的度：结点所拥有的子树的个数。树的度：树中各结点度的最大值。叶子结点：度为0的结点，也称为终端结点。分支结点：度不为0的结点，也称为非终端结点。孩子、双亲：树中某结点子树的根结点称为这个结点的孩子结点，这个结点称为它孩子结点的双亲结点；兄弟：具

4、有同一个双亲的孩子结点互称为兄弟。,5.1 树的逻辑结构,7,路径：如果树的结点序列n1,n2,nk有如下关系：结点ni是ni+1的双亲（1=ik），则把n1,n2,nk称为一条由n1至nk的路径；路径上经过的边的个数称为路径长度。,5.1 树的逻辑结构,树的基本术语,8,祖先、子孙：在树中，如果有一条路径从结点x到结点y，那么x就称为y的祖先，而y称为x的子孙。,5.1 树的逻辑结构,树的基本术语,9,结点所在层数：根结点的层数为1；对其余任何结点，若某结点在第k层，则其孩子结点在第k+1层。树的深度：树中所有结点的最大层数，也称高度。,5.1 树的逻辑结构,树的基本术语,10,层序编号：将

5、树中结点按照从上层到下层、同层从左到右的次序依次给他们编以从1开始的连续自然数。,5.1 树的逻辑结构,树的基本术语,11,有序树、无序树：如果一棵树中结点的各子树从左到右是有次序的，称这棵树为有序树；反之，称为无序树。,数据结构中讨论的一般都是有序树,5.1 树的逻辑结构,树的基本术语,12,森林：m(m0)棵互不相交的树的集合。,5.1 树的逻辑结构,树的基本术语,13,同构：对两棵树，若通过对结点适当地重命名，就可以使这两棵树完全相等（结点对应相等，结点对应关系也相等），则称这两棵树同构。,5.1 树的逻辑结构,树的基本术语,14,树结构和线性结构的比较,线性结构,树结构,无前驱,无双亲

6、,无后继,无孩子,一个前驱,一个后继,一个双亲,多个孩子,一对一 一对多,5.1 树的逻辑结构,15,树的抽象数据类型定义,5.1 树的逻辑结构,数据对象 D：,D是具有相同特性的数据元素的集合。,若D为空集，则称为空树；否则:(1)在D中存在唯一的称为根的数据元素root,(2)当n1时，其余结点可分为m(m0)个互不相交的有限集T1,T2,Tm,其中每一棵子集本身又是一棵符合本定义的树，称为根root的子树。,数据关系 R：,16,A(B(E,F(K,L),C(G),D(H,I,J(M),T1,T3,T2,树根,(b),(a),上面是树的广义表表示形式,例如：,17,树的文氏图表示法和凹入

7、表示法,18,树的遍历操作,树的遍历：从根结点出发，按照某种次序访问树中所有结点，使得每个结点被访问一次且仅被访问一次。,如何理解访问?,抽象操作，可以是对结点进行的各种处理，这里简化为输出结点的数据。,如何理解次序?,树通常有前序（根）遍历、后序（根）遍历和层序（次）遍历三种方式。,5.1 树的逻辑结构,树结构（非线性结构）线性结构。,遍历的实质?,19,前序遍历,树的前序遍历操作定义为：若树为空，则空操作返回；否则 访问根结点；按照从左到右的顺序前序遍历根结点的每一棵子树。,5.1 树的逻辑结构,前序遍历序列：A B D E H I F C G,20,后序遍历,树的后序遍历操作定义为：若树

8、为空，则空操作返回；否则 按照从左到右的顺序后序遍历根结点的每一棵子树；访问根结点。,5.1 树的逻辑结构,后序遍历序列：D H I E F B G C A,21,层序遍历,树的层序遍历操作定义为：从树的第一层（即根结点）开始，自上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。,5.1 树的逻辑结构,层序遍历序列：A B C D E F G H I,22,5.2 树的存储结构,实现树的存储结构，关键是什么?,什么是存储结构?,树中结点之间的逻辑关系是什么?,思考问题的出发点：如何表示结点的双亲和孩子,如何表示树中结点之间的逻辑关系。,数据元素以及数据元素之间的逻辑关系在存储器中的表

9、示。,23,下标 data parent,5.2 树的存储结构,1）双亲表示法以一组连续空间存储树的结点，在每个结点中设一个指示器指示双亲结点的位置。,24,012345678,下标 data firstchild,A B C D E F G H I,5.2 树的存储结构,2）孩子表示法：每个结点的孩子以单链表的形式存储，n个结点有n个孩子链表，n个头指针又组成一个线性表，并以顺序存储结构存储。,25,3）双亲孩子表示法,5.2 树的存储结构,26,5.2 树的存储结构,4）孩子兄弟表示法：以二叉链表作为树的存储结构，链表中的结点的两个指针分别指向该结点的第一个孩子结点和下一个兄弟结点。,27

10、,二叉树的定义,二叉树是n（n0）个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。,5.3 二叉树的逻辑结构,问题转化：将树转换为二叉树，从而利用二叉树解决树的有关问题。,研究二叉树的意义？,28,二叉树的特点：,每个结点最多有两棵子树；二叉树是有序的，其次序不能任意颠倒。,5.3 二叉树的逻辑结构,注意：二叉树和树是两种树结构。,29,二叉树的基本形态,5.3 二叉树的逻辑结构,30,5.3 二叉树的逻辑结构,具有3个结点的树和具有3个结点的二叉树的形态,二叉树和树是两种树结构。,31,特殊的二叉树,斜树1.所

11、有结点都只有左子树的二叉树称为左斜树；2.所有结点都只有右子树的二叉树称为右斜树；3.左斜树和右斜树统称为斜树。,1.在斜树中，每一层只有一个结点；2.斜树的结点个数与其深度相同。,5.3 二叉树的逻辑结构,斜树的特点：,32,满二叉树在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上。,满二叉树的特点：,叶子只能出现在最下一层；只有度为0和度为2的结点。,5.3 二叉树的逻辑结构,特殊的二叉树,33,满二叉树,5.3 二叉树的逻辑结构,不是满二叉树，虽然所有分支结点都有左右子树，但叶子不在同一层上。,满二叉树在同样深度的二叉树中结点个数最多满二叉树在同样深度的二叉

12、树中叶子结点个数最多,特殊的二叉树,34,完全二叉树对一棵具有n个结点的二叉树按层序编号，如果编号为i（1in）的结点与同样深度的满二叉树中编号为i的结点在二叉树中的位置完全相同。,5.3 二叉树的逻辑结构,特殊的二叉树,35,在满二叉树中，从最后一个结点开始，连续去掉任意个结点，即是一棵完全二叉树。,5.3 二叉树的逻辑结构,A,1,5,2,3,4,6,7,9,10,B,C,D,E,F,G,H,I,J,不是完全二叉树，结点10与满二叉树中的结点10不是同一个结点,特殊的二叉树,36,1.叶子结点只能出现在最下两层，且最下层的叶子结点都集中在二叉树的左部；2.完全二叉树中如果有度为1的结点，只

13、可能有一个，且该结点只有左孩子。3.深度为k的完全二叉树在k-1层上一定是满二叉树。,完全二叉树的特点,5.3 二叉树的逻辑结构,特殊的二叉树,37,二叉树的基本性质,性质5-1 二叉树的第i层上最多有2i-1个结点（i1）。,推广：深度为h的k叉树中，第i层上最多具有 个结点。,5.3 二叉树的逻辑结构,ki1,38,性质5-2 一棵深度为k的二叉树中，最多有2k-1个结点，最少有k个结点。,5.3 二叉树的逻辑结构,二叉树的基本性质,39,性质5-3 在一棵二叉树中，如果叶子结点数为n0，度为2的结点数为n2，则有:n0n21。,证明:抓住结点总数=结点总度数+1n0+n1+n2=n1+2

14、*n2+1 n0=n2+1,5.3 二叉树的逻辑结构,二叉树的基本性质,推广：已知一棵树度为m的树中有n1个度为1的结点，n2个度为2的结点，nm个度为m的结点，问该树中有多少片叶子？,证明：根据结点总数=结点总度数+1 n0+n1+n2+nm=n1+2*n2+m*nm+1=n0=1+n2+(m-1)nm,40,5.3 二叉树的逻辑结构,在有n个结点的满二叉树中，有多少个叶子结点？,因为在满二叉树中没有度为1的结点，只有度为0的叶子结点和度为2的分支结点，所以，,n n0+n2n0n2+1,即叶子结点n0（n+1）/2,二叉树的基本性质,41,5.3 二叉树的逻辑结构,任一个有n个结点的二叉树

15、，有m个叶子结点，则非叶子结点数（度为2）有 个？,二叉树的基本性质,42,性质6-4 具有n个结点的完全二叉树的深度为 log2n+1。,5.3 二叉树的逻辑结构,证明：假设具有n个结点的完全二叉树的深度为k，根据完全二叉树的定义和性质2，有下式成立 2k-1 n 2k,最少结点数,最多结点数,完全二叉树的基本性质,43,5.3 二叉树的逻辑结构,证明：假设具有n个结点的完全二叉树的深度为k，根据完全二叉树的定义和性质2，有下式成立 2k-1 n 2k,完全二叉树的基本性质,44,性质6-5 对一棵具有n个结点的完全二叉树中从1开始按层序编号，则对于任意的序号为i（1in）的结点（简称为结点

16、i），有：（1）如果i1，则结点i的双亲结点的序号为 i/2；如果i1，则结点i是根结点，无双亲结点。(2)如果2in，则结点i的左孩子的序号为2i；如果2in，则结点i无左孩子。(3)如果2i1n，则结点i的右孩子的序号为2i1；如果2i1n，则结点 i无右孩子。,5.3 二叉树的逻辑结构,完全二叉树的基本性质,45,对一棵具有n个结点的完全二叉树中从1开始按层序编号，则 结点i的双亲结点为 i/2；结点i的左孩子为2i；结点i的右孩子为2i1。,5.3 二叉树的逻辑结构,性质6表明，在完全二叉树中，结点的层序编号反映了结点之间的逻辑关系。,完全二叉树的基本性质,46,二叉树的抽象数据类型定

17、义,查书,5.3 二叉树的逻辑结构,二叉树的主要基本操作：,查 找 类 插 入 类 删 除 类,47,二叉树的遍历操作,二叉树的遍历是指从根结点出发，按照某种次序访问二叉树中的所有结点，使得每个结点被访问一次且仅被访问一次。,二叉树遍历操作的结果？,5.3 二叉树的逻辑结构,48,如果限定先左后右，则二叉树遍历方式有三种：前序：DLR中序：LDR后序：LRD,层序遍历：按二叉树的层序编号的次序访问各结点。,5.3 二叉树的逻辑结构,考虑二叉树的组成：,49,前序遍历若二叉树为空，则空操作返回；否则：访问根结点；前序遍历根结点的左子树；前序遍历根结点的右子树。,5.3 二叉树的逻辑结构,前序遍历

18、序列：A B D G C E F,二叉树的遍历操作,50,中序遍历若二叉树为空，则空操作返回；否则：中序遍历根结点的左子树；访问根结点；中序遍历根结点的右子树。,5.3 二叉树的逻辑结构,中序遍历序列：D G B A E C F,二叉树的遍历操作,51,后序遍历若二叉树为空，则空操作返回；否则：后序遍历根结点的左子树；后序遍历根结点的右子树。访问根结点；,5.3 二叉树的逻辑结构,后序遍历序列：G D B E F C A,二叉树的遍历操作,52,层序遍历二叉树的层次遍历是指从二叉树的第一层（即根结点）开始，从上至下逐层遍历，在同一层中，则按从左到右的顺序对结点逐个访问。,5.3 二叉树的逻辑结

19、构,层序遍历序列：A B C D E F G,二叉树的遍历操作,53,5.3 二叉树的逻辑结构,若已知一棵二叉树的前序（或中序，或后序，或层序）序列，能否唯一确定这棵二叉树呢？,例：已知前序序列为ABC，则可能的二叉树有5种。,二叉树的遍历操作,54,5.3 二叉树的逻辑结构,例：已知前序遍历序列为ABC，后序遍历序列为CBA，则下列二叉树都满足条件。,若已知一棵二叉树的前序序列和后序序列，能否唯一确定这棵二叉树呢？,二叉树的遍历操作,55,若已知一棵二叉树的前序序列和中序序列，能否唯一确定这棵二叉树呢？怎样确定？,例如：已知一棵二叉树的前序遍历序列和中序遍历序列分别为ABCDEFGHI 和B

20、CAEDGHFI，如何构造该二叉树呢?,5.3 二叉树的逻辑结构,二叉树的遍历操作,56,1.根据前序序列的第一个元素建立根结点；2.在中序序列中找到该元素，确定根结点的左右子树的中序序列；3.在前序序列中确定左右子树的前序序列；4.由左子树的前序序列和中序序列建立左子树；5.由右子树的前序序列和中序序列建立右子树。,5.3 二叉树的逻辑结构,已知一棵二叉树的前序序列和中序序列，构造该二叉树的过程如下：,二叉树的遍历操作,57,顺序存储结构,二叉树的顺序存储结构就是用一维数组存储二叉树中的结点，并且结点的存储位置（下标）应能体现结点之间的逻辑关系父子关系。,如何利用数组下标来反映结点之间的逻辑

21、关系?,完全二叉树和满二叉树中结点的序号可以唯一地反映出结点之间的逻辑关系。,5.4 二叉树的存储结构及实现,58,完全二叉树的顺序存储,5.4 二叉树的存储结构及实现,以编号为下标,59,二叉树的顺序存储,5.4 二叉树的存储结构及实现,以编号为下标,按照完全二叉树编号,60,一棵斜树的顺序存储会怎样呢？,深度为k的右斜树，k个结点需分配2k1个存储单元。,一棵二叉树改造后成完全二叉树形态，需增加很多空结点，造成存储空间的浪费。,5.4 二叉树的存储结构及实现,二叉树的顺序存储结构一般仅存储完全二叉树,61,二叉链表,基本思想：令二叉树的每个结点对应一个链表结点，链表结点除了存放与二叉树结点

22、有关的数据信息外，还要设置指示左右孩子的指针。,结点结构：,其中，data：数据域，存放该结点的数据信息；lchild：左指针域，存放指向左孩子的指针；rchild：右指针域，存放指向右孩子的指针。,5.4 二叉树的存储结构及实现,62,template struct BiNode T data;BiNode*lchild,*rchild;,5.4 二叉树的存储结构及实现,二叉链表,63,二叉链表,5.4 二叉树的存储结构及实现,具有n个结点的二叉链表中，有多少个空指针？,64,二叉链表,5.4 二叉树的存储结构及实现,具有n个结点的二叉链表中，有n+1个空指针。,65,前序遍历递归算法,te

23、mplate void BiTree:PreOrder(BiNode*root)if(root=NULL)return;else coutdata;PreOrder(root-lchild);PreOrder(root-rchild);,5.4 二叉树的存储结构及实现,66,5.4 二叉树的存储结构及实现,前序遍历算法的执行轨迹,67,二叉树前序遍历的非递归算法的关键：在前序遍历过某结点的整个左子树后，如何找到该结点的右子树的根指针。解决办法：在访问完该结点后，将该结点的指针保存在栈中，以便以后能通过它找到该结点的右子树。,在前序遍历中，设要遍历二叉树的根指针为root，则有两种可能：若roo

24、t!=NULL，则表明？如何处理？若root=NULL，则表明？如何处理？,5.4 二叉树的存储结构及实现,前序遍历非递归算法,68,访问结点序列:,A,栈S内容:,B,D,A,B,前序遍历的非递归实现,5.4 二叉树的存储结构及实现,A,D,B,C,69,访问结点序列:,A,栈S内容:,B,D,A,前序遍历的非递归实现,5.4 二叉树的存储结构及实现,A,D,B,C,D,70,访问结点序列:,A,栈S内容:,B,D,C,前序遍历的非递归实现,5.4 二叉树的存储结构及实现,A,D,B,C,C,71,1.栈s初始化；2.循环直到root为空且栈s为空 2.1 当root不空时循环2.1.1 输

25、出root-data;2.1.2 将指针root的值保存到栈中；2.1.3 继续遍历root的左子树2.2 如果栈s不空，则2.2.1 将栈顶元素弹出至root；2.2.2 准备遍历root的右子树；,前序遍历非递归算法（伪代码）,5.4 二叉树的存储结构及实现,72,前序遍历非递归算法,5.4 二叉树的存储结构及实现,template void BiTree:PreOrder(BiNode*root)top=-1;/采用顺序栈，并假定不会发生上溢 while(root!=NULL|top!=-1)while(root!=NULL)coutdata;s+top=root;root=root-l

26、child;if(top!=-1)root=stop-;root=root-rchild;,73,中序遍历递归算法,template void BiTree:InOrder(BiNode*root)if(root=NULL)return;else InOrder(root-lchild);coutdata;InOrder(root-rchild);,5.4 二叉树的存储结构及实现,74,后序遍历递归算法,template void BiTree:PostOrder(BiNode*root)if(root=NULL)return;else PostOrder(root-lchild);PostO

27、rder(root-rchild);coutdata;,5.4 二叉树的存储结构及实现,75,层序遍历,5.4 二叉树的存储结构及实现,遍历序列：,A,A,B,C,B,D,C,E,F,G,D,E,F,G,76,层序遍历,队列Q初始化；2.如果二叉树非空，将根指针入队；3.循环直到队列Q为空 3.1 q=队列Q的队头元素出队；3.2 访问结点q的数据域；3.3 若结点q存在左孩子，则将左孩子指针入队；3.4 若结点q存在右孩子，则将右孩子指针入队；,5.4 二叉树的存储结构及实现,77,二叉树的建立,为了建立一棵二叉树，将二叉树中每个结点的空指针引出一个虚结点，其值为一特定值如“#”，以标识其为

28、空，把这样处理后的二叉树称为原二叉树的扩展二叉树。,为什么如此处理?,5.4 二叉树的存储结构及实现,如何由一种遍历序列生成该二叉树？,遍历是二叉树各种操作的基础，可以在遍历的过程中进行各种操作，例如建立一棵二叉树。,78,扩展二叉树的前序遍历序列:A B#D#C#,5.4 二叉树的存储结构及实现,二叉树的建立,79,前序遍历若二叉树为空，则空操作返回；否则：访问根结点；前序遍历根结点的左子树；前序遍历根结点的右子树。,前序遍历序列：A B D C,二叉树的遍历操作,5.4 二叉树的存储结构及实现,80,前序遍历若二叉树为空，则空操作返回；否则：访问根结点；前序遍历根结点的左子树；前序遍历根结

29、点的右子树。,二叉树的遍历操作,5.4 二叉树的存储结构及实现,前序创建若输入为#(空)，则root=NULL；否则：创建根结点；前序创建根结点的左子树；前序创建根结点的右子树。,81,template BiTree:BiTree(BiNode*root)creat(root)；void BiTree:Creat(BiNode*root)cinch;if(ch=#)root=NULL;else root=new BiNode;root-data=ch;creat(root-lchild);creat(root-rchild);,建立二叉递归算法,5.4 二叉树的存储结构及实现,82,线索链表,

30、5.4 二叉树的存储结构及实现,为什么要线索？,1）二叉树的存储结构中没有反映出某结点的直接前驱结点和直接后继结点是什么。2）二叉树的二叉链表存储结构中的那些空指针域 可利用。,83,线索链表,线索：将二叉链表中的空指针域指向前驱结点和后继结点的指针被称为线索；线索化：使二叉链表中结点的空链域存放其前驱或后继信息的过程称为线索化；线索二叉树：加上线索的二叉树称为线索二叉树。,5.4 二叉树的存储结构及实现,84,5.4 二叉树的存储结构及实现,结点结构,线索链表,85,enum flag Child,Thread;template struct ThrNode T data;ThrNode*l

31、child,*rchild;flag ltag,rtag;,5.4 二叉树的存储结构及实现,线索链表,结点结构,86,二叉树的遍历方式有4种，故有4种意义下的前驱和后继，相应的有4种线索二叉树：前序线索二叉树 中序线索二叉树 后序线索二叉树 层序线索二叉树,5.4 二叉树的存储结构及实现,线索二叉树,87,前序线索二叉树：前序序列为：ABCD,5.4 二叉树的存储结构及实现,线索二叉树画法,88,中序线索二叉树：中序序列为：BADC,5.4 二叉树的存储结构及实现,线索二叉树,89,后序线索二叉树：后序序列为：BDCA,5.4 二叉树的存储结构及实现,线索二叉树,90,分析：建立线索链表，实质

32、上就是将二叉链表中的空指针改为指向前驱或后继的线索，而前驱或后继的信息只有在遍历该二叉树时才能得到。,5.4 二叉树的存储结构及实现,中序线索链表的建立构造函数,91,在遍历过程中，访问当前结点root的操作为：如果root的左、右指针域为空，则将相应标志置1；若root的左指针域为空，则令其指向它的前驱，这需要设指针pre始终指向刚刚访问过的结点，显然pre的初值为NULL；若pre的右指针域为空，则令其指向它的后继，即当前访问的结点root;令pre指向刚刚访问过的结点root；,5.4 二叉树的存储结构及实现,中序线索链表的建立,92,1.建立二叉链表，将每个结点的左右标志置为0；2.遍

33、历二叉链表，建立线索；2.1 如果二叉链表root为空，则空操作返回；2.2 对root的左子树建立线索；2.3 对根结点root建立线索；2.3.1 若root没有左孩子，则为root加上前驱线索;2.3.2 若root没有右孩子，则将root右标志置为1；2.3.3 若结点pre右标志为1，则为pre加上后继线索；2.3.4 令pre指向刚刚访问的结点root；2.4 对root的右子树建立线索。,5.4 二叉树的存储结构及实现,中序线索链表的建立构造函数,93,5.5 树、森林与二叉树的转换,是哪些树结构的存储结构?,树和二叉树之间具有对应关系,94,5.5 树、森林与二叉树的转换,树和

34、二叉树之间的对应关系 树：兄弟关系二叉树：双亲和右孩子 树：双亲和长子二叉树：双亲和左孩子,95,5.5 树、森林与二叉树的转换,1.兄弟加线.,树和二叉树之间的对应关系,96,5.5 树、森林与二叉树的转换,2.保留双亲与第一孩子连线,删去与其他孩子的连线.,树和二叉树之间的对应关系,1.兄弟加线.,97,3.顺时针转动,使之层次分明.,5.5 树、森林与二叉树的转换,树和二叉树之间的对应关系,2.保留双亲与第一孩子连线,删去与其他孩子的连线.,1.兄弟加线.,A,B,C,D,E,F,G,98,3.顺时针转动,使之层次分明.,5.5 树、森林与二叉树的转换,树和二叉树之间的对应关系,2.保留

35、双亲与第一孩子连线,删去与其他孩子的连线.,1.兄弟加线.,99,树转换为二叉树,加线树中所有相邻兄弟之间加一条连线。去线对树中的每个结点，只保留它与第一个孩子结点之间的连线，删去它与其它孩子结点之间的连线。层次调整以根结点为轴心，将树顺时针转动一定的角度，使之层次分明。,5.5 树、森林与二叉树的转换,100,森林转换为二叉树,将森林中的每棵树转换成二叉树；从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子，当所有二叉树连起来后，此时所得到的二叉树就是由森林转换得到的二叉树。,5.5 树、森林与二叉树的转换,101,二叉树转换为树或森林,加线若某结点x是其双亲y的左

36、孩子，则把结点x的右孩子、右孩子的右孩子、，都与结点y用线连起来；去线删去原二叉树中所有的双亲结点与右孩子结点的连线；层次调整整理由、两步所得到的树或森林，使之层次分明。,5.5 树、森林与二叉树的转换,102,5.5 树、森林与二叉树的转换,103,森林的遍历,森林有两种遍历方法：前序（根）遍历：前序遍历森林即为前序遍历森林中的每一棵树。后序（根）遍历：后序遍历森林即为后序遍历森林中的每一棵树。,5.5 树、森林与二叉树的转换,104,相关概念,叶子结点的权值：对叶子结点赋予的一个有意义的数值量。,二叉树的带权路径长度：设二叉树具有n个带权值的叶子结点，从根结点到各个叶子结点的路径长度与相应

37、叶子结点权值的乘积之和。记为：,WPL=,5.6 哈夫曼树及哈夫曼编码,105,哈夫曼树：给定一组具有确定权值的叶子结点，带权路径长度最小的二叉树。,例：给定4个叶子结点，其权值分别为2，3，4，7，可以构造出形状不同的多个二叉树。,5.6 哈夫曼树及哈夫曼编码,WPL=32 WPL=41 WPL=30,106,哈夫曼树的特点：1.权值越大的叶子结点越靠近根结点，而权值越小的叶子结点越远离根结点。2.只有度为0（叶子结点）和度为2（分支结点）的结点，不存在度为1的结点.,5.6 哈夫曼树及哈夫曼编码,2,3,4,7,WPL=32 WPL=41 WPL=30,2,3,4,7,7,4,2,3,10

38、7,哈夫曼算法基本思想：初始化：由给定的n个权值w1，w2，wn构造n棵只有一个根结点的二叉树，从而得到一个二叉树集合FT1，T2，Tn；选取与合并：在F中选取根结点的权值最小的两棵二叉树分别作为左、右子树构造一棵新的二叉树，这棵新二叉树的根结点的权值为其左、右子树根结点的权值之和；删除与加入：在F中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到F中；重复、两步，当集合F中只剩下一棵二叉树时，这棵二叉树便是哈夫曼树。,5.6 哈夫曼树及哈夫曼编码,108,W2，3，4，5 哈夫曼树的构造过程,5.6 哈夫曼树及哈夫曼编码,重复第2步,5,4,3,2,5,重复第3步,109,哈夫曼算法

39、的存储结构,struct element int weight;int lchild,rchild,parent;,5.6 哈夫曼树及哈夫曼编码,110,伪代码,数组huffTree初始化，所有元素结点的双亲、左 右孩子都置为-1；2.数组huffTree的前n个元素的权值置给定值wn；3.进行n-1次合并 3.1 在二叉树集合中选取两个权值最小的根结点，其下标分别为i1,i2；3.2 将二叉树i1、i2合并为一棵新的二叉树k；,5.6 哈夫曼树及哈夫曼编码,111,哈夫曼树应用哈夫曼编码,编码：给每一个对象标记一个二进制位串来表示一组对象。例：ASCII，指令系统等长编码：表示一组对象的二进

40、制位串的长度相等。不等长编码：表示一组对象的二进制位串的长度不相等。,不等长编码什么情况下空间效率高？,等长编码什么情况下空间效率高？,5.6 哈夫曼树及哈夫曼编码,112,5.6 哈夫曼树及哈夫曼编码,前缀编码：一组编码中任一编码都不是其它任何一个编码的前缀。前缀编码保证了在解码时不会有多种可能。,例：一组字符A,B,C,D,E,F,G出现的频率分别是9,11,5,7,8,2,3，设计最经济的编码方案。,哈夫曼树应用哈夫曼编码,113,5.6 哈夫曼树及哈夫曼编码,编码方案：A：00B：10C：010D：110E：111F：0110G：0111,哈夫曼树应用哈夫曼编码,114,实习课内容：,用Huffman算法实现：w=2，3，5，7，11，13，17，19，23，29，31，37，41,