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