数据结构与算法

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,*,数 据 结 构,（数据结构及其算法）,冯耀霖,Chap 5,树,树的基本概念,二叉树,二叉树遍历,树的存储结构,树结构是元素之间具有分层关系的结构，它类似于自然界中的树，是一种很重要的非线性数据结构。一方面，计算机应用中常出现嵌套的数据，树结构提供了对该类数据的自然表示；另一方面，利用树结构可以有效地解决一些算法问题。因此，树结构有着广泛的应用。树结构常采用递归方式定义，被称为递归数据结构，有关树的许多算法是递归的。,1,树的基本概念,树的定义,基本术语,树的基本操作,1.1 树的定义,层次结构的数据在现实世界中大量存在。例如，一个国家包括若干省，一个省有若干市，每个市管辖若干个县、区。又如，书的内容可以分成章节，章节编号也是有层次的。所有上级和下级、整体和部分、祖先和后裔的关系都是层次关系的例子。,1.树（Tree）的一般定义,树T=(D,R)，其中，D是包含n个结点的有限非空集合，R是D上的关系的集合，R满足以下特性：,(1)有且仅有一个结点rD，不存在任何结点vD，vr，使得R，称r为树的根（root）；,(2)除根之外的所有结点uD，都有且仅有一个结点v，vu，使得R。,(3)树中任一结点xD，都可以有m（m0）个结点y,i,（i0），使得R。,从上述定义可知，树不为空集合，树中至少有一个根结点，根结点没有前驱，其余结点都有唯一的前驱结点，而每个结点又都可以有0或多个后继结点。因此，树形成了层次结构。,2.树的递归定义,树是包含n个结点的有限非空集合T，其中一个特定的结点r称为根，其余结点(T-r)划分成m（m0）个互不相交的子集T,1,T,2,T,m,，其中每一个子集都是树，被称为根r的子树。,图5.1 树的示例,A,A,C,B,D,G,E,F,K,L,H,I,J,M,（a）,（b）,在图5.1中，（a）是只有一个根结点的树；(b)是有13个结点的树，其中A是根，其余结点分成3个互不相交的子集：T1=B,E,F,K,L，T2=C,G，T3=D,H,I,J,M；T1,T2,T3都是根A的子树，且本身也是一棵树。例如T1，其根为B，其余结点分成2个互不相交的子集：T11=E,K,L，T12=F。T11和T12都是B的子树。在T11中，E是根，K和L是E的两棵互不相交的子树，其本身又是只有一个根结点的树。,可以看出，上述两种关于树的定义是完全一致的。,1.2 基本术语,结点,：,树中的每个元素分别对应一个结点，结点包含数据元素值及其逻辑关系信息（后继子树的指针）。,结点的度,：,一结点拥有的子树数目。,树的度,：,树中结点度的最大值。,叶子结点,：,度为0的结点，简称叶子，又称终端结点。,分支结点,：,度大于0的结点，又称非终端结点。,子结点和父结点,：,如果一结点有子树，则子树的根结点称为该结点的子结点，反之，该结点是子结点的父结点。,结点的层次,：,树有明显的层次关系。根结点为第一层，根结点的子结点处于第二层，以此类推。,树的深度,：,树中结点的最大层次，也称树的高度。,兄弟结点,：,同一父结点的结点互为兄弟。,堂兄弟结点,：,在同一层上但父结点不同的结点互为堂兄弟。,祖先结点,：,从根结点到某个结点路径上的所有结点都是该结点的祖先结点。,子孙后裔结点,：,一个结点的所有子树上的任何结点都是该结点的后裔。,路径,：,从某个结点到另一个结点的分支（边）构成这两个结点之间的路径。,有序树,：如果将树中根结点的各子树看成是从左到右有次序的，则称该树是有序树。从左到右，可分别称这些子树为第一子树、第二子树等。,无序树,：如果根结点的各子树之间不存在确定的次序关系，可以交换位置，则称该树是无序树，也就是通常所说的树。,森林,：是树的集合。与现实世界的森林不同，在数据结构中，森林和树只有微小的差别，删去树根，树变成森林，对森林加上一个结点作为树根，森林即成为树。但是需要注意的是，森林可以是空森林，但树不能是空树。,图5.2 树和森林的例子,F,E,B,A,G,C,D,L,M,N,J,X,Y,Z,U,E,F,B,A,D,C,G,J,L,N,M,T,1,T,2,T,3,(a)树T1和T2组成的森林,(b)树T3,在图5.2(a)中，T,1,和T,2,是两棵树，组合在一起成为森林。如果树是无序的，则图5.2(a)中的树T,1,和图5.2(b)中的树T,3,是相同的树，否则它们是不相同的树。在树T1中，结点A、F、和B是结点E的子结点，结点E是A、F、B的父结点，A、F和B互为兄弟。结点E、F、C和L都是结点N的祖先，F的后裔结点有C、L、M、N、D和J。结点E的度为3。根结点E的层次是1，F的层次是2，树T,1,的深度为5，T,2,的深度为3。在树T,1,中，G、M、N、J和B是叶子结点，其余结点是分支结点。,就逻辑结构而言，任何一棵树是一个二元组,Tree=(root,F),，其中，,root,是数据元素，称作树的根结点；,F,是,m（m0）,棵树的森林，,F=(T,1,T,2,T,m,)，,其中,T,i,=(r,i,F,i,),称作根,root,的第,i,棵子树；当,m0,时，在树根和其子树森林之间存在下列关系：,RF=|i=1,2,m,m0,这个定义将有助于得到森林和树与二叉树之间转换的递归定义。,1.3,树的基本操作,InitTree,功能：初始化，构造一棵空树。,DcestroyTree,功能：销毁树,ClearTree,功能：清除树,TreeEmpty,功能：查询是否为空树,TreeDepth,功能：获取树的深度,Root,功能：获取树的根,GetElem,功能：读取指定结点的元素值,SetElem,功能：设置指定结点的元素值,Parent,功能：获取指定结点的父结点,LeftChild,功能：获取指定结点的最左孩子,RightSibling,功能：获取指定结点的右兄弟,InsertChild,功能：插入子树,DeleteChild,功能：删除子树,TraverseTree,功能：树遍历,2,二叉树,二叉树的定义,二叉树的性质,二叉树的存储结构,二叉树的基本操作,二叉树是非常重要的树形结构。很多从实际问题中抽象出来的数据是二叉树形的，二叉树的算法高效且容易实现。并且，一般树或森林都可通过简单的转换得到与之对应的二叉树，从而为一般树或森林的存储和处理提供了有效方法。,2.1,二叉树的定义,二叉树（binary tree）是结点的有限集合，该集合或者为空集，或者是由一个根和两棵互不相交的左子树及右子树所组成。,二叉树的基本形状：,空二叉树,仅有根结点的二叉树,右子树为空的二叉树,左子树为空的二叉树,左右子树均非空的二叉树,二叉树与树之间的差别：,树不能是空树，而二叉树可以是空树；,一般地，树的子树之间是无序的，而二叉树中结点的子树要区分左、右子树，其次序不能颠倒，即使在一棵子树的情况下也要指明是左子树还是右子树；,树中结点的度可以大于2，但二叉树的每个结点最多只有2棵子树（即二叉树中不存在度大于2的结点）。,2.2,二叉树的性质,性质1,：,在二叉树的第i（i1）层上最多有2,i-1,个结点。,可用数学归纳法证明：,当i=1时，二叉树只有一个根结点，结论成立。设当i=k时结论成立，即二叉树的第k层上至多有2,k-1,个结点，则当i=k+1时，因为每个结点最多只有两个子结点，故第k+1层上的结点数最多是第k层上结点数的2倍，即至多有22,k-1,=2,k,个结点。性质成立。,性质2：深度为k（k1）的二叉树上至多有2,k,-1个结点。,证明：当k0时，利用性质1，则深度为k的二叉树上结点的总数最多为：,2,i-1,=2,k,-1,性质,3,：任意一棵二叉树中，若叶子结点的个数为n,0,，度为2的结点的个数为n,2,，则必有n,0,=n,2,+1。,证明：设二叉树的结点总数为n，树中度为1的结点数为n,1,，则有,n=n,0,+n,1,+n,2,(1),由于除根结点没有父结点外，每个结点都有且仅有一个父结点，于是有n-1=n,1,+2n,2,个子结点，即有,n=n,1,+2n,2,+1 (2),将式(2)代入式(1)，便得到n,0,=n,2,+1。结论成立。,性质4：含有n个结点的二叉树的深度至少为,log,2,(n+1)。,证明：由性质2，深度为k的二叉树最多有2,k,-1个结点，因而n2,k,-1，则有klog,2,(n+1)。因为k是整数，所以klog,2,(n+1)。,满二叉树,定义：深度为k的二叉树恰好有2,k,-1个结点时称为满二叉树。或只含度为0和度为2的结点，且度为0的结点只出现在最下层的二叉树称为满二叉树。,完全二叉树,定义：一棵二叉树中，只有最下面两层结点的度可以小于2，并且最下一层的叶子结点集中在靠左的位置上，这样的二叉树称为完全二叉树。,扩充二叉树,定义：扩充二叉树中除叶子结点外，其余结点的度均为2。,图5.3 特殊二叉树,(a)完全二叉树,(b)扩充二叉树,图5.3 特殊二叉树,1,4,3,2,5,6,7,8,9,10,11,12,13,14,15,1,2,3,3,4,5,8,9,10,11,6,7,12,(b)完全二叉树,(a)满二叉树,1,2,3,4,6,7,1,2,3,4,5,5,6,(c)扩充二叉树,(d)非完全二叉树,性质5：具有n个结点的完全二叉树的深度为log,2,(n+1)。,证明：设完全二叉树的深度为k，则除最下层外，前k-1层形成满二叉树，总共有2,k-1,-1个结点；而最下层，即第k层的结点个数最多不超过2,k-1,个，因此有,2,k-1,-1n2,k,-1,移项得2,k-1,n+12,k,取对数得k-1log,2,(n+1)k,因k是整数，故k是不小于log,2,(n+1)的最小整数。,性质6,：若对含n个结点的完全二叉树，按照从上到下、从左至右的次序进行1n的编号，对其中任意一个编号为i的结点，有以下关系：,(1)若i=1，则结点i是二叉树的根；若i1，则结点i/2为结点i的父结点；,(2)若2in，则结点i无左子树，否则（2in）结点2i为左子树；,(3)若2i+1n，则结点i无右子树，否则（2i+1n）结点2i+1为右子树；,Its Over,