数据结构《第6章树和二叉树》

1、页眉内容第6章树和二叉树本章学习要点熟悉树的递归定义、相关术语以及基本概念熟悉二叉树的递归定义、二叉树的有关术语以及基本概念掌握二叉树的基本性质以及相应的证明方法了解二叉树的两种存储结构、各种存储方法的特点和适用范围熟练掌握二叉树的各种遍历算法，能通过应用二叉树的遍历操作实现二叉树的其它基本操作了解线索二叉树的实质和目的，掌握在中序线索化的二叉树中，查找给定结点的前驱和后继的方法掌握树、森林与二叉树之间的关系和转换方法掌握树的各种存储结构的特点、适应范围以及树和森林的遍历算法树型结构是一种应用非常广泛的非线性结构，其中以二叉树最为常用。树型结构反映了元素之间的层次关系和分支关系，它非常类似于自

2、然界中的树。树型结构在计算机领域中广泛应用。比如，在计算机操作系统中对文件的目录管理就是采用树型结构；在编译程序中，使用树来表示程序的语法结构；在数据库系统中，树型结构也是信息的重要组织形式之一。本章将详细讨论二叉树的逻辑结构、各种存储结构及其基本操作的实现，研究树、森林和二叉树之间的转换关系，最后介绍一个二叉树的应用实例Huffman树及其应用。6.1树的定义和基本术语机T(Tree)是n(n=0)个数据元素(结点)的有限集合D,如果D为空集，则称T为空树；否则有下面的定义：(1)在D中有且仅有一个特定的结点，称为根结点；(2)当n1时，其余的结点可分成m(m0)个互不相交的有限集：Ti,T

3、2,Tm,期中每个集合又都是一棵树，并称它们为树T的根结点的子树。树是以递归的方式来定义的，即在叙述树的定义的过程中又用到了树的概念。树的这种递归定义方式反映了树型结构的层次特性。直观地讲，树是由根结点和若干棵子树组成，其中的每棵子树又都是由一个根结点和它自己的若干棵子树组成，依此类推。例如，图6.1是用图形表示法表示的一棵树T。根据树的定义，T的数据元素集合D中一共包含有10个结点：D=ABC,D,E,F,G,H,I,J，其中结点A为T的根结点。根结点A有三棵子树万213,子树的根结点分别为B、C、D均为A的孩子结点，每棵子树中所含数据元素的集合分别为Di、Q、D3,它们互不相交且为：Di=

4、B,E,F,D2=C,G和D3=D,H,I。13树的表示方法还有广义表表示法、集合表示法和凹入表示法等。图6.2分别给出图6.1中所表示的树T的其它三种表示方法。树1隼合表示注(1)结点(Node)树的结点包含一个数据元素以及若干个指向其子树的分支指针。(2)结点的度(Degree)结点所拥有的子树个数称为该结点的度。例如，在图6.1所示的树T中，度为零的结点有E、F、G、H、I、J,度为1的结点有C,度为2的结点有B,度为3的结点有A、B。(3)叶子结点(Leaf)度为0的结点称为叶结点或终端结点。例如，树T中，其叶结点为E、F、G、H、I、Jo(4)分支结点(Offshoot-Node)度

5、不为。的结点称为分支结点或非终端结点。例如，树T中，分支结点有A、B、C、Do(5)树的度(Tree-Degree)树内各结点的度的最大值称为该树的度。例如，树T的度等于3。（6）孩子（Child）结点的子树的根称为该结点的孩子。显然叶结点无孩子，例如，树T中，根结点A的孩子结点有B、C、D，结点B的孩子结点有E、F,结点C的孩子结点为G,结点D的孩子结点有H、I、J。（7）双亲（Parents）结点称为该结点的所有子树的根的双亲。显然根结点无双亲，例如，树T中，根结点A为B、C、D的双亲结点，结点B为E、F的双亲结点，结点C为G的双亲结点，结点D为H、I、J的双亲结点。（8）兄弟（Broth

6、er）同一个双亲的孩子之间互为兄弟。显然根结点无兄弟，例如，树T中，结点B、C、D为兄弟结点，结点H、I、J为兄弟结点，（9）祖先（Ancestor）从根到该结点所经分支上的所有结点均为该结点的祖先。例如，树T中，结点E的祖先有A、B。（10）子孙（Offspring）以某结点为根的树中的任一个结点都是该结点的子孙。在非空树中所有结点（根结点除外）均为其根结点的子孙。（11）层次（Level）从根开始定义起，根为第一层，根的孩子为第二层，若某结点在第m层，则其子树的根就在第m+1层。例如，在树T中，第一层的结点为A，第二层的结点为B、C、D，第三层的结点为E、F、G、H、I、J。（12）堂兄弟

7、（Brother-in-low）双亲在同一层的结点互为堂兄弟。例如，在树T中，结点E、G、H为堂兄弟。（13）树的深度（Tree-Degree）树中结点的最大层数称为该树的深度。显然树的深度等于该树中叶结点的最大层数。（14）有序树与无序树如果将树中结点的各子树看成从左到右是有次序的（即不能互换），则称该树是有序树，否则称为无序树（本章所讨论的树均为有序树）。（15）森林（Forest）森林是m（m=0）棵互不相交的树的集合。说明：在一棵树中，双亲结点与其孩子结点的关系即为前驱与后继的关系，可以写成。显然，树的根结点无前驱结点，而树的叶子结点无后继结点。例如，图6.1所表示的树T中，所有结点的

8、逻辑结构可以表示为：,树的基本操作主要有：（1）InitTree（&T）构造一棵空树T；(2)DestroyTree(&T)若树T非空，则收回T所占的内存资源； 3) 3)CreateTree(&T,definition)根据definition构造树T； 4) 4)TreeEmpty(T)判断树T是否为空树； 5) 5)TreeDepth(T)返回树T的深度； 6) Value(T,cur_e)返回树T中结点cur_e的值； 7) 7)Assign(&T,cur_e,value)置T中结点cur_e的值为value； 8) Parent(T,cur_e)返回T中结点cur_e的双亲结点； 9

9、) InsertChild(&T,&p,i,e)子树e插入到T中p所指的结点中，p的度数+1,使其成为p结点的第i棵子树(T与e不交)； 10) 10)DeleteChild(&T,&p,i)删除T中p所指结点的第i棵子树；(11)TraverseTree(T)按照某种次序对树T的每个结点进行一次且仅有一次的访问。6.2二叉树二叉树(BineryTree)是一种重要的树型结构，许多实际问题抽象出来的数据结构往往是二叉树的形式。与树的结构相比，二叉树在结构上更规范和更具有确定性，而且操作比较简单。一般的树和森林都可以转换为二叉树，因此，本章主要讨论二叉树的性质、存储结构、基本操作的实现以及二叉树

10、的应用。1 二叉树的定义二叉树T(BinaryTree)是n(n)0)个数据元素(结点)的有限集合，当n=0时称T为空二叉树,简称为空树，当n0时存在唯一的称为根的结点，且其余元素分成互不相交的两个子集，每个子集自身也是一棵二叉树，分别称为T的左子树和右子树。显然，二叉树是一种特殊的树型结构，二叉树的度最多为2，且二叉树的子树有左右之分，其次序不能颠倒。2 二叉树的五种基本形态二叉树有5种基本形态，它们分别是：(1) 空二叉树(2)仅有根结点的二叉树(3)只有左子树而右子树为空的二叉树(4)左子树和右子树都不为空的二叉树(5)有右子树而左子树为空的二叉树。图6.3所示的就是以上5种二叉树的基本

11、形态。S)仅有左子树 的二义村空二叉树3)仅有根结点 的二支树S)仅有方子树弟一歹捌E6.3二型.柄的五种基本形态3 .满二叉树和完全二叉树有关二叉树的基本术语与树完全相同，不再赘述。基于二叉树的特点，此处给出两种特殊形态的二叉树，即满二叉树和完全二叉树的概念。(1)满二叉树(FullBinaryTree)如果二叉树中的所有分支结点的度数均为2,且叶子结点都在同一层次上，则称此类二叉树为满二叉树。(2)完全二叉树(CompleteBinaryTree)对满二叉树T上的所有结点从上到下从左到右从1开始编号，1,2,3,4。那么，任意一棵二叉树都可以和一棵同深度的满二叉树相对比，假如这棵含有n个结

12、点的二叉树中的每个结点都可以和T中的编号为1至n的结点对应，则称该二叉树为完6.4(a)为一棵满二叉全二叉树。显然，满二叉树本身也一定是一棵完全二叉树，反之不然。例如，图树，而图6.4(b)为一棵完全二叉树。囤6 4芮二叉树与完全二夏桐面一出树全二叉树由二叉树的定义可知，二叉树具有以下5个重要性质。性质1在二叉机勺第i层上最多有2i1个结点。证明：(利用归纳法证明此性质)当i=1时，由于该层上最多只有一个根结点，所以第1层最多有2i-1=20=1个结点；假设第i层上最多有2i-1个结点成立，下面来证明在第i+1层上最多有2=2。+1)-1个结点成立：由于二叉树的度为2,所以每个结点最多有两个孩

13、子，根据归纳的假设，在第i层最多有2i-1个结点，所以在第i+1层上最多有zxzi-JzZzQ+D-1个结点成立。性质2深度为k的二叉树至多有2k-1个结点(k1)。证明：根据性质1的结论可知，深度为k的二叉树至多有20+21+22+2k-1=2k-1个结点。性质3如果二叉树T的叶结点数为n0,度为2的结点数为n2，则n0n21。证明：设共有n个结点，其中度为1的结点有n1个，那么nn0n1n2；又因为，结点的总数等于二叉树中总的分支数加1(根结点无分支)，即n0n01nl2n21o所以：n0+n1+n2=n1+2n2+1,即：n0n21。性质4具有n个结点的完全二叉树的深度为log2n1。证

14、明：设该完全二叉树的深度为h,那么由性质2和完全二叉树的定义可知，结点数n满足：2h1n2h1,即2h1n2h,在不等式两边取以2为底的对数可得：h1log2nh,所以必有：log2nh1,即hlog2n1。性质5将具有n个结点的完全二叉树T的结点按层序从上到下，同一层的结点从左到右编号，则对任一个结点i(1&i1,则其双亲结点编号为|_2；(2)如果2Xin,则结点i为叶子结点；否则结点i的左孩子结点的编号为2i;(3)如果2Xi+1n,则结点i无右孩子；否则结点i右孩子结点的编号为2i+1。证明：只要能证明(2)、(3)成立，那么可以由此导出结论(1)也成立。以下用归纳法对结论(2)、(3

15、)给出证明。当i=1时，其左孩子结点编号为2=2i,右孩子结点编号为3=2i+1,所以结论成立；假设i=k时结论成立，即其左孩子结点编号为2k,右孩子结点编号为2k+1;以下证明当i=k+1时结论也成立：根据归纳的假设，由完全二叉树的特点以及编号的顺序可知，当第k个和第k+1个结点在同一层时其结构如图6.5(a)所示，第k+1个结点的左孩子结点编号为2k+2=2(k+1)=2i,右孩子结点编号为2k+3=2(k+1)+1=2i+1结论成立；当第k个和第k+1个结点不在同一层时，第k个必为上一层的最右一个结点，而第k+1个结点必为下一层最左一个结点，其结构如图6.5(b)所示，此时如前所述，结论

16、也成立，所以在一般情况下(2),(3)的结论也是成立的。me.5完生二叉树中结点i和结点i*i的左右珠子1 .顺序存储结构二叉树的顺序存储结构是，用一组地址连续的存储单元来存放一颗二叉树的所有结点元素。为此,必须将二叉树中的所有结点依照一定的规律安排在数组的存储单元中。具体方法如下：(1)对于完全二叉树，按照至上而下，自左到右的次序存放树中的所有结点元素即可。(2)对于一般二叉树，首先要将其转化”为完全二叉树，然后再按照完全二叉树的顺序存储方式将每个结点存储在一维数组的相应分量中。其转化”过程是，在非完全二叉树的所有残缺”位置上(相对于完全二叉树而言)增设虚结点“，通常用犊示不存在的点。例如：

17、对于图6.6(a)所示的完全二叉树可以顺序存储表示为图6.6(b)。此时，根据性质5可知：对于任意一个结点的序号i(0ilchild,Visit);先序遍历左子树PreOrder(T-rchild,Visit);先序遍历右子树2 .中序遍历的递归算法voidInOrder(BiTreeT,void(*Visit)(BiTree)if(T)InOrder(T-lchild,Visit);中序遍历左子树Visit(T);/访问根结点InOrder(T-rchild,Visit);中序遍历右子树3 .后序遍历的递归算法voidPostOrder(BiTreeT,void(*Visit)(BiTree

18、)if(T)PostOrder(T-lchild,Visit);/后序遍历左子树PostOrder(T-rchild,Visit);后序遍历右子树Visit(T);/访问根结点函数voidPT(BiTreeT)的功能是输出(显示)结点T的数据域的值。voidPT(BiTreeT)coutdata;/PT(T)为访问结点T的函数T的三种遍历序列。函数voidPtTree(BiTreeT)的作用是分别按先序、中序、后序输出二叉树voidPtTree(BiTreeT)/函数PtTree(T)输出二叉树T的三种遍历序列cout先序遍历序列为:n;PreOrder(T,PT);coutn中序遍历序列为：

19、n;InOrder(T,PT);coutn后序遍历序列为:n;PostOrder(T,PT);coute;if(e=*)T=NULL;return;/输入嚷示空指针NULLT=newBiTNode;当e不为零时建立结点TT-data=e;Create_BiT(T-lchild);/通过递归调用建立T的左子树T-lchildCreate_BiT(T-rchild);/通过递归调用建立T的右子树T-rchild先序建立二叉树的演示程序代码如下：voidmain()BiTree T1,T2;cout”先序建立二叉树 T1:n;cout输入T1的先序遍历全序列(用Create_BiT(T1);cout

20、对T1进行遍历:n;PtTree(T1);cout”先序建立二叉树 T2:n;cout输入T2的先序遍历全序列(用Create_BiT(T2);coutlchild);/通过递归调用计算左子树的深度h2=1+Depth_BiT(T-rchild);/通过递归调用计算右子树的深度returnh1h2?h1:h2;3 .复制一棵二叉树递归算法函数BiTreeCopyTree(BiTreeT)的作用是通过二叉树T复制生成另一棵二叉树T1并将其返回。叉树的复制过程是通过递归调用来完成的。即先复制根结点，再分别复制其左子树和右子树。BiTreeCopyTree(BiTreeT)BiTreeT1;if(!

21、T)T1=NULL;elseT1=newBiTNode;/建立新树的根结点T1T1-data=T-data;T1-lchild=CopyTree(T-lchild);/通过递归用复制T的左子树到T1的左子树中T1-rchild=CopyTree(T-rchild);/通过递归用复制T的右子树到T1的右子树中returnT1;4 交换一棵二叉树中所有结点的左孩子和右孩子函数voidChange(BiTree&T)的功能是交换二叉树T的所有结点的左右孩子。函数的实现过程是通过递归调用来完成的。即先交换根结点的左右孩子，再分别交换根结点的左孩子和右孩子结点的左右孩子。voidChange(BiTre

22、e&T)BiTreett;if(T)tt=T-lchild;T-lchild=T-rchild;T-rchild=tt;Change(T-lchild);/通过递归调用交换左子树中根结点的左右孩子Change(T-rchild);/通过递归调用交换右子树中根结点的左右孩子5 求二叉树的所有叶结点的个数操作intLeaf_BiT(BiTreeT)的功能是返回二叉树T中所有叶结点的个数。函数的实现过程是通过递归调用来完成的。即分别计算根结点的左子树叶结点和右子树叶结点，最后返回其和值。intLeaf_BiT(BiTreeT)intnum;if(!T)num=0;/空树的叶结点数为0elseif(!

23、T-lchild&!T-rchild)num=1;/只有根结点的树的叶结点数为1elsenum=Leaf_BiT(T-lchild)+Leaf_BiT(T-rchild);/通过递归调用计算其左右子树的叶子结点数returnnum;6 求结点x的双亲结点Parent函数BiTreeParent(BiTreeT,ETypex)的作用是返回二叉树T中结点值为x的结点的双亲结点的首地址。其结点的寻访顺序是按先序遍历的顺序进行的，如果查找失败返回NULL。显然，该操作的实现过程是通过递归调用来完成的。BiTreeParent(BiTreeT,ETypex)BiTreep;if(!T|T-data=x)

24、p=NULL;/树的根结点T无双亲结点elseif(T-lchild&T-lchild-data=x|T-rchild&T-rchild-data=x)p=T;/如果T的左孩子或右孩子结点值为x则返回Telseif(!(p=Parent(T-lchild,x)/如果在左子树中递归差找不成功p=Parent(T-rchild,x);/在右子树中递归查找return(p);7 求一个结点x的所有祖先结点Ancestor操作voidAncestor(BiTreeT,ETypex)的功能是输出二叉树T中值为x的结点的所有祖先结点的值。函数的实现过程是通过多次调用函数BiTreeParent(BiTre

25、eT,ETypex)，从其双亲结点开始输出，逐步上升到根结点。voidAncestor(BiTreeT,ETypex)BiTreep;cout结点xdata;coutx;coutlchild)/如果有左孩子则左孩子入队Qr+=t-lchild;r%=n;if(t-rchild)/如果有右孩子则右孩子入队Qr+=t-rchild;r%=n;cout删除结点：datadata=x)/如果x为根结点则删除整棵树DelBiTree(T);return;elseDelSubTree(T-lchild,x);/通过递归调用在T的左子树中完成删除操作DelSubTree(T-rchild,x);通过递归调用

26、在T的右子树中完成删除操作9 .二叉树基本操作演示主函数函数要求按先序遍历全序列来创建二叉树T1。其功能是:1)输出T1的三种遍历序列、深度、叶结点数；2)复制T1到二叉树T2,并输出T2的深度、以及交换T2中所有结点的左右孩子结点后，T2的三种遍历序列和深度，并释放T2的存储空间；3)根据输入的结点值x输出T1中x的所有祖先结点的值;4)删除T1中所有以x为根的子树，并释放空间。voidmain()voidDelSubTree(BiTree&T,ETypex);voidDelBiTree(BiTree&T);BiTreeT1,T2;cout先序建立一棵二叉树：n;Create_BiT(T1)

27、;PtTree(T1);cout深度为:Depth_BiT(T1)endl;cout叶结点的个数为：Leaf_BiT(T1)endl;T2=CopyTree(T1);cout”复制后的二叉树为：n;PtTree(T2);cout深度为:Depth_BiT(T2)endl;Change(T2);cout”交换后的二叉树T2为:n;PtTree(T2);cout深度为:Depth_BiT(T2)endl;ETypex;coutx;Ancestor(T1,x);cout销毁T1中所有根为x的子树！n;DelSubTree(T1,x);cout删除后的T1为:n;PtTree(T1);coutlchi

28、ld,T2-lchild);like2=LikeTree(Ti-rchild,T2-rchild);return(likei*like2);【例6.5】编写递归算法，输出在二叉树的先序遍历序列中第k个位置上的结点的值。解：本题的算法思想是，通过先序遍历二叉树的递归调用方法，在执行过程中每访问一次结点前先执行操作“k-;”一次，并判断k的值是否为0。如果在某次访问结点时k的值为0,那么该结点即为所求结点，输出该结点的值结束操作。算法实现如下：voidPreOrder_k(BiTreeT,int&k)由于在函数调用过程中的参数k为值传递是单向的，所以此处的参数k应定义为引用参数&koif(T)k-

29、;if(k=0)coutdatalchild,k);PreOrder_k(T-rchild,k);【例6.6】编写按层次顺序遍历一棵二叉树T的算法TraverseLevel(T)。解：按层次遍历二叉树的过程是，由根结点开始，按照从上到下从左到右的次序依次访问树中的每一个结点。为此，先建立一个初始仅有根结点的队列Q，每次提取一个队首元素，并在访问该结点的值后将其左、右孩子结点(如果存在)依次入队，直至队列为空为止。其程序实现过程如下：voidTraverseLevel(BiTreeT)intf=0,r=0,n=100;/r为队尾指针,f为队首指针，n为最大队列长度BiTreeQ100,t;/Q为

30、存放树T中结点的队列if(!(Qr+=T)return;while(f!=r)t=Qf+;f%=n;/t出队coutdatalchild)/如果t有左孩子则左孩子入队Qr+=t-lchild;r%=n;if(t-rchild)/如果t有右孩子则右孩子入队Qr+=t-rchild;r%=n;coutlchild&!T-rchild)return1;Qr+=T;while(r!=f)&(!leaf)t=Qf+;f%=n;if(t-lchild&t-rchild)/结点t的度为2时继续Qr+=t-lchild;r%=n;Qr+=t-rchild;r%=n;elseif(t-lchild)/结点t的度

31、为1且仅有左孩子时以后均为叶结点Qr+=t-lchild;r%=n;leaf=1;elseif(t-rchild)/结点t的度为1时不能有右孩子结点h=0;break;elseleaf=1;/结点t的度为0时以后结点的度均为0while(h&(f!=r)/在剩下的结点中均为叶结点t=Qf+;f%=n;if(t-lchild|t-rchild)h=0;returnh;【例6.8】设计算法，通过由顺序表存储的完全二叉树STn建立该完全二叉树的二叉链表结构T。解：本问题的算法思想是，通过递归调用的方法来逐步完成对二叉树T中各个结点的建立操作。即先建立根结点，再依次建立根结点的左子树根结点和右子树的根

32、结点，直至完成所有结点的建立。算法实现如下：voidTreeSqToL(BiTree&T,ETypeST,intn,inti=1)/i为根结点的序号，n为结点总数if(in)T=NULL;return;elseT=newBiTNode;T-data=STi-1;TreeSqToL(T-lchild,ST,n,i*2);TreeSqToL(T-rchild,ST,n,i*2+1);【例6.9】设计一个算法，由二叉树T的先序遍历序列preoder口和中序遍历序列inoder口来构造二叉树T。解：根据二叉树的递归定义和遍历过程可知，在先序遍历序列preoder中的第一个数据元素必为树的根结点，根结点

33、后面的前一部分为其左子树的先序遍历序列，后一部分为其右子树的先序遍历序列；在中序遍历序列inoder中，根结点前面的元素序列为其左子树的中序遍历序列，而在根结点后面的元素序列为其右子树的中序遍历序列。所以本问题可以采用递归调用的方法，先建立根结点，再分别建立根结点的左子树和右子树。算法实现代码如下：BiTreeBiTreeCreate(EType*preoder,EType*inoder,intn)/preoder为先序首地址，inoder为中序首地址，n为结点总数BiTreeT;intk;EType*p;if(ndata=*preoder;/建立根结点for(p=inoder;plchild

34、=BiTreeCreate(preoder+1,inoder,k);/建立左子树T-rchild=BiTreeCreate(preoder+k+1,p+1,n-1-k);/建立右子树returnT;【例6.10】编写通过中序遍历序列Inn和层次遍历序列Levn建立一棵由二叉链表存储的二叉树的程序代码。voidInLev_Create(EType*In,EType*Lev,intn,BiTree&T)BiTreep,q,*Q;inti,f=0,r=0,k=1;/f,r分别为队列Q的头、尾指针，k指向Levn中第二个元素Q=newBiTreen;T=newBiTNode;/建立树的根结点TT-da

35、ta=*Lev;T-lchild=T-rchild=NULL;Qr+=T;/建立一个初始只有根结点T的队列Qwhile(r!=f)/当队列Q不空时继续p=Qf+;f%=n;for(i=0;idata)break;/查找p-data在Inn中的下标值iIni=A;将Inn中访问过的元素Ini设置为if(i0&Ini-1!=w)建立结点p的左子树qq=newBiTNode;p-lchild=q;q-data=Levk+;q-lchild=q-rchild=NULL;Qr+=q;r%=n;if(irchild=q;q-data=Levk+;q-lchild=q-rchild=NULL;Qr+=q;r

36、%=n;deleteQ;演示主程序代码该程序的主要功能是，通过调用前面给出的各种算法完成以下操作：(1)判断两棵二叉树T1和T2是否为相似二叉树；(2)查找位于先序序列中第k个位置的结点的值；(3)按层次顺序遍历一棵二叉树T1；(4)判断一棵二叉树是否为完全二叉树；(5)由顺序表存储的完全二叉树STn建立二叉链表T；(6)由二叉树的先序和中序序列构造该二叉树的二叉链表存储结构。voidmain()ETypest100,pre100,in100;BiTreeT1,T2;intnum,k,n,i;while(1)cout1-判断两棵二叉树T1和T2是否为相似二叉树n;cout2-求位于先序序列中第k个位置的结点的值.n;cout3-按层次顺序遍历一棵二叉树T1n;cout4-判断一棵二叉树是否为完全二叉树.n;cout5-由顺序表存储的完全二叉树STn建立二叉链表Ton;cout6-由二叉树的先序和中序序列构造二叉树.n;coutnum;switch(num)case 1:cout先序建立一棵二叉树T1:n;Create_BiT(T1);cout”先序建立一棵二叉树T2:n;Create_BiT(T2)