数据结构-清华大学-殷人昆-04.pptVIP

第4章 树与二叉树 清华大学计算机系 殷人昆 第 4 章 树与二叉树 树和森林的概念 树的定义 树是由n (n＞0) 个结点组成的有限集合： 有一个特定的称之为根(root)的结点； 除根以外的其它结点划分为 m (m≥0) 个 互不相交的有限集合T1, T2, …, Tm，每个集合又是一棵树，并且称之为根的子树。 此定义是离散数学和图论中给出的。它们把树视为图的一个极小连通子图。有 n 个结点的树有 n-1 条边，而且不能有回路。 这种观点的典型代表是 Knuth。他认为图至少有一个顶点，树也必须至少有一个顶点。树不能是空树，但 N 叉树可以是空树。N 叉树是限制根的子树最多不能超过 N 棵的树。 随着对树讨论的深入，人们放宽了对树结构的限制。若把树当作层次结构单独对待，树中允许结点个数为0。这样，树与N叉树就没有不可逾越的鸿沟了。 从面向对象观点，N叉树是树的特殊实现：树是父类，N叉树是子类。N叉树继承了树的特性，它还有自己增加的特性，例如 理论上树不可是空树，N叉树可以是空树； 树的子树可以有序，也可以不要求有序，而N叉树的子树必须有序。 N叉树的定义也是递归的，递归到空树终止；树则递归到只有一个结点的子树。 树的子树棵数不限，而N叉树中根的子树最多N棵。 树可以区分为外向树和内向树，而N叉树一般是外向树，即边是有向的，从父指向子。 树可以用N叉树实现。二叉树、B树等又都是N叉树的特殊情形。 树的特点 树是分层结构，又是递归结构。每棵子树的根结点有且仅有一个直接前驱，但可以有 0 个或多个直接后继。 注意，结点的深度和结点的高度是不同的。结点的深度即结点所处层次，是从根向下逐层计算的；结点的高度是从下向上逐层计算的：叶结点的高度为1, 其他结点的高度是取它的所有子女结点最大高度加一。 树的深度与高度相等。 树的深度按离根最远的 叶结点算，树的高度按 根结点算，都是6。 叶结点也称为终端结点， 非叶结点也称为非终端 结点。 二叉树 (Binary Tree) 二叉树的定义 一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。 这个定义是递归的。 二叉树的性质 性质1 若二叉树的层次从 1 开始, 则在二叉树的第 i 层最多有 2i-1 个结点。( i≥1) [证明用数学归纳法] i = 1时，根结点只有1个，21-1 = 20 =1； 若设 i = k 时性质成立，即该层最多有 2k-1 个结点，则当 i = k+1 时，由于第 k 层每个结点最多可有 2 个子女，第 k+1 层最多结点个数可有 2*2k-1 = 2k 个，故性质成立。 性质2 高度为 h 的二叉树最多有 2h -1个结点。(h≥1) [证明用求等比级数前k项和的公式] 高度为 h 的二叉树有 h 层，各层最多结点个数相加，得到等比级数，求和得： 20 + 21 + 22 + … + 2h-1 = 2h-1 空树的高度为 0，只有根结点的树的高度为 1。 性质3 对任何一棵二叉树, 如果其叶结点有 n0 个, 度为2的非叶结点有 n2 个, 则有 n0＝n2＋1 证明： 若设度为 1 的结点有 n1 个，总结点个数为 n，总边数为 e，则根据二叉树的定义， n = n0+n1+n2 e = 2n2+n1 = n-1 因此，有 2n2+n1 = n0+n1+n2-1 n2 = n0-1 n0 = n2+1 引申：可用于判断二叉树各类结点个数。 定义1 满二叉树 (Full Binary Tree) 定义2 完全二叉树 (Complete Binary Tree) 若设二叉树的高度为 h，则共有 h 层。除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层从右向左连续缺若干结点，这就是完全二叉树。 性质4 具有 n (n≥0) 个结点的完全二叉树的高度为 ?log2(n+1)? 证明：设完全二叉树的高度为 h，则有 2h-1-1＜n ≤ 2h-1 上面h-1层结点数 包括第h层的最大结点数 变形 2h-1＜n+1≤2h 取对数 h-1＜log2(n+1)≤h 有 h = ?log2(n+1)? 注意： 求高度的另一公式为 ?log2n? +1, 此公式对于 n = 0 不适用。 若设完全二叉树中叶结点有 n0 个, 则该二叉树总的结点数为 n = 2n0, 或 n = 2n0 –1。 若完全二叉树的结点数为奇数，没有度为1的结