第六章树和二叉树.ppt

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

1、数据结构,主讲教师:杨艳霞时间：20102011学年下,第六章 树和二叉树,概述,树型结构是一类重要的非线性结构树是以分支关系定义的层次结构树的应用人类社会的族谱社会组织结构在编译程序中的语法树在数据库系统中，可用树来组织信息,树型结构实例,1家族树,math,ds,zhao,jiang,shao,li,queue,tree,graph,stack,sw,root,bin,lib,user,etc,【2】磁盘目录结构和文件管理系统,内 容,6.1 树的定义和基本术语,1,6.3 遍历二叉树和线索二叉树,2,6.4 树和森林,3,4,6.6 哈夫曼树及其应用,5,6.2 二叉树,6.1 树的定义

2、和基本术语,1.树的一般定义,树(Tree)是n（n=0）个结点的有限集T，T为空时称为空树，否则它满足如下两个条件：有且仅有一个结点没有前驱，称该结点为根结点(Root)；除根结点以外，其余结点可分为m(m0)个互不相交的有限集合T0，Tl，Tm-1。其中每个集合又构成一棵树，树T0，Tl，Tm-1被称为根结点的子树(Subtree)。每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个后继。,例子,A,根,子树,说明,树的结构定义是一个递归定义,即在树的定义中有用到了树的概念，递归是树的固有特性。其它表示形式（含有递归特性）：嵌套集合形式广义表形式凹入表示法,2.树的基本术语,树的结点

3、:包含一个数据元素和指向其子树的所有分支;结点的度:一个结点拥有的子树个数,度为零的结点称为叶结点;树的度:树中所有结点的度的最大值 Max(D(I)含义:树中最大分支数为树的度;,结点的层次及树的深度:根为第一层,根的孩子为第二层,若某结点为第k层,则其孩子为k+1层.树中结点的最大层次称为树的深度或高度.森林:是m(m=0)棵互不相交的树的集合.序树、无序树:如果树中每棵子树从左向右的排列拥有一定的顺序，不得互换，则称为有序树，否则称为无序树。,孩子、双亲:结点子树的根称为这个结点的孩子，而这个结点又被称为孩子的双亲。子孙:以某结点为根的子树中的所有结点都被称为是该结点的子孙。祖先:从根结

4、点到该结点路径上的所有结点。兄弟:同一个双亲的孩子之间互为兄弟。堂兄弟:双亲在同一层的结点互为堂兄弟。,结点A的度：3结点B的度：2结点M的度：0,叶子：K，L，F，G，M，I，J,结点A的孩子：B，C，D结点B的孩子：E，F,结点I的双亲：D结点L的双亲：E,结点B，C，D为兄弟结点K，L为兄弟,树的度：3,结点A的层次：1结点M的层次：4,树的深度：4,结点F，G为堂兄弟结点A是结点F，G的祖先,2、基本术语,6.2 二叉树的相关概念,二叉树在树结构的应用中起着非常重要的作用，因为对二叉树的许多操作算法简单；而任何树都可以与二叉树相互转换，这样就解决了树的存储结构及其运算中存在的复杂性。,

5、1.二叉树的定义,二叉树是由 n(n=0)个结点的有限集合构成；此集合或者为空集（空树）；或者由一个根结点及两棵互不相交的左子树和右子树组成(左、右子树可以为空)，并且左右子树都是二叉树。,这也是一个递归定义。二叉树可以是空集合，根可以有空的左子树或空的右子树。,实例,说明,二叉树和树的区别二叉树是有序树，其子树要区分左子树和右子树，即使只有一棵子树也要进行区分，说明它是左子树，还是右子树。而树一般是指无序树。二叉树的五种基本形态,二叉树的五种基本形态,空二叉树 仅有根结点的二叉树 左右子树均非空的二叉树 右子树为空的二叉树 左子树为空的二叉树,2.二叉树的性质,性质1：在二叉树的第i层上至多

6、有2i-1个结点(i=1),性质2：深度为k的二叉树至多有2k1个结点。,证明（数学归纳法）：（1）当i=1时，只有一个根结点，2i-1=20=1,命题成立。（2）假定对于i-1（i=2）时,命题成立，则第i1层上至多有2i-2个结点。（3）对于第 i 层而言，由于二叉树每个结点的度最大为2，故在第 i 层上最 大结点数为第i1层上最大结点数的二倍，即22i-2 2i-1。,由性质1可知，深度为k的二叉树的最大结点数为：,性质3：对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0n21。,证明：假设二叉树中总的结点数为 n，度为0的结点数为 n0，度为1的结点数为 n1，

7、度为2的结点数为 n2；则有 n n0n1n2。又根据二叉树中的分支数：设B为二叉树中的分支总数。则除根结点外，其余结点都有一个进入分支，则有：n B1。而这些分支都是由度为1和2的结点射出的，故又有：B n1+2*n2。即，nB1n12n21。则有n=n0+n1+n2=n1+2*n2+1，故n0n21。,满二叉树和完全二叉树,满二叉树是深度为k，且有 2k-1 个结点的二叉树。即，满二叉树的每一层上的结点数都是最大结点数。对满二叉树编号：从根结点开始，从上到下，从左至右。,完全二叉树：深度为k且有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称之

8、为完全二叉树。,特点,叶子结点只可能在层次最大的两层上出现；对任一结点，若其右分支下的子孙的最大层次为l，则其左分支下的子孙的最大层次必为l 和 l+1。在满二叉树的最下一层上，从最右边开始连续删除去若干个结点得到的二叉树任然是一棵完全树。,实例,证明：假设深度为k，则根据性质2和完全二叉树的定义有:2k-11n2k-1，或 2k-1 n 2k-1，则有：k-1 log2n k。由于k是整数，则有k=,性质4：具有n个结点的完全二叉树的深度为,性质5 在按层序编号的n个结点的完全二叉树中，任意一结点 i(1in)有：,(1)i=1时，结点i是树的根；否则，结点i的双亲为结点 i/2(i1)。,

9、(2)2in时，结点i无左孩子，为叶结点；否则，结点i的左孩子为结点2i。,(3)2i+1n时，结点i无右孩子；否则，结点i的右孩子为结点2i+1。,3.二叉树的存储结构,顺序存储结构链式存储结构二叉链表三叉链表线索链表,二叉树的顺序存储结构,/=二叉树的顺序存储表示=#define MAX_TREE_SIZE 100 typedef TElemType SqBiTree MAX_TREE_SIZE；/0号单元存储根结点SqBiTree bt；,说明,顺序存储结构是用一组连续的存储单元存储二叉树的数据元素，即要把二叉树这种非线性结构的结点安排成为一个线性的序列，且二叉树结点在这个线性序列中的相

10、互位置能反映出二叉树结点之间的逻辑关系。约定：按照完全二叉树上的编号 i的结点元素存储在如上定义的一维数组中下标为 i-1 的分量中。而对于一般的二叉树，则应将其每个结点与完全二叉树上的结点相对照，存储在一维数组的相应分量中；对于不存的结点，以“0”表示。,例子,顺序存储结构的缺点,很可能对存储空间造成极大的浪费。在最坏的情况下，一个深度为k且只有k个结点的右单支树，需要2k-1个结点存储空间。若经常需要插入与删除树中结点时，顺序存储方式不是很好！,二叉链表和三叉链表,二叉链表,头指针指向根结点,说明：,一个二叉链表由根指针root唯一确定。若二叉树为空，则root=NULL；若结点的某个孩子

11、不存在，则相应的指针为空。具有n个结点的二叉链表中，共有2n个指针域。其中只有n-1个用来指示结点的左、右孩子，其余的n+1个指针域为空。,三叉链表,头指针指向根结点,/=二叉链表的存储表=typedef struct BiTNode TElemType data;struct BiTNode*lchild,*rchild;/左右孩子指针 BiTNode,*BiTree;,/=基本操作的原型=Status CreateBiTree(BiTree,6.3 遍历二叉树和线索二叉树,1.遍历二叉树的含义,遍历二叉树，就是按某条搜索路径访问树中的每一个结点，使得每一个结点均被访问一次，而且仅被访问一次

12、。遍历运算对线性结构是容易解决的，而对于二叉树这样的非线性结构，则需要寻找某种规律，以使二叉树上的结点能排列在一个线性队列上，从而便于遍历。因此，二叉树遍历的问题的本质，就是如何将二叉树的非线性结构按照一定的规则排列成为线性结构。,由二叉树的递归定义，二叉树的三个基本组成单元是：根结点、左子树和右子树。,寻找规律,假如以L、D、R分别表示遍历左子树、遍历根结点和遍历右子树，遍历整个二叉树则有DLR、LDR、LRD、DRL、RDL、RLD六种遍历方案。若规定先左后右，则只有前三种情况：(1)DLR先（根）序遍历；(2)LDR中（根）序遍历；(3)LRD后（根）序遍历。,先根遍历操作,若二叉树为空

13、，则空操作；否则访问根结点；先序遍历左子树；先序遍历右子树。,中根遍历操作,若二叉树为空，则空操作；否则中序遍历左子树；访问根结点；中序遍历右子树。,后根遍历操作,若二叉树为空，则空操作；否则后序遍历左子树；后序遍历右子树；访问根结点。,例子,表达式：a+b*(c-d)-e/f,先序：-+a*b c d/e f,中序：a+b*c d-e/f,后序：a b c d-*+e f/-,这三个式子分别为表达式的前缀表示（波兰式）、中缀表示和后缀表示（逆波兰式）。,先序遍历二叉树的递归算法,Status PreOrderTraverse(BiTree T,Status(*Visit)(TElemType

14、 e)/先序遍历二叉树T的递归算法，采用二叉链表存储结构。/对其中的每个元素调用函数Visit。/最简单的Visit函数是：/Status PrintElement(TElemType e)/输出元素e的值/printf(e);/return OK;/调用实例：PreOrderTraverse(T,PrintElement);1.if(T)2.if(Visit(T-data)3.if(PreOrderTraverse(T-lchild,Visit)4.if(PreOrderTraverse(T-rchild,Visit)5.return Ok;6.return ERROR;/在Visit函数失

15、败的情况下，才会执行此语句。7.else return OK;8.,D L R,先序遍历序列：A B D C,先序遍历:,先序遍历,若二叉树为空树，则空操作；否则，,中序遍历算法,（1）中序遍历左子树；,（2）访问根结点；,（3）中序遍历右子树。,void Inorder(BiTree T，void(*visit)(BiTree)/中序遍历以T为根指针的二叉树 if(T)/T=NULL时，二叉树为空树，不做任何操作Inorder(T-lchild,visit);/中序遍历左子树 visit(T);/通过函数指针*visit 访问根结点 Inorder(T-rchild,visit);/中序遍历

16、右子树/if,L D R,中序遍历序列：B D A C,中序遍历,中序遍历算法,后序遍历算法,若二叉树为空树，则空操作；否则，,（1）后序遍历左子树；,（2）后序遍历右子树；,（3）访问根结点。,void Postorder(BiTree T，void(*visit)(BiTree)/后序遍历以T为根指针的二叉树 if(T)/T=NULL时，二叉树为空树，不做任何操作Postorder(T-lchild,visit);/后序遍历左子树 Postorder(T-rchild,visit);/后序遍历右子树 visit(T);/通过函数指针*visit 访问根结点/if,L R D,后序遍历序列：

17、D B C A,后序遍历:,后序遍历算法,所谓二叉树的层次遍历，是指从二叉树的第一层（根结点）开始，从上至下逐层遍历，在同一层中，则按从左到右的顺序对结点逐个访问。,层次遍历,作业:查资料写出层次遍历的算法.,例如：,先序序列：,中序序列：,后序序列：,A B C D E F G H K,B D C A E H G K F,D C B H K G F E A,层次序列：,A B E C F D G H K,总结:“遍历”是二叉树各种操作的基础，可以在遍历过程中对结点进行各种操作。如：对于一棵已知树可求结点的双亲，求结点的孩子结点，判定结点所在层次等；反之，也可以在遍历过程中生成结点，建立二叉树

18、的存储结构.,线索二叉树,二叉树遍历算法的缺陷：在二叉链表的存储结构下，我们能够直接找到的只有左、右孩子的信息，而无法直接得到结点在任一序列（先、中、后序）中的前驱和后继信息。这种信息只有在遍历的动态过程中才能得到。,解决思路：利用二叉链表中的空闲指针域保存每个结点的前驱、后继信息。并且为结点增加标志域，指明该结点指针域究竟是保存的前驱后继信息，还是保存的左右孩子信息。,线索二叉树,若结点有左子树，则其lchild域指示其左孩子，否则令lchild域指示其前驱；若结点有右子树，则其rchild域指示其右孩子，否则令rchild域指示其后继。为了避免混淆，增加两个标志域LTag和RTag。其中：

19、,lchild域指示结点的左孩子lchild域指示结点的前驱rchild域指示结点的右孩子rchild域指示结点的后继,结点的结构,线索二叉树,以上述结构的结点构成的二叉链表，称为线索链表。其中指向前驱和后继的指针，叫做线索。加上了线索的二叉树称为线索二叉树（Threaded Binary Tree）。对二叉树以某种次序遍历之后，使其变为线索二叉树的过程叫做线索化。,中序线索二叉树,a+b*c d e/f,中序线索链表,在二叉树的线索链表上添加了一个头结点。P134。,对于添加了头结点的线索链表而言，令头结点的lchild域的指针指向二叉树的根结点，其rchild域的指针指向中序遍历时访问的最

20、后一个结点；反之，令二叉树中序序列中的第一个结点的lchild域指针和最后一个结点rchild域的指针均指向头结点。由此就建立了双向线索链表。既可以从第一个结点起顺后继进行遍历，也可以从最后一个结点起顺前驱进行遍历。,/二叉树的二叉线索存储表示typedef enum PointerTag Link,Thread;/Link=0:指针，Thread=1：线索typedef struct BiThrNode TElemType data;struct BiThrNode*lchild,*rchild;/左右孩子指针 PointerTag LTag,RTag;/左右标志BiThrNode,*BiT

21、hrTree;,线索链表的遍历,在序列中找出第一个结点 依次找结点后继，直到其后继为空而止,基本思想：,中序寻找后继结点,树中所有叶子结点的右链都是线索，其右链直接指示其后继。树中所有非终端结点的右链都是指针，无法直接得到其后继?,根据中序遍历的规律，非终端结点的后继，是其右子树遍历的第一个结点，及右子树最左下的结点。,中序线索链表遍历的规则,在中序线索树中找结点后继的规律是：若其右标志为“1”，则右链为线索，指示其后继；否则遍历它的右子树最左下的结点。在中序线索树中找结点前驱的规律是：若其左标志为“1”，则左链为线索，指示其前驱；否则遍历它的左子树最右下的结点。,先序线索链表遍历的规则,若结

22、点x是树中的叶子结点（RTag=1），则其右链都是线索，直接指示其后继。若结点x是树中的非终端结点(Rtag=0），若其左子树存在，直接后继为左孩子；若其左子树不存在，则为右孩子。,后序线索链表遍历的规则（寻找后继）,若结点x是二叉树的根，则其后继为空；若结点x是其双亲的右孩子，或者其双亲的左孩子且双亲没有右孩子，则其后继为双亲结点；若结点x是双亲的左孩子，且其双亲有右子树，则后继为双亲的右子树上按后序遍历列出的第一个结点。若结点x是树中的叶子结点，则其右链都是线索，直接指示其后继。,6.4 树和森林,树的存储结构,三种常用的链表结构：双亲表示法孩子表示法孩子兄弟表示法,1 双亲表示法,一般采

23、用顺序存储结构实现。用一组地址连续的存储单元来存放树的结点，每个结点有两个域：data域-存放结点的信息；parent域-存放该结点双亲结点的位置,双亲表示法,/树的双亲表存储表示#define MAX_TREE_SIZE 100typedef struct PTNode/结点结构 TElemType data;int parent;/双亲位置域PTNode;typedef struct/树结构 PTNode nodesMAX_TREE_SIZE;int r,n;PTree;,双亲表示法的优缺点：求PARENT(T,x)操作可以在常量时间内实现。反复调用PARENT操作，直到遇见无双亲的结点时

24、，就找到了根。这种存储表示在求孩子结点时，需要遍历整个树的结构。,孩子表示法多重链表,同构：树中每个结点除了数据域而外，还有d个域，分别存放结 点的每个孩子结点的位置。其中d是树的度，即树的各个结点的 最大度。这种存储结构的缺点是，浪费存储空间。一棵具有n个 结点的度为k的树中必有n(k-1)+1个空链域。,异构：若树的每个结点除了数据域而外，仅仅存储各自的孩子 结点的位置，则每个结点将是异构的。虽然这样可以节约 存储空间，但是操作麻烦。,2孩子链表表示法,这是树的链式存储结构。每个结点的孩子用单链表存储，称为孩子链表。n个结点可以有n个孩子链表（叶结点的孩子链表为空表）。n个孩子链表的头指针

25、用一个向量表示。,孩子表示法孩子链表,/树的孩子链表存储表示 typedef struct CTNode/孩子结点 int child;struct CTNode*next;*ChildPtr;,typedef struct TElemType data;ChildPtr firstchild;/孩子链表头指针 CTBox;,typedef struct CTBox nodesMAX_TREE_SIZE;int n,r;/结点数和根的位置；CTree;,改进,孩子表示法便于那些涉及孩子的操作的实现，却不适用于PARENT(T,x)操作。,3孩子兄弟链表表示法,孩子兄弟表示法也称为二叉树表示法，

26、或二叉链表表示法。即以二叉链表作为存储结构，链表中结点的左、右两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点，分别命名为firstchild域和nextsibling域。,/树的二叉链表存储表示 typedef struct CSNode ElemType data;struct CSNode*firstchild,*nextsibling;CSNode,*CSTree;,访问结点x的第 i 个孩子，则只要从firstchild域找到第1个孩子结点，然后沿着孩子结点的nextsibling域连续走i-1步，则可以找到第 i 个孩子。如果为每个结点增设一个PARENT域，则同样能方便实现

27、PARENT（T,x）操作。,森林与二叉树的转换,采用孩子兄弟表示法，则给定一棵树，可以找到唯一的一棵二叉树与之对应。任何一棵和树对应的二叉树，其右子树必空。若把森林中第二棵树的根结点看成是第一棵树的根结点的兄弟，则森林和二叉树也有对应关系。,树转换成二叉树,将一棵树转化为等价的二叉树方法如下：在树中各兄弟（堂兄弟除外）之间加一根连线。对于任一结点，只保留它与最左孩子的连线外，删去它与其余孩子之间的连线。以树根为轴心，将整棵树按顺时钟方向旋转约45,树和二叉树的对应,森林和二叉树的对应：,森林和树的遍历,树的遍历：（1）先根遍历：先访问树的根结点，然后依次先根遍历根的每棵子树；（2）后根遍历：

28、先依次后根遍历每棵子树，然后访问根结点。,树的先根序列为：ABCDE树的后根序列为：BDCEA,当以二叉链表作为树的存储结构时，树的先根遍历和后根遍历分别 对应二叉树的先序遍历和中序遍历算法。,森林和树的遍历,森林和树的遍历,森林的遍历：（1）先序遍历森林：若森林非空，则可按下述规则遍历之：,（2）中序遍历森林：若森林非空，则可按下述规则遍历之：,访问森林中第一棵树的根结点；先序遍历第一棵树中根结点的子树森林；先序遍历除去第一树之后剩余的树构成的森林。,中序遍历第一棵树中根结点的子树森林；访问森林中第一棵树的根结点；中序遍历除去第一树之后剩余的树构成的森林。,森林的先序遍历和中序遍历分别对应二

29、叉树的先序和中序遍历。,6.6 赫夫曼树及其应用,基本概念,结点的带权路径长度树的带权路径长度赫夫曼树（最优二叉树）,结点的带权路径长度为从该结点到树根之间路径长度与结点上权 的乘积。树的带权路径长度为树中所有叶子结点的带权路径长度之和，通 常记作,假设有n个权值，试构造一棵有n个叶子结点的 二叉树，每个叶子结点带权为，其中带权路径长度WPL 最小的 二叉树称为最优二叉树，或赫夫曼树。,例子,WPL=72+52+22+42=36WPL=73+53+21+42=46WPL=71+52+23+43=35,赫夫曼树在判定算法上的应用,解某些判定问题，利用赫夫曼树可以得到最佳判定算法,例如，编制一个程

30、序实现从百分制到五级分制的转换。,if(a60)b=“bad”;else if(a70)b=“pass”;else if(a80)b=“general”;else if(a90)b=“good”;else b=“excellent”;,若考虑上述程序所耗费的时间，就会发现该程序的缺陷。在实际中，学生成绩在五个等级上的分布是不均匀的。当学生百分制成绩的录入量很大时，上述判定过程需要反复调用，此时程序的执行效率将成为一个严重问题。假设其分布规律如P145表所示，则80%以上的数据需要进行三次或三次以上的比较，才能得到结果。,a60,不及格,Y,N,a70,及格,Y,N,a80,中等,Y,N,a80

31、,良好,Y,N,良好,中等,Y,N,a80,a70,Y,N,a60,及格,Y,a90,优秀,N,良好,Y,N,不及格,赫夫曼算法,赫夫曼算法：,step1：根据给定的n个权值 构成n棵二叉树的集合 F=T1,T2,Tn，其中每棵二叉树Ti 中只有一个带权为wi 的根结点，其左右子树均空。step2：在 F 中选取两棵根结点的权值最小的树作为左右子树构造一棵新 的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根 结点的权值之和。step3：在 F 中删除这两棵树，同时将新得到的二叉树加入 F 中。step4:重复step2和step3，直到F中只含有一棵树为止。这棵树就是赫 夫曼树。,给定

32、权值集合5，15，40，30，10构造哈夫曼树,1步：,2步：,15,3步：,30,4步：,30,60,5步：,30,60,100,最优的带权路径长度为：WPL(510)415330240205。,赫夫曼编码,通信中的电报编码问题,假设需要传送的电文为A B A C C D A，其中只有四种字符，若要区分这四个字符，只需两位二进制数：A 00,B 01,C 10,D 11。由此，上述七个字符的电文便可译00010010101100，总长度为14位。且对该字符串的解释是唯一的。若对每个字符设计长度不等的编码，且让电文中出现次数较多的字符采用尽可能短的编码，则传送电文的总长便可减少。但是要注意，必

33、须使翻译后的电文能够有唯一的解释。例如，若设计A 0，B 00,C 1,D 01，则上述七个字符的电文可转换成为总长度为9的字符串 000011010。但是对该电文的解释不是唯一的。,采用前缀编码可以解决此问题。所谓前缀编码是指，对于设计长短不等的编码，则必须是任一字符的编码都不是另一个字符编码的前缀。,对于电文“ABACCDA”，采用怎样的前缀码才能使得到的二进制编码最短？,怎样才能得到前缀编码？,利用二叉树来设计二进制的前缀编码。,如右图示，该二叉树中四个叶子结点分别表示A、B、C、D四个字符，且约定左分支是编码0，右分支是编码1，则可以从根结点到叶子结点的路径上分支字符组成的字符串作为该

34、叶子结点字符的编码。,求使电文长度最短的二进制前缀码，即设计赫夫曼树的问题。,若每种字符在电文中出现的次数为w i，其编码长度为l i，电文中只有n个字符，则电文总长度为。,因为前缀编码对应了一棵二叉树，若将每种字符在电文中出现的次数w i 作为叶子结点的权值，l i 则是二叉树中从根到叶子的路径长度。则电文总长度 即是二叉树的带权路径长度。,设计电文总长最短的二进制前缀编码即为以n种字符出现的频率作权，设计一棵赫夫曼树的问题。由此得到的二进制前缀编码称为赫夫曼编码。,例如，设一文本的字符序列是：DATA TRERTER ARE AREA ART，此文本的字符集为A，D，T，R，E，各字符出现

35、的次数为6，1，4，6，4。以此为权值，构造一棵最优二叉树（哈夫曼树），,由二叉树的先序和中序序列建树,先序序列,中序序列,左子树,右子树,根,例题：已知二叉树结点的前序序列为：，中序序列为：，求后序序列,二叉树,后序序列:CEDBGFA,习题：已知二叉树结点的前序序列为：，中序序列为：，求后序序列,作业,1.已知信息为“ABCD BCD CB DB ACB”,请按此信息构造哈夫曼树，求出每一字符的最优编码。2.已知一棵二叉树的中序和后序序列，求该二叉树的高度和双支、单支及叶子结点数。中序：c,b,d,e,a,g,i,h,j,f 后序：c,e,d,b,i,j,h,g,f,a3.一棵度为m的树中，有n1个度为的结点，有n2个度为2的结点,有nm个度为m的结点，则该树的叶子结点数为（）n1+n2+nm(m-1)nm+n2+1 n1+n2+1 n1-n2,4.将下面树转换为二叉树。,