数据结构第六章 树和二叉树.ppt

《数据结构第六章 树和二叉树.ppt》由会员分享，可在线阅读，更多相关《数据结构第六章 树和二叉树.ppt（119页珍藏版）》请在三一办公上搜索。

1、第6章 树和二叉树,6.1 树的定义和基本术语,6.2 二叉树,6.3 遍历二叉树和线索二叉树,6.4 树和森林,6.6 哈夫曼树及其应用,作业,实验,6.1 树的定义和基本术语,结点:,结点的度:,树的度:,叶子结点:,分支结点:,数据元素+若干指向子树的分支,分支的个数,树中所有结点的度的最大值,度为零的结点,度大于零的结点,D,H,I,J,M,(从根到结点的)路径：,孩子结点、双亲结点兄弟结点、堂兄弟祖先结点、子孙结点,由从根到该结点所经分支和结点构成,结点的层次:,树的深度：,假设根结点的层次为1，第l 层的结点的子树根结点的层次为l+1,树中叶子结点所在的最大层次,森林：,是m（m0

2、）棵互不相交的树的集合,A,B,C,D,E,F,G,H,I,J,M,K,L,A(B(E,F(K,L),C(G),D(H,I,J(M),T1,T3,T2,树根,例如:,()有确定的根；()树根和子树根之间为有向关系。,有向树：,有序树：,子树之间存在确定的次序关系。,无序树：,子树之间不存在确定的次序关系。,对比树型结构和线性结构的结构特点,线性结构,树型结构,第一个数据元素(无前驱),根结点(无前驱),最后一个数据元素(无后继),多个叶子结点(无后继),其它数据元素(一个前驱、一个后继),其它数据元素(一个前驱、多个后继),而现实中的许多事物的关系并非这样简单，如人类社会的族谱、各种社会组织机

3、构以及城市交通、通讯等，这些事物中的联系都是非线性的，采用非线性结构进行描绘会更明确和便利。,在前面几章里讨论的数据结构都属于线性结构,线性结构的特点是逻辑结构简单，易于进行查找、插入和删除等操作,其主要用于对客观世界中具有单一的前驱和后继的数据关系进行描述,所谓非线性结构是指，在该结构中至少存在一个数据元素，有两个或两个以上的直接前驱（或直接后继）元素。,树型结构和图型就是其中十分重要的非线性结构，可以用来描述客观世界中广泛存在的层次结构和网状结构的关系，如前面提到的族谱、城市交通等。,本章对树型结构中最简单、应用十分广泛的二叉树结构进行讨论。,二叉树或为空树，或是由一个根结点加上 两棵分别

4、称为左子树和右子树的、互不交的二叉树组成。,A,B,C,D,E,F,G,H,K,根结点,左子树,右子树,6.2 二叉树,6.2.1 二叉树的定义,二叉树的五种基本形态：,N,空树,只含根结点,N,N,N,L,R,R,右子树为空树,L,左子树为空树,左右子树均不为空树,二叉树的主要基本操作：,查 找,插 入,删 除,性质 1：在二叉树的第 i 层上至多有2i-1 个结点。(i1),用归纳法证明：归纳基：归纳假设：归纳证明：,i=1 层时，只有一个根结点：2i-1=20=1；,假设对所有的 j，1 j i，命题成立；,二叉树上每个结点至多有两棵子树，则第 i 层的结点数=2i-2 2=2i-1。,

5、6.2.2 二叉树的性质,性质 2：深度为 k 的二叉树上至多含 2k-1 个结点（k1）。,证明：,基于上一条性质，深度为 k 的二叉树上的结点数至多为 20+21+2k-1=2k-1。,性质 3：对任何一棵二叉树，若它含有n0 个叶子结点、n2 个度为 2 的结点，则必存在关系式：n0=n2+1。,证明：,设 二叉树上结点总数 n=n0+n1+n2又 二叉树上分支总数 b=n1+2n2 而 b=n-1=n0+n1+n2-1由此，n0=n2+1。,两类特殊的二叉树：,满二叉树：指的是深度为k且含有2k-1个结点的二叉树。,完全二叉树：树中所含的 n 个结点和满二叉树中编号为 1 至 n 的结

6、点一一对应。,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,a,b,c,d,e,f,g,h,i,j,性质 4：具有 n 个结点的完全二叉树的深度为 log2n+1。,证明：,设完全二叉树的深度为 k 则根据第二条性质得 2k-1 n 2k 即 k-1 log2 n k 因为 k 只能是整数，因此，k=log2n+1。,性质 5：,若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中任意一个编号为 i 的结点：(1)若 i=1，则该结点是二叉树的根，无双亲，否则，编号为 i/2 的结点为其双亲结点；(2)若 2in，则该结点无左孩子

7、，否则，编号为 2i 的结点为其左孩子结点；(3)若 2i+1n，则该结点无右孩子结点，否则，编号为2i+1 的结点为其右孩子结点。,2.二叉树的链式存储表示,1.二叉树的顺序存储表示,6.2.3 二叉树的存储结构,#define MAX_TREE_SIZE 100/二叉树的最大结点数typedef TElemType SqBiTreeMAX_ TREE_SIZE;/0号单元存储根结点SqBiTree bt;,1.二叉树的顺序存储表示,例如:,A,B,C,D,E,F,A B D C E F,0 1 2 3 4 5 6 7 8 9 10 11 12 13,1,4,0,13,2,6,2、二叉树的链

8、式存储表示,（1）二叉链表,（2）三叉链表,A,D,E,B,C,F,root,lchild data rchild,结点结构:,（1）二叉链表,typedef struct BiTNode/结点结构 TElemType data;struct BiTNode*lchild,*rchild;/左右孩子指针 BiTNode,*BiTree;,lchild data rchild,结点结构:,C 语言的类型描述如下:,A,D,E,B,C,F,root,（2）三叉链表,parent lchild data rchild,结点结构:,typedef struct TriTNode/结点结构 TElemT

9、ype data;struct TriTNode*lchild,*rchild;/左右孩子指针 struct TriTNode*parent;/双亲指针 TriTNode,*TriTree;,parent lchild data rchild,结点结构:,C 语言的类型描述如下:,6.3 遍历二叉树和线索二叉树,一、问题的提出,二、先左后右的遍历算法,三、算法的递归描述,四、中序遍历算法的非递归描述,五、遍历算法的应用举例（对教材的补充）,6.3.1 遍历二叉树,顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次。,一、问题的提出,“访问”的含义可以很广，如：输出

10、结点的信息等。,“遍历”是任何类型均有的操作，对线性结构而言，只有一条搜索路径(因为每个结点均只有一个后继)，故不需要另加讨论。,而二叉树是非线性结构，每个结点有两个后继，则存在如何遍历即按什么样的搜索路径遍历的问题。,对“二叉树”而言，可以有三条搜索路径：,1先上后下的按层次遍历；2先左（子树）后右（子树）的遍历；3先右（子树）后左（子树）的遍历。,二、先左后右的遍历算法,先（根）序的遍历算法,中（根）序的遍历算法,后（根）序的遍历算法,若二叉树为空树，则空操作；否则，（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。,先（根）序的遍历算法：,若二叉树为空树，则空操作；否则，（1

11、）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。,中（根）序的遍历算法：,若二叉树为空树，则空操作；否则，（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。,后（根）序的遍历算法：,三、算法的递归描述,void Preorder(BiTree T,void(*visit)(TElemType/遍历右子树,算法6.1,四、中序遍历算法的非递归描述,Status InOrderTraverse(BiTree T,Status(*visit)(TElemType e)InitStack(S);push(S,T);while(!StackEmpty(S)while(GetTop(

12、S,p),算法6.2,算法6.3,Status InOrderTraverse(BiTree T,Status(*visit)(TElemType e)InitStack(S);p=T;while(p|!StackEmpty(S)if(p)push(S,p);p=p-lchild;else pop(S,p);if(!visit(p-data)return ERROR;return OK;,五、遍历算法的应用举例,1、统计二叉树中叶子结点的个数(先序遍历),2、求二叉树的深度(后序遍历),3、建立二叉树,1、统计二叉树中叶子结点的个数,算法基本思想:,先序(或中序或后序)遍历二叉树，在遍历过程中

13、查找叶子结点，并计数。由此，需在遍历算法中增添一个“计数”的参数，并将算法中“访问结点”的操作改为：若是叶子，则计数器增1。,void CountLeaf(BiTree T,int/if/CountLeaf,2、求二叉树的深度(后序遍历),算法基本思想:,从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加1。由此，需先分别求得左、右子树的深度，算法中“访问结点”的操作为：求得左、右子树深度的最大值，然后加 1。,首先分析二叉树的深度和它的左、右子树深度之间的关系。,int Depth(BiTree T)/返回二叉树的深度 if(!T)depthval=0;else depthL

14、eft=Depth(T-lchild);depthRight=Depth(T-rchild);depthval=1+(depthLeft depthRight?depthLeft:depthRight);return depthval;,不同的定义方法相应有不同的存储结构的建立算法,3、建立二叉树,（1）以字符串的形式 根 左子树 右子树定义一棵二叉树,例如:,A,B,C,D,以空白字符“”表示,A(B(,C(,),D(,),空树,只含一个根结点的二叉树,A,以字符串“A”表示,以下列字符串表示,Status CreateBiTree(BiTree/CreateBiTree,算法6.4,A B

15、 C D,A,B,C,D,上页算法执行过程举例如下：,A,T,B,C,D,（2）按给定的表达式建相应二叉树,由先缀表示式建树例如：已知表达式的先缀表示式-+a b c/d e,由原表达式建树例如：已知表达式(a+b)c d/e,对应先缀表达式-+a b c/d e的二叉树,a,b,c,d,e,-,+,/,特点：操作数为叶子结点 运算符为分支结点,scanf(,由先缀表示式建树的算法的基本操作：,a+b,(a+b)c d/e,a+bc,分析表达式和二叉树的关系:,a,b,+,a,b,c,+,a,b,c,+,(a+b)c,a,b,c,d,e,-,+,/,基本操作:,scanf(,void CrtE

16、xptree(BiTree/CrtExptree,switch(ch)case(:Push(S,ch);break;case):Pop(S,c);while(c!=()CrtSubtree(t,c);/建二叉树并入栈 Pop(S,c)break;defult:/switch,while(!Gettop(S,c),建叶子结点的算法为：,void CrtNode(BiTree,建子树的算法为：,void CrtSubtree(Bitree,仅知二叉树的先序序列“abcdefg”不能唯一确定一棵二叉树，,（3）由二叉树的先序和中序序列建树,如果同时已知二叉树的中序序列“cbdaegf”，则会如何？,

17、二叉树的先序序列,二叉树的中序序列,左子树,左子树,右子树,右子树,根,根,a b c d e f g,c b d a e g f,例如:,a,a,b,b,c,c,d,d,e,e,f,f,g,g,a,b,c,d,e,f,g,先序序列中序序列,void CrtBT(BiTree else/CrtBT,T=(BiTNode*)malloc(sizeof(BiTNode);T-data=preps;if(k=is)T-Lchild=NULL;else CrtBT(T-Lchild,pre,ino,ps+1,is,k-is);if(k=is+n-1)T-Rchild=NULL;else CrtBT(T

18、-Rchild,pre,ino,ps+1+(k-is),k+1,n-(k-is)-1);,遍历二叉树的结果是，求得结点的一个线性序列。,A,B,C,D,E,F,G,H,K,例如:,先序序列:A B C D E F G H K,中序序列:B D C A H G K F E,后序序列:D C B H K G F E A,6.3.2 线索二叉树,指向该线性序列中的“前驱”和“后继”的指针，称作“线索”,与其相应的二叉树，称作“线索二叉树”,包含“线索”的存储结构，称作“线索链表”,A B C D E F G H K,D,C,B,E,对线索链表中结点的约定：,在二叉链表的结点中增加两个标志域，并作如下

19、规定：,若该结点的左子树不空，则Lchild域的指针指向其左子树，且左标志域的值为“指针 Link”；否则，Lchild域的指针指向其“前驱”，且左标志的值为“线索 Thread”。,若该结点的右子树不空，则rchild域的指针指向其右子树，且右标志域的值为“指针 Link”；否则，rchild域的指针指向其“后继”，且右标志的值为“线索 Thread”。,如此定义的二叉树的存储结构称作“线索链表”。,6.4.1 树的三种存储结构,一、双亲表示法,二、孩子链表表示法,三、树的二叉链表(孩子-兄弟）存储表示法,6.4 树和森林,A,B,C,D,E,F,G,0 A-11 B 02 C 03 D 0

20、4 E 2 5 F 26 G 5,r=0n=6,data parent,一、双亲表示法:,typedef struct PTNode Elem data;int parent;/双亲位置域 PTNode;,data parent,#define MAX_TREE_SIZE 100,结点结构:,C语言的类型描述:,typedef struct PTNode nodes MAX_TREE_SIZE;int r,n;/根结点的位置和结点个数 PTree;,树结构:,A,B,C,D,E,F,G,0 A-11 B 02 C 03 D 04 E 25 F 26 G 5,r=0n=6,data firstc

21、hild,1 2 3,4 5,6,二、孩子链表表示法:,-1000224,typedef struct CTNode int child;struct CTNode*next;*ChildPtr;,孩子结点结构:,child next,C语言的类型描述:,typedef struct Elem data;ChildPtr firstchild;/孩子链的头指针 CTBox;,双亲结点结构,data firstchild,typedef struct CTBox nodesMAX_TREE_SIZE;int n,r;/结点数和根结点的位置 CTree;,树结构:,A,B,C,D,E,F,G,AB

22、 C E D F G,root,AB C E D F G,三、树的二叉链表(孩子-兄弟）存储表示法,typedef struct CSNode Elem data;struct CSNode*firstchild,*nextsibling;CSNode,*CSTree;,C语言的类型描述:,结点结构:,firstchild data nextsibling,6.4.2 森林和二叉树的对应关系,设森林 F=(T1,T2,Tn);T1=(root，t11,t12,t1m);,二叉树 B=(LBT,Node(root),RBT);,由森林转换成二叉树的转换规则为:,若 F=，则 B=；否则，由 RO

23、OT(T1)对应得到 Node(root)；由(t11,t12,t1m)对应得到 LBT；由(T2,T3,Tn)对应得到 RBT。,由二叉树转换为森林的转换规则为：,若 B=，则 F=；否则，由 Node(root)对应得到 ROOT(T1)；由LBT 对应得到(t11,t12,，t1m)；由RBT 对应得到(T2,T3,Tn)。,由此，树的各种操作均可对应二叉树的操作来完成。,应当注意的是，和树对应的二叉树，其左、右子树的概念已改变为：左是孩子，右是兄弟。,6.4.3 树和森林的遍历,树的遍历可有三条搜索路径:,按层次遍历:,先根(次序)遍历:,后根(次序)遍历:,若树不空，则先访问根结点，

24、然后依次先根遍历各棵子树。,若树不空，则先依次后根遍历各棵子树，然后访问根结点。,若树不空，则自上而下自左至右访问树中每个结点。,A B C DE F G H I J K,先根遍历时顶点的访问次序：,A B E F C D G H I J K,后根遍历时顶点的访问次序：,E F B C I J K H G D A,层次遍历时顶点的访问次序：,A B C D E F G H I J K,B C DE F G H I J K,1森林中第一棵树的根结点；,2森林中第一棵树的子树森林；,3森林中其它树构成的森林。,森林由三部分构成：,1.先序遍历,森林的遍历,若森林不空，则访问森林中第一棵树的根结点；

25、先序遍历森林中第一棵树的子树森林；先序遍历森林中(除第一棵树之外)其 余树构成的森林。,即：依次从左至右对森林中的每一棵树进行先根遍历。,中序遍历,若森林不空，则中序遍历森林中第一棵树的子树森林；访问森林中第一棵树的根结点；中序遍历森林中(除第一棵树之外)其 余树构成的森林。,即：依次从左至右对森林中的每一棵树进行后根遍历。,最优树的定义 如何构造最优树 前缀编码,6.6 哈夫曼树及其应用,一、最优树的定义,树的路径长度定义为：树中每个结点的路径长度之和。,结点的路径长度定义为：从根结点到该结点的路径上 分支的数目。,树的带权路径长度定义为：树中所有叶子结点的带权路径长度之和 WPL(T)=w

26、klk(对所有叶子结点)。,在所有含 n 个叶子结点、并带相同权值的 m 叉树中，必存在一棵其带权路径长度取最小值的树，称为“最优树”。,例如：,2,7 9,7,5,4,9,2,WPL(T)=72+52+23+43+92=60,WPL(T)=74+94+53+42+21=89,5,4,根据给定的 n 个权值 w1,w2,wn，构造 n 棵二叉树的集合 F=T1,T2,Tn，其中每棵二叉树中均只含一个带权值 为 wi 的根结点，其左、右子树为空树；,二、如何构造最优树,(1),(赫夫曼算法)以二叉树为例：,在 F 中选取其根结点的权值为最 小的两棵二叉树，分别作为左、右子树构造一棵新的二叉树，并

27、 置这棵新的二叉树根结点的权值 为其左、右子树根结点的权值之 和；,(2),从F中删去这两棵树，同时加入 刚生成的新树；,重复(2)和(3)两步，直至 F 中只 含一棵树为止。,(3),(4),9,例如:已知权值 W=5,6,2,9,7,5,6,2,7,5,2,7,6,9,7,6,7,13,9,5,2,7,6,7,13,9,5,2,7,9,5,2,7,16,6,7,13,29,0,0,0,0,1,1,1,1,00,01,10,110,111,指的是，任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀。,三、前缀编码,利用赫夫曼树可以构造一种不等长的二进制编码，并且构造所得的赫夫曼编码是

28、一种最优前缀编码，即使所传电文的总长度最短。,1.熟练掌握二叉树的结构特性，了解相应的证明方法。2.熟悉二叉树的各种存储结构的特点及适用范围。3.遍历二叉树是二叉树各种操作的基础。实现二叉树遍历的具体算法与所采用的存储结构有关。掌握各种遍历策略的递归算法，灵活运用遍历算法实现二叉树的其它操作。层次遍历是按另一种搜索策略进行的遍历。,4.理解二叉树线索化的实质是建立结点与其在相应序列中的前驱或后继之间的直接联系，熟练掌握二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。二叉树的线索化过程是基于对二叉树进行遍历，而线索二叉树上的线索又为相应的遍历提供了方便。,5.熟悉树的各种存储

29、结构及其特点，掌握树和森林与二叉树的转换方法。建立存储结构是进行其它操作的前提，因此读者应掌握 1 至 2 种建立二叉树和树的存储结构的方法。6.学会编写实现树的各种操作的算法。7.了解最优树的特性，掌握建立最优树和哈夫曼编码的方法。,作业,一、选择题,1、树最适合用来表示_A）有序数据元素B）无序数据元素C）元素之间具有分支层次关系的数据D）元素之间无联系的数据,2、将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为_。A）98 B）99 C）50 D）48,3、在下图所示的4棵二叉树中，_不是完全二叉树。A）

30、图（a）B）图（b）C）图（c）D）图（d）,4、在一棵二叉树中，双分支的结点数为15，单分支结点数为30，则叶子结点数为_。A）15 B）16 C）17 D）47,5、判断线索二叉树中某结点*p有左孩子的条件是_。A）p-lchild=NULL B）p-lchild=NULLC）p-ltag=0 D）p-ltag=1,6、如果T1是由有序树T转换而来的二叉树，那么T中结点的前序遍历序列就是T1中结点的_遍历序列。A）前序 B）中序 C）后序 D）层次序,g,7、一棵二叉树如下图所示，其中序遍历的序列为_。A）abdgcefh B）dgbaechfC）gdbehfca D）abcdefgh,8

31、、深度为5的二叉树至多有_个结点。A）16 B）32 C）31 D）10,9、在一非空二叉树的中序遍历序列中，根结点的右边_。A）只有右子树上的所有结点 B）只有右子树上的部分结点C）只有左子树上的部分结点 D）只有左子树上的所有结点,10、如下图所示的T2是由森林T1转换而来的二叉树，那么森林T1有_个叶结点。A）4 B）5 C）6 D）7,11、设n、m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是_。A）n在m右方 B）n是m祖先 C）n在m左方 D）n是m子孙,12、有n个叶子结点的哈夫曼树的结点总数为_。A）不确定 B）2n C）2n1 D）2n1,13、设树T的度为4，其

32、中度为1、2、3、4的结点个数分别为4、2、1、1，则T中的叶子数为_。A）5 B）6 C）7 D）8,14、有n个叶子的哈夫曼树的结点总数为_A）不确定 B）2n C）2n1 D）2n1,15、树的先序遍历是_A）先访问树的根结点，再从左到右依次先序遍历根结点的各子树B）先序遍历根结点的各子树，最后访问根结点C）先从左到右依次先序遍历根结点的各子树D）先访问树的根结点，再从右到左依次先序遍历根结点的各子树,16、除根结点外，树上每个结点_A）可有任意多个孩子，任意多个双亲 B）可有任意多个孩子、一个双亲C）可有一个孩子、任意多个双亲 D）只有一个孩子、一个双亲,18、现有一棵结点总数为20的

33、二叉树，它含有4个度为2的结点，由此可知其叶子结点数为_A）20 B）16 C）11 D）5,19、若由一棵一般树转化得到的二叉树是非空二叉树，则该二叉树的形状是_A）根结点无右子树的二叉树 B）根结点无左子树的二叉树C）根结点可能有左子树和右子树 D）各结点只有一个孩子的二叉树,20、若由森林转化得到的二叉树是非空二叉树，则该二叉树的形状是_A）根结点无右子树的二叉树 B）根结点无左子树的二叉树C）根结点可能有左子树和右子树 D）各结点只有一个孩子的二叉树,21、哈夫曼树是访问叶子结点的外部路径长度_的二叉树。A）最短 B）最长 C）可变 D）固定,22、从1开始对二叉树进行连续编号，要求每

34、个结点的编号大于其左、右孩子的编号。在同一个结点的左、右孩子中，其左孩子的编号小于其右孩子的编号，则可采用_遍历实现编号。A）先序 B）中序 C）后序 D）从根开始的层次遍历,23、二叉树在线索化后，下列问题中相对较难解决的是_A）先序线索二叉树中求先序后继 B）中序线索二叉树中求中序后继C）中序线索二叉树中求中序前趋 D）后序线索二叉树中求后序后继,24、一棵左子树为空的二叉树在先序线索化后，其空指针域数为_A）0 B）1 C）2 D）不确定,25、对具有100个结点的二叉树，若用二叉链表存储，则其指针域部分用来指向结点的左、右孩子，其余_个指针域为空。A）50 B）99 C）100 D）1

35、01,26、设有13个值，用它们组成一棵哈夫曼树，则该哈夫曼树中共有_个结点。A）13 B）12 C）26 D）25,二、填空题,1、若已知一棵二叉树的先序序列和中序序列分别是BEFCGDH和FEBGCHD，则它的后序序列是_，层次遍历序列是_,2、二叉树的先序遍历顺序是ABDGEHICE，则该二叉树的根结点是_3、二叉树的后序遍历顺序是GFCDBFIBA，则该二叉树的根结点是_4、树与二叉树之间的转换方法中，树的根结点变成二叉树的_5、树与二叉树之间的转换方法中，树的B结点的右边相邻的兄弟结点是C，在变成二叉树后，C结点是B结点的_结点。6、已知一棵二叉树的中序遍历序列为DBEHAFCIG，

36、后序遍历序列为DHEBFIGCA，该二叉树的前序序列为_，层次遍历序列是_。,三、简答题,1、下述编码哪一组不是前缀码？00，01，10，11，0，1，00，11，0，10，110，111,四、综合题,1、采用顺序存储方法和链接存储方法分别画出下图所示的二叉树的存储结构。并写出该树的前序、中序和后序序列。,2、若二叉树中各结点的值均不相同，则由二叉树的前序序列和中序序列，或由其后序序列和中序序列均能唯一地确定一棵二叉树，但由前序序列和后序序列却不一定能唯一地确定一棵二叉树。（1）已知一棵二叉树的前序序列和中序序列分别为 ABDGHCEFI和GDHBAECIF，请画出此二叉树。（2）已知一棵二叉

37、树的中序序列和后序序列分别为 BDCEAFHG和DECBHGFA，请画出该二叉树。（3）已知两棵二叉树的前序序列和后序序列均为AB和BA，请画出这两棵不同的二叉树。,（b）,3、试画出如下图中两棵二叉树的先根次序、中根次序、后根次序的线索树。,4、对如下图所示的森林：（1）求各树的前序序列和后序序列；（2）求森林的前序序列和后序序列；（3）将此森林转换为相应的二叉树；（4）给出（a）所示树的双亲链表表示、孩子链表表示、带双亲的孩子链表表示及孩子兄弟链表表示等四种存储结构，并指出哪些存储结构易于求指定结点的祖先，哪些易于求指定结点的后代？,5、画出如下图所示的二叉树所对应的森林。,6、假设用于通

38、信的电文由字符集a，b，c，d，e，f，g，h中的字母构成，这8个字母在电文中出现的概率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。（1）为这8个字母设计哈夫曼编码。（2）若用三位二进制数（07）对这个8个字母进行等长编码，则哈夫曼编码的平均码长是等长编码的百分之几？它使电文总长平均压缩多少？,7、设一棵二叉树的中序遍历序列为DGBAECHIF、后序遍历序列 为GDBEIHFCA（1）画出这棵二叉树。（2）画出该二叉树的中序线索二叉树。（3）画出该二叉树对应的森林。,9、对二叉树中的结点进行按层次顺序（每一层自左至右）访问的操作称为二叉树的层次遍历，得到的结点序列称为二叉树的层次序列。现已知一棵二叉树的层次序列为ABCDEFGHIJ，中序序列为DBGEHJACIF，请画出该二叉树。,8、设一棵二叉树的先序遍历序列为ABDFCEGH，中序遍历序列为BFDAGEHC。（1）画出这棵二叉树。（2）画出该二叉树的后序线索二叉树。（3）画出该二叉树对应的森林。,