第六章 树和二叉树.ppt

《第六章 树和二叉树.ppt》由会员分享，可在线阅读，更多相关《第六章 树和二叉树.ppt（85页珍藏版）》请在三一文库上搜索。

1、第6章 树和二叉树,F 6.1 树的定义和基本术语 F 6.2 二叉树 F 6.3 遍历二叉树和线索二叉树 F 6.4 树和森林 F 6.6 赫夫曼树及其应用,特点：非线性结构，一个直接前驱，但可能有多个 直接后继（1：n）,第6章 树和二叉树,1.树的定义,注：树的定义具有递归性，即树中还有树。,由一个或多个（n 0）结点组成的有限集合。在任何一棵非空树T中： （1）有且仅有一个结点称为根（root）； （2）当n1时，其余的结点分为m（m 0）个 互不相交的有限集合T1、T2Tm。每个 集合本身又是棵树，被称作这个根的子树。,6.1 树的定义和基本术语,A,只有根结点的树,根,子树,6.1

2、 树的定义和基本术语,树的抽象数据类型定义,D是具有相同特性的数据元素的集合。,ADT Tree ,Tree,数据对象D:,数据操作P:,数据关系R:,若D是空集，则称为空树；/允许n=0 若D中仅含一个数据元素，则R为空集； 其他情况下的R存在二元关系： Root唯一/关于根的说明 DjDk= /关于子树不相交的说明 /关于数据元素的说明,/至少15个,6.1 树的定义和基本术语,图形表示法 嵌套集合表示法 广义表表示法 凹入表示法（目录表示法）,树的表示方法,6.1 树的定义和基本术语,图形表示法：,6.1 树的定义和基本术语,广义表表示法：,根作为由子树森林组成的表的名字写在表的左边,A

3、（B，C，D）,A（B，C（E,F,G,H），D）,凹入表示法：,6.1 树的定义和基本术语,嵌套表示法：,B,D,E,G,F,H,6.1 树的定义和基本术语,2.若干术语,根-根结点（没有前驱） 森林-指m棵不相交的树的集合,有序树-结点各子树从左至右有序，不能互换（左为第一） 无序树-结点各子树可互换位置,双亲-上层的那个结点（直接前驱） 孩子-下层结点的子树的根（直接后继） 兄弟-同一双亲下的同一层结点（孩子之间互称兄弟） 堂兄弟-双亲位于同一层的结点（但并非同一双亲） 祖先-从根到该结点所经分支的所有结点 子孙-该结点下层子树的任一结点,6.1 树的定义和基本术语,结点-树中的数据元素

4、 结点的度-结点拥有的子树的数目（有几个直接后继度就是几） 结点的层次-从根到该结点的层数（根结点算第一层）,叶子-度为0的点（终端结点） 分支结点-度不为0的点（非终端结点）,树的度-所有结点度中的最大值（Max各结点的度） 树的深度-所有结点中最大的层数（ Max各结点的层次 ） （或高度）,6.1 树的定义和基本术语,已知一棵树的集合为, , , , , , , , , , , ，请画出这棵树，并回答下列问题： （1）哪个是根结点？ （2）哪些是叶子结点？ （3）哪个是结点G的双亲？ （4）哪些是结点G的祖先？ （5）哪些是结点G的孩子？ （6）哪些是结点E的子孙？ （7）哪些是结点E的

5、兄弟？哪些是结点F的兄弟？ （8）结点B和N的层次号分别是什么？ （9）树的深度是多少？ （10）以C为根的子树的深度是多少？,课堂练习(一),一、对照右图回答下列问题： 1、这棵树的根结点？ 2、这棵树的叶子结点？ 3、结点k3的度？ 4、这棵树的度？ 5、这棵树的深度？ 6、结点k1的孩子结点？ 7、结点k3的双亲结点？ 8、以k3为根的子树的深度？,二、已知树的集合为,，分别用图形表示法、广义表表示法、嵌套表示法、凹入表示法画出这棵树。,课堂练习(一),二叉树的结构最简单，规律性最强； 可以证明，所有树都能转化为唯一对应的二叉树，不失一般性。,1. 二叉树的定义 2. 二叉树的性质 3.

6、 二叉树的存储结构,6.2 二叉树,1、二叉树的定义, 每个结点最多只有两棵子树（不存在度大于2的结点）； 左子树和右子树次序不能颠倒（有序树）。,基本特征：,基本形态：,具有3个结点的二叉树可能有几种不同形态？普通树呢？,6.2 二叉树-定义,2、二叉树的性质,性质1：在二叉树的第i层上至多有2i-1个结点（i0）。,问：第i层上至少有 个结点？,性质2：深度为k的二叉树至多有2k-1个结点（k0）。,性质3：对于任何一棵二叉树，若度2的结点数有n2个， 叶子结点数为n0，则n0=n2+1。,6.2 二叉树-性质,证明性质3：,二叉树中全部结点数n=n0+n1+n2(叶子数+度1的结数+度为

7、2的结点数),又 二叉树中全部结点数n=B+1(总分支数 + 根结点),（除根结点外，每个结点必有一个直接前驱，即一个分支）,而 总分支数B=n1+2n2(度为1必有1个直接后继，度为2必有2个直接后继),三式联立可得：n0+n1+n2=n1+2n2+1，即n0=n2+1,6.2 二叉树-性质,满二叉树：深度为k且有 2k-1个结点的二叉树。,特点：每一层上的结点数都是最大结点数。 可以对满二叉树的结点进行连续编号。,完全二叉树：深度为k，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n 的结点一一对应时，称之为完全二叉树。,特点: （1）叶子结点只可能在层次最大的

8、两层上出现； （2）对任一结点，若其右分支下的子孙的最大层次为h， 则其左分支下的子孙的最大层次数必为h或h+1。,6.2 二叉树-特例,6.2 二叉树-特例,对于特殊性质的二叉树，还具备以下2个性质：,性质4：具有n个结点的完全二叉树的深度必为log2n1。,性质5：如果对一棵有n个结点的完全二叉树(其深度为log2n1) 的结点按层序编号，则对任一结点i（1in），有： 1）如果i=1，则结点i是二叉树的根，无双亲；如果i1， 则其双亲parent（i）是结点 i/2 ； 2）如果2in，则结点i无左孩子(结点i为叶子结点)；否则其 左孩子lchild（i）是结点2i； 3）如果2i+1n

9、，则结点i无右孩子；否则其右孩子rchild(i) 是结点2i+1。,6.2 二叉树-性质,一、顺序存储结构,3、二叉树的存储结构,用一组地址连续的存储单元依次自上而下、自左至右存储二叉树上的结点元素。,A,B,C,D,E,F,G,H,I,A,F,仅适合于完全二叉树,对于非完全二叉树：将各层空缺处全部补上“虚结点”，其内容为0,缺点：浪费空间；插入、删除不便,6.2 二叉树-存储结构,二叉树的顺序存储表示可描述为：,#define MAX_TREE_SIZE 100 / 二叉树的最大结点数 typedef TElemType SqBiTreeMAX_TREE_SIZE; / 0号单元存储根结点

10、 SqBiTree bt;,即将 bt 定义为含有MAX_TREE_SIZE个 TElemType 类型元素的一维数组。,二、链式存储结构,二叉链表中包含2个指针域。一般从根结点开始存储。,为了便于找到结点的双亲，可再增加一个双亲域指针，将二叉链表变成三叉链表。,链表的头指针指向二叉树的根结点。,6.2 二叉树-存储结构,二叉链表类型表述如下：,typedef struct BiTNode / 结点结构 TElemType data; struct BiTNode *lchild, *rchild; / 左右孩子指针 BiTNode, *BiTree;,结点结构:,结论1：在含有n个结点的二叉

11、链表中有n1个空链域。（提示： n0 = n2+1 ）,两个结论,结论2：在含有n个结点的度为k的树中必有n(k-1)+1 个空链域。 （结论1的推广）,三叉链表类型表述如下：,typedef struct TriTNode DataType data; struct TriTNode *parent; struct TriTNode *lchild; struct TriTNode *rchild; TriTNode, *TriTree;,结点结构:,例：,二叉链表,三叉链表,在含有n个结点的二叉链表中有n+1个空链域,空指针个数：2*n0+1*n1+0*n2 =2n0+n1 =n0+n1+

12、n0 =n0+n1+n2+1 =n+1,6.2 二叉树-存储结构,1. 设T是一棵完全二叉树, 则T的根结点的左子树的结点数n与右子树的结点数n的大小关系是 。 2. 一棵深度为6的满二叉树有 个叶子和 个分支结点。 3. 设一棵完全二叉树具有36个结点，则此完全二叉树有 个叶子结点，有 个度为2的结点，有 个结点只有非空左子树，有 个结点只有非空右子树。 4. 一棵满k叉树上的叶子结点数n0和非叶子结点数n1之间满足以下关系： n0 = ( k-1)* n1 + 1 5.一棵二叉树若采用顺序存储结构，存储于数组T中，如下图所示，请画出该二叉树的二叉链表存储形式。,课堂练习(二),一、遍历二叉

13、树,按某条搜索路径访问树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。,二叉树由根、左子树、右子树构成，三者的组合可构成6种 遍历方案：根左右、根右左、左根右、左右根、右根左、右左根,若限定“先左后右”，则有3种实现方案： 根左右 左根右 左右根,先序遍历 中序遍历 后序遍历,6.3 遍历二叉树和线索二叉树,1、 先序遍历,2、 中序遍历,3、 后序遍历,访问根结点 先序遍历左子树 先序遍历右子树,A,B,D,C,F,G,H,I,D,B,A,F,C,H,G,I,D,B,F,H,I,G,C,A,例1：,6.3 遍历二叉树和线索二叉树,1、 先序遍历,2、 中序遍历,3、 后序遍历,+,

14、*,*,/,A,B,C,D,E,A,/,B,*,C,*,D,+,E,A,B,/,C,*,D,例2：,*,E,+,6.3 遍历二叉树和线索二叉树,例：已知一棵二叉树的中序序列和后序序列分别是BDCEAFHG 和 DECBHGFA，请画出这棵二叉树。,讨论：若已知先序序列（或后序序列）和中序序列，能否恢复 出对应的二叉树？,分析： 由后序遍历特征，根结点必在后序序列尾部（即A） 由中序遍历特征，根结点必在其中间，而且其左部必全部是左子树的子孙（即BDCE），其右部必全部是右子树的子孙（即FHG） 继而，根据后序中的DECB子树可确定B为A的左孩子，根据HGF子串可确定F为A的右孩子；以此类推,6.

15、3 遍历二叉树和线索二叉树,已知中序遍历：B D C E A F H G 已知后序遍历：D E C B H G F A,A,（D C E）,A,A,B,C,6.3 遍历二叉树和线索二叉树,已知先序遍历序列如下：ABDCEF,6.3 遍历二叉树和线索二叉树,二、线索二叉树,普通二叉树只能找到结点的左右孩子的信息，而该结点的直接前驱和直接后继只能在遍历过程中获得。,若将遍历后对应的有关前驱和后继预存起来，则从第一个结点开始就能很快地遍历整个树了。,例如中序遍历结果：A/B*C*D+E，实际上已将二叉树转为线性排列，显然具有唯一前驱和唯一后继。,如何预存这类信息呢？,增加两个域:前驱指针、后继指针,

16、利用n+1个空链域,6.3 遍历二叉树和线索二叉树,规定：,1）若结点有左子树，则lchild指向其左孩子； 否则，lchild指向其直接前驱（即线索）；,2）若结点有右子树，则rchild指向其右孩子； 否则，rchild指向其直接后继（即线索）；,约定： 当Tag域为0时，表示孩子情况； 当Tag域为1时，表示线索情况。,6.3 遍历二叉树和线索二叉树,有关线索二叉树的几个术语：,线索链表：用上述结点构成的二叉链表 线索：指向前驱和后继结点的指针 线索二叉树：同加上线索的二叉树（图形式样） 线索化：对二叉树以某种次序遍历使其变为线索二叉树的过程,线索化过程就是在遍历过程中修改空指针的过程：

17、 将空的lchild改为结点的直接前驱； 将空的rchild改为结点的直接后继。 非空指针呢？仍然指向孩子结点（称为“正常情况”）,6.3 遍历二叉树和线索二叉树,例：画出下列二叉树所对应的中序线索二叉树,中序遍历结果：HDIBE A FCG,NIL,NIL,6.3 遍历二叉树和线索二叉树,存储结构,6.3 遍历二叉树和线索二叉树,中序遍历结果：HDIBE A FCG,2. 对于前序遍历和后序遍历结果相同的二叉树为 。 A. 一般二叉树 B. 只有根结点的二叉树 C. 根结点无左孩子的二叉树 D. 根结点无右孩子的二叉树,3. 设n、m为一棵二叉树上的两个结点，在中序遍历中，n在m前的条件是

18、。 A. n在m的右面 B. n是m的祖先 C. n在m的左面 D. n在m的子孙,课堂练习(三),4、写出下列二叉树的先序、中序和后序遍历序列，并画出其后序线索二叉树。,5、某二叉树前序遍历序列是ABDGCEFH， 中序遍历序列是DGBAECHF，请写出其后序遍历结果。,课堂练习(三),1. 树的存储结构 2. 森林与二叉树的转换 3. 树和森林的遍历,6.4 树和森林,一、 树的存储结构,树有三种常用存储方式： 双亲表示法 孩子表示法 孩子兄弟表示法,1、用双亲表示法来存储,方法：用一组连续空间来存储树的结点，同时在每个结点中附设一个指示器，指示其双亲结点在链表中的位置。,6.4 树和森林

19、-树的存储,例1：双亲表示法,双亲表示法,缺点：求结点的孩子时需要遍历整个结构,A -1,B 0,C 0,D 1,E 1,F 4,G 4,H 4,6.4 树和森林-树的存储,2、用孩子表示法来存储,方法：将每个结点的孩子排列起来，形成一个带表头（装父亲结点）的线性表（n个结点要设立n个链表），再将n个表头用数组存放起来，这样就形成一个混合结构。,孩子表示法,0 1 2 3 4 5 6 7,6.4 树和森林-树的存储,带双亲的 孩子表示法,Parent Data,A B C D E F G H,-1 0 0 1 1 4 4 4, ,6.4 树和森林-树的存储,3、用孩子兄弟表示法来存储,方法：用

20、二叉链表来存储树，但链表的两个指针域含义不同。,孩子兄弟 表示法,6.4 树和森林-树的存储,二、 森林与二叉树的转换,转换步骤： 结点的第一孩子做为其左孩子 结点的右邻近兄弟做为其右孩子,A,二叉树,1、树与二叉树的转换,6.4 树和森林-树与二叉树的转换,2、二叉树与树的转换,转换步骤：把所有右孩子都变成其双亲的兄弟,A,6.4 树和森林-树与二叉树的转换,3、森林与二叉树的转换,转换步骤： 各树要先各自转为二叉树 依次连接到前一个二叉树的右子树上,A,E,G,6.4 树和森林-森林与二叉树的转换,三、树和森林的遍历,1、树的遍历,先序遍历,后序遍历, 访问根结点 依次先序遍历根结点的每棵

21、子树, 依次后序遍历根结点的每棵子树 访问根结点,A,B,C,D,E,B,D,C,E,A,先序： 中序： 后序：,ABCDE,BDCEA,DECBA,结论： 树后序遍历相当于对应二叉树的中序遍历； 树没有中序遍历，因为子树无左右之分。,6.4 树和森林-树的遍历,2、森林的遍历,先序遍历,中序遍历,访问森林中第一棵树的根结点 先序遍历第一棵树中根结点的子树森林 先序遍历除去第一棵树之后剩余的树构成的森林,中序遍历森林中第一棵树的根结点的子树森林 访问第一棵树的根结点 中序遍历除去第一棵树之后剩余的树构成的森林,A,B,C,D,E,F,G,H,I,J,B,C,D,A,F,E,H,J,I,G,6.

22、4 树和森林-森林的遍历,1、写出下列树的先序和后序遍历序列，并将其转换为相应的二叉树。,课堂练习(四),2、把如图所示的树转换成二叉树。,课堂练习(四),2、把如图所示的森林转换成二叉树。,课堂练习(四),3、把如图所示的二叉树转换成森林。,课堂练习(四),一、 最优二叉树（赫夫曼树）,路 径：由一个结点到另一结点间的分支所构成。 路径长度：路径上的分支数目。 树的路径长度：从根到每一结点的路径长度之和。 带权路径长度：结点到根的路径长度与结点上权值的乘积。 树的带权路径长度：树中所有叶子结点的带权路径长度之和。 赫夫曼树：带权路径长度最小的树。,6.6 赫夫曼树及其应用,例：三棵二叉树中，

23、4个叶子结点a、b、c、d分别带权7、5、2、4，它们的带权路径长度分别为?, WPL=7*2+5*2+2*2+4*2=36, WPL=7*3+5*3+2*1+4*2=46, WPL=7*1+5*2+2*3+4*3=35,6.6 赫夫曼树及其应用,二、构造赫夫曼树的基本步骤,1）根据给定的n个权值1，2，n，构成n棵二叉树的集合F=T1，T2，Tn，其中每棵二叉树Ti中只有一个带权为i的根结点，其左右子树均空； 2）在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且新的二叉树的根结点的权值为其左、右子树上根结点的权值之和； 3）在F中删除这两棵树，同时将新得到的二叉树加入F中

24、； 4）重复2）和3），直到F只含有一棵树为止。,6.6 赫夫曼树及其应用,例：画出以7、5、2、4四个权值构造生成的赫夫曼树。,步骤2,7,5,步 骤 3,7,4骤步,步骤1,一棵有n个叶子结点的赫夫曼树共有2n-1个结点。,6.6 赫夫曼树及其应用,三、赫夫曼编码,设有电文A B A C C D A,若00、01、10、11，则00 01 00 10 10 11 00，总长14位；,若0、00、1、01，则0 00 0 1 1 01 0，总长9位，但译码时产生二意性。,若要设计长短不等的编码，则必须是任一个字符的编码都不是另一个字符的编码的前缀，称为前缀编码。,6.6 赫夫曼树及其应用,左

25、分支为0 右分支为1,Huffman编码的结果是： a=0 b=10 c=110 d=111,由于赫夫曼树的WPL最小，说明编码所需要的长度最小。所以，这种编码已广泛应用于网络通信中。,设计电文总长度最短的二进制前缀编码即为以n种字符出现的频率作权值，设计一棵赫夫曼树的问题，由此得到的二进制前缀编码便称为赫夫曼编码。,6.6 赫夫曼树及其应用,例：已知某系统在通信联络中只可能出现八种字符，其概率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10，试设计赫夫曼编码。,解：先将概率放大100倍，以方便构造赫夫曼树。 权值集合w=7，19，2，6，32，3，21，1

26、0,6.6 赫夫曼树及其应用,typedef struct int weight；/权值分量（可放大取整） int parent，lchild，rchild； /双亲和孩子分量 HTNode，*HuffmanTree；/用动态数组存储Huffman树 typedef char*HuffmanCode； /动态数组存储Huffman编码表,1、Huffman树和Huffman树编码的存储表示：,四、如何编程实现Huffman编码？,参见教材P147,建议1：Huffman树中结点的结构可设计成4分量形式：,建议2： Huffman树的存储结构可采用顺序存储结构： 将整个Huffman树的结点存储

27、在一个数组HT1nm中;各叶子结点的编码存储在另一“复合”数组HC1n中,指针型指针,6.6 赫夫曼树及其应用,2、先构造Huffman树HT,Void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n),if (n=1)return; m=2*n-1; /n 个叶子的HuffmanTree共有2n-1个结点； HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); /0单元未用,*w存放n个字符的权值,for(p=HT,i=1; i=n; +i,+p,+w)*p=*w,0,0,0; /初

28、始化前n个单元 for(；i=m; +i,+p) *p =0,0,0,0; /对叶子之后的存储单元清零 for(i=n+1;i=m; +i) /建Huffman树(从叶子开始) Select(HT, i-1, s1, s2); /在HT1i-1选择parent为0且weight最小的两个结点，其序号分别为S1和s2 HTs1.parent=i; HTs2.parent=i; HTi.lchild=s1; HTi.rchild=s2; HTi.weight=HTs1.weight+ HTs2.weight; ,6.6 赫夫曼树及其应用,3、求出n个字符的Huffman编码HC,HC=(Huffm

29、anCode)malloc(n+1)*sizeof(char*); /分配n个字符编码的头指针 向量（一维数组） cd=(char*) malloc(n*sizeof(char); /分配求编码的工作空间(n) cdn-1=0; /编码结束符（从cd0cdn-1为合法空间） for(i=1;i=n;+i) /逐个字符求Huffman编码 start=n-1; /编码结束符位置 for(c=i,f=HTi.parent; f!=0; c=f, f=HTf.parent)/从叶子到根逆向求编码 if(HTf.lchild=c) cd-start=0; else cd-start=1; HCi=(c

30、har*)malloc(n-start)*sizeof(char);/为第i个字符编码分配空间 strcpy(HCi, /释放工作空间 ,6.6 赫夫曼树及其应用,2、已知某字符串S中共有8种字符，各种字符分别出现2次、1次、4次、5次、7次、3次、4次和9次，对该字符串用0、1进行前缀编码。,1、对给定的一组值5，2，9，11，8，3，7构造赫夫曼树，并计算它的带权路径长度。,课堂练习(五),树,森林,二叉树,存储结构,遍历,先序遍历,后序遍历,双亲表示法 孩子表示法 孩子兄弟法,先 中 序 序 遍 遍 历 历,1、定义和性质 2、存储结构 3、遍历 4、线索化,赫夫曼树,赫夫曼编码,小结,

31、1 在任何非空二叉树中，叶子结点数等于度为2的结点数+1，即n0=n2+1。 ( ) 2 在线索二叉树中，根据线索可以找到树中任何一个结点在相应遍历序列中的直接前驱。( ) 3 在非空完全二叉树中，若一个结点不存在左孩子，则该结点一定是叶子结点。( ) 4 在非空完全二叉树中，若一个结点不存在右孩子，则该结点一定是叶子结点。( ) 5在一棵完全二叉树中，对任一结点而言，若其左孩子不存在，则右孩子一定不存在。( ),课堂练习（判断题）,1不含任何结点的空树 。 （）是一棵树; （）是一棵二叉树; （）是一棵树也是一棵二叉树; （）既不是树也不是二叉树 2二叉树是非线性数据结构，所以 。 它不能用

32、顺序存储结构存储; 它不能用链式存储结构存储; 顺序存储结构和链式存储结构都能存储; 顺序存储结构和链式存储结构都不能使用 3. 具有n(n0)个结点的完全二叉树的深度为 。 () log2(n) () log2(n) () log2(n) +1 () log2(n)+1 4把一棵树转换为二叉树后，这棵二叉树的形态是 。 唯一的 有多种 有多种，但根结点都没有左孩子 有多种，但根结点都没有右孩子,课堂练习（选择题）,5. 树是结点的有限集合，它 A 根结点，记为T。其余的结点分成为m（m0）个 B 的集合T1，T2，Tm，每个集合又都是树，此时结点T称为Ti的父结点，Ti称为T的子结点（1im

33、）。一个结点的子结点个数为该结点的 C 。 供选择的答案 A：有0个或1个 有0个或多个 有且只有1个 有1个或1个以上 B: 互不相交 允许相交 允许叶结点相交 允许树枝结点相交 C： 权 维数 度 序 6. 在完全的二叉树中，若一个结点没有 A ，则它必定是叶结点。每棵树都能惟一地转换成与它对应的二叉树。由树转换成的二叉树里，一个结点N的左孩子是N在原树里对应结点的 B ，而N的右子女是它在原树里对应结点的 C 。 A: 左结点 右结点 左结点或者没有右结点 兄弟 BC： 最左结点 最右结点 最邻近的右兄弟 最邻近的左兄弟 最左的兄弟 最右的兄弟,课堂练习,1.试写出如图所示的二叉树分别按

34、先序、中序、后序遍历时得到的结点序列。,2. 给定某二叉树的中序序列为B R X S A C U Y V，后序序列为 B R S X C U V Y A，试画出该二叉树的结构图。,作业(一),3. 对所示二叉树进行后序线索化。,作业(一),4. 将下列二叉链表改为先序线索链表。,作业(一),1.写出如图所示树的三种存储结构。,作业(二),3.把如图所示的森林分别转换成二叉树。,11,作业(二),4.把如图所示的二叉树分别转换成树或森林。,A,作业(二),1、设给定权值2，3，4，7，8，9，试构造一棵赫夫曼树，并求其加权路径长度WPL。 2、已知某系统在通讯时，只出现C，A，S，T，B五种字符

35、，它们出现的频率依次为2，4，2，3，3，试设计Huffman编码。,作业(三),教学要求： 1、了解树和森林的概念。包括树的定义、树的术语和性质； 2、熟练掌握二叉树的结构特性、遍历方法，熟悉二叉树的各 种存储结构； 3、熟悉树的各种存储结构及其特点，掌握树、森林与二叉树 的转换方法; 4、掌握建立赫夫曼树和赫夫曼编码的方法及带权路径长度的 计算。,第6章 树和二叉树,void Creat_Bintree(BiTree ,按照前序遍历建立二叉树,void Inorder(BiTree ,按照中序遍历建立二叉树,已知一棵二叉树是以二叉链表的形式存储的，其结点结构说明如下： struct nod

36、e int data; / 结点的数据场。 struct node *left; / 给出结点的左儿子的地址。 struct node * right; / 给出结点的右儿子的地址。 ； 请在 处进行填空，求出以T 为根的二叉树或子树的结点个数。 注意，每空只能填一个语句 int size (struct node * T ) if ( ) return 0; else ; ,T = NULL return 1 +size(T-left) + size(T-right),有如下递归函数 int D(int m) int vallue; if (m=0) value=3; else value=

37、D(m-1)+5; return value; 执行语句printf(“%dn”,D(3);的结果是 。,18,有如下递归过程 void print(int w) int i; if (w!=0) print(w-1); for(i=1;i=w;i+) printf(“%3d”,w) printf(“n”); 调用语句print(4)的结果是 。,1 2 2 3 3 3 4 4 4 4,1、 给定某二叉树的中序序列为B R X S A C U Y V，后序序列为B R S X C U V Y A，试写出该二叉树的后序遍历序列。 2、设给定权值2，3，4，7，8，9，试构造一棵赫夫曼树，并求其加权路径长度WPL。,3、下面森林转换成二叉树。,4、下面二叉树转换成森林。,