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

《数据结构《第6章 树和二叉树》.doc》由会员分享，可在线阅读，更多相关《数据结构《第6章 树和二叉树》.doc（39页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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

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

4、3，它们互不相交且为：D1=B,E,F,D2=C,G和D3=D,H,I。树的表示方法还有广义表表示法、集合表示法和凹入表示法等。图6.2分别给出图6.1中所表示的树T的其它三种表示方法。6.1.2树结构中的基本术语（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、J。（4）分

5、支结点（Offshoot-Node）度不为0的结点称为分支结点或非终端结点。例如，树T中，分支结点有A、B、C、D。（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

6、、J的双亲结点。（8）兄弟（Brother）同一个双亲的孩子之间互为兄弟。显然根结点无兄弟，例如，树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，第三层的结点为

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

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

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

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

11、子树为空的二叉树。图6.3所示的就是以上5种二叉树的基本形态。3满二叉树和完全二叉树有关二叉树的基本术语与树完全相同，不再赘述。基于二叉树的特点，此处给出两种特殊形态的二叉树，即满二叉树和完全二叉树的概念。（1）满二叉树(Full Binary Tree) 如果二叉树中的所有分支结点的度数均为2，且叶子结点都在同一层次上，则称此类二叉树为满二叉树。（2）完全二叉树（Complete Binary Tree）对满二叉树T上的所有结点从上到下从左到右从1开始编号，1，2，3，4，。那么，任意一棵二叉树都可以和一棵同深度的满二叉树相对比，假如这棵含有n个结点的二叉树中的每个结点都可以和T中的编号为1

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

13、1层上最多有22i-1=2i=2(i+1)-1个结点成立。性质2 深度为k的二叉树至多有2k-1个结点（k1）。证明：根据性质1的结论可知，深度为k的二叉树至多有20+21+22+2k-1=2k-1个结点。性质3 如果二叉树T的叶结点数为，度为2的结点数为，则。证明：设共有n个结点，其中度为1的结点有个，那么；又因为，结点的总数等于二叉树中总的分支数加1（根结点无分支），即。所以：+=+2+1，即：。性质4 具有n个结点的完全二叉树的深度为。证明：设该完全二叉树的深度为h，那么由性质2和完全二叉树的定义可知，结点数n满足：，即，在不等式两边取以2为底的对数可得：，所以必有：，即。性质5 将具有

14、n个结点的完全二叉树T的结点按层序从上到下，同一层的结点从左到右编号，则对任一个结点i(1in)有：（1）如果i=1，则结点i是T的根结点，无双亲；如果i1，则其双亲结点编号为；（2）如果2in，则结点i为叶子结点；否则结点i的左孩子结点的编号为2i；（3）如果2i+1n，则结点i无右孩子；否则结点i右孩子结点的编号为2i+1。证明：只要能证明（2）、（3）成立，那么可以由此导出结论（1）也成立。以下用归纳法对结论（2）、（3）给出证明。当i=1时，其左孩子结点编号为2=2i，右孩子结点编号为3=2i+1，所以结论成立；假设i=k时结论成立，即其左孩子结点编号为2k，右孩子结点编号为2k+1；

15、以下证明当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)所示，此时如前所述，结论也成立，所以在一般情况下(2),(3)的结论也是成立的。6.2.3二叉树的存储结构1顺序存储结构二叉树的顺序存储结构是，用一组地址连续的存储单元来存放一颗二叉树的所有结点

16、元素。为此，必须将二叉树中的所有结点依照一定的规律安排在数组的存储单元中。具体方法如下：（1）对于完全二叉树，按照至上而下，自左到右的次序存放树中的所有结点元素即可。（2）对于一般二叉树，首先要将其“转化”为完全二叉树，然后再按照完全二叉树的顺序存储方式将每个结点存储在一维数组的相应分量中。其“转化”过程是，在非完全二叉树的所有“残缺”位置上（相对于完全二叉树而言）增设“虚结点”，通常用表示不存在的点。例如：对于图6.6(a)所示的完全二叉树可以顺序存储表示为图6.6(b)。此时，根据性质5可知：对于任意一个结点的序号i(0ilchild,Visit); /先序遍历左子树PreOrder(T-

17、rchild,Visit); /先序遍历右子树2中序遍历的递归算法void InOrder(BiTree T,void(*Visit)(BiTree)if(T)InOrder(T-lchild,Visit); /中序遍历左子树Visit(T); /访问根结点InOrder(T-rchild,Visit); /中序遍历右子树3后序遍历的递归算法void PostOrder(BiTree T,void(*Visit)(BiTree)if(T)PostOrder(T-lchild,Visit); /后序遍历左子树PostOrder(T-rchild,Visit); /后序遍历右子树Visit(T);

18、 /访问根结点函数void PT(BiTree T)的功能是输出（显示）结点T的数据域的值。void PT(BiTree T) coutdata ; /PT(T)为访问结点T的函数函数void PtTree(BiTree T)的作用是分别按先序、中序、后序输出二叉树T的三种遍历序列。void PtTree(BiTree T) /函数PtTree(T)输出二叉树T的三种遍历序列cout先序遍历序列为:n;PreOrder(T,PT);coutn中序遍历序列为:n;InOrder(T,PT);coutn后序遍历序列为:n;PostOrder(T,PT);coute;if(e=*)T=NULL; r

19、eturn; /输入*表示空指针NULLT=new BiTNode; /当e不为零时建立结点TT-data=e;Create_BiT(T-lchild); /通过递归调用建立T的左子树T-lchildCreate_BiT(T-rchild); /通过递归调用建立T的右子树T-rchild先序建立二叉树的演示程序代码如下：void main()BiTree T1,T2;cout先序建立二叉树T1:n;cout输入T1的先序遍历全序列（用*表示NULL）:n; Create_BiT(T1);cout对T1进行遍历:n;PtTree(T1); cout先序建立二叉树T2:n;cout输入T2的先序遍

20、历全序列（用*表示NULL）:n; Create_BiT(T2);coutlchild); /通过递归调用计算左子树的深度h2=1+Depth_BiT(T-rchild); /通过递归调用计算右子树的深度return h1h2? h1:h2;3复制一棵二叉树递归算法函数BiTree CopyTree(BiTree T)的作用是通过二叉树T复制生成另一棵二叉树T1并将其返回。二叉树的复制过程是通过递归调用来完成的。即先复制根结点，再分别复制其左子树和右子树。BiTree CopyTree(BiTree T)BiTree T1;if(!T)T1=NULL;elseT1=new BiTNode; /

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

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

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

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

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

26、-rchild,x); /通过递归调用在T的右子树中完成删除操作9二叉树基本操作演示主函数函数要求按先序遍历全序列来创建二叉树T1。其功能是：1）输出T1的三种遍历序列、深度、叶结点数；2）复制T1到二叉树T2，并输出T2的深度、以及交换T2中所有结点的左右孩子结点后，T2的三种遍历序列和深度，并释放T2的存储空间；3）根据输入的结点值x输出T1中x的所有祖先结点的值；4）删除T1中所有以x为根的子树，并释放空间。void main()void DelSubTree(BiTree &T,EType x);void DelBiTree(BiTree &T);BiTree T1,T2;cout先序

27、建立一棵二叉树:n;Create_BiT(T1);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;EType x;coutx;Ancestor(T1,x);cout销毁T1中所有根为x的子树!n;DelSubTree(T1,x);cout删除

28、后的T1为:n;PtTree(T1);cout销毁二叉树T2:n;DelBiTree(T2);程序运行过程为：先序建立一棵二叉树:ABDG*HJ*K*E*C*F*DM*先序遍历序列为:A B D G H J K E C F D M中序遍历序列为:G D J H K B E A C F M D后序遍历序列为:G J K H D E B M D F C A深度为: 5叶结点的个数为: 5复制后的二叉树为:先序遍历序列为:A B D G H J K E C F D M中序遍历序列为:G D J H K B E A C F M D后序遍历序列为:G J K H D E B M D F C A深度为:

29、5交换后的二叉树T2为:先序遍历序列为:A C F D M B E D H K J G中序遍历序列为:D M F C A E B K H J D G后序遍历序列为:M D F C E K J H G D B A深度为: 5输入结点值x:D结点D的祖先为:B A销毁T1中所有根为D的子树!删除结点：D删除结点：G删除结点：H删除结点：J删除结点：K删除结点：D删除结点：M删除后的T1为:先序遍历序列为:A B E C F中序遍历序列为:B E A C F后序遍历序列为:E B F C A销毁二叉树T2:删除结点：A删除结点：C删除结点：B删除结点：F删除结点：E删除结点：D删除结点：D删除结点：H删除结点：G删除结点：M删除结点：K删除结点：J