六章 树ppt课件.pptVIP

第六章 树 树的概念和基本术语 树——由n (n ? 0)个结点组成的有限集合。 如果n = 0，称为空树； 如果n 0，则 有一个特定的称之为根(root)的结点，它只有直接后继，但没有直接前驱； 除根以外的其它结点划分为m (m ? 0)个互不相交的有限集合T0, T1, …, Tm-1，每个集合又是一棵树，并且称之为根的子树(subTree)。 每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。 树的表示 树型表示 a是根； T1,T2都是根a的子树，且本身也是一棵树 T1={b,d,e,f,i,j}； T2={c,g,h}； 凹入表表示 嵌套集合表示 嵌套括号表示 a ( b ( d, e ( i, j ), f ), c ( g, h ) ) 树的基本术语 结点(node) 结点的度(degree) 结点的子树个数 分支(branch)结点 度不为0的结点 叶(leaf)结点 度为0的结点 子女(child)结点 某结点子树的根结点 双亲(parent)结点 某个结点是其子树之根的双亲 兄弟(sibling)结点 具有同一双亲的所有结点 祖先(ancestor)结点 若树中结点k到ks存在一条路径，则称k是ks的祖先 子孙(descendant)结点 若树中结点k到ks存在一条路径，则称ks是k的子孙 结点所处层次(level) 根结点的层数为1，其余结点的层数为双亲结点的层数加1 树的高度(depth) 树中结点的最大层数 有序树 树中结点的子树由左向右有序，子树的次序不能互换 无序树 子树的次序可以互换 森林 m(m ? 0)棵互不相交的树的集合 对树中每个结点而言，其子树的集合即为森林 树的基本操作 初始化 求指定结点所在树的根结点 求指定结点的双亲结点 求指定结点的某一孩子结点 求指定结点的最右边兄弟结点 将一棵树插入到另一树的指定结点下作为它的子树 删除指定结点的某一子树 树的遍历 二叉树 (Binary Tree) 二叉树的定义 一棵二叉树是n（n≥0）个结点的一个有限集合，该集合或者为空(n=0)，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。(递归定义：用二叉树定义二叉树) 二叉树的每个结点至多只有两棵子树（二叉树中不存在度大于2的结点） 在二叉树中，子树是有顺序的，下面两棵二叉树是不同的。 思考：画出由三个结点所能组成的所有二叉树。 二叉树的性质 性质1 若二叉树的层次从1开始, 则在二叉树的第 i 层最多有 2i-1 个结点。(i ? 1) 证明： i = 1 时，有2i-1 = 20 =1，成立 假定 ：i = k 时性质成立，即第k层最多有2k-1个结点； 当 i = k+1 时，由于二叉树的每个结点的度至多为2，故在第i层上的最大结点数为第i-1层上的最大结点数的2倍，第k+1的结点至多是第k层结点的两倍，即总的结点个数至多为2×2k-1 = 2k 性质2 高度为k的二叉树最多有2k － 1个结点。(k ? 1) 证明：仅当每一层都含有最大结点数时，二叉树的结点数最多，利用性质1可得二叉树的结点数至多为： 20 + 21 + 22 + 23 + … + 2k-1 = 2k － 1 性质3 对任何一棵二叉树, 如果其度为0的叶结点个数为n0, 度为2的非叶结点个数为 n2, 则有n0＝n2＋1 证明： 1、结点总数n=度为0的结点数＋度为1的结点数＋度为2的结点：n = n0 + n1 + n2 2、另一方面，二叉树中一度结点有一个孩子，二度结点有二个孩子，根结点不是任何结点的孩子，因此，结点总数为：n = n1 + 2n2 + 1 3、两式相减，得到：n0 = n2 + 1 特殊形态的二叉树 满二叉树 (Full Binary Tree) 一棵深度为k且有2k -1个结点的二叉树 完全二叉树(Complete Binary Tree) 若设二叉树的高度为h。除第h层外，其它各层的结点数都达到最大个数，第h层从右向左连续缺若干结点，这就是完全二叉树。 性质4 具有 n (n ? 0) 个结点的完全二叉树的深度为?log2n ?＋1 证明： 设完全二叉树的深度为 h，则根据性质2和完全二叉树的定义有 2h-1 - 1 n ? 2h – 1 ，即 2h-1 ? n 2h 取对数 h-1 ? log2n h，又h是整数， 因此有 h = ?log2n ? ＋1 性质5 如果将一棵有n个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号1, 2, …, n-1,n，然后按此结点编号将树中各结点顺序地存放于一个一维数组中, 并简称编号为i的结点为结点i (1 ? i ? n)。 则有以下