济南大学数据结构第6章.doc

第六章 树和二叉树 族谱 树结构是一类重要的非线性结构(层次结构)。 学习重点: 树的基本概念 二叉树的基本概念、相关操作 树和森林与二叉树之间的相互转换 二叉树的应用 6.1 树的定义和基本术语 树(Tree) : 是具有层次结构的 n(n≥0) 个结点的有限集。 树(Tree) : 是 n(n≥0) 个结点的有限集。 n＝0 ，空树 Φ 。 n＝1 ，有且仅有一个称为根的结点的树。 n＞1 ，除根结点外，其余结点可分为 m(m＞0) 个互不相交的有限子集 ，每个子集都称为根结点的子树 。 基本术语: 树的结点包含一个数据元素及若干指向其子树的分支。 结点拥有的分支数（子树数）称为结点的度。 例，A 的度为 3 ，F 的度为 0 。 度为0的结点称为叶子结点或终端结点。 度不为0的结点称为分支结点或非终端结点。 例，K,L,F,G,M,I,J 为叶子；A,B,C,D,E,H 为分支结点 。 除根结点外，其余分支结点又称为内部结点。 例，B,C,D,E,H 为内部结点 。 树的度是指树内各结点的度的最大值。 例，树的度为 3。 结点的子树的根称为该结点的儿子。 该结点称为儿子的父亲。 例，B,C,D 是 A 的儿子，A 是 B,C,D 的父亲。 同一个父亲的儿子之间互称兄弟。 例，B,C,D 互为兄弟。 其父亲在同一层的结点互为堂兄弟。 例，G 与 E,F,H,I,J 互为堂兄弟。 从根到结点所经分支上的所有结点称为该结点的祖先。 例，M 的祖先为 H,D,A。 以某结点为根的子树中的任一结点都称为该结点的子孙。 例，B 的子孙有 E,K,L,F。 结点的层次从根开始定义起，根为第一层，根的儿子为第二层。 例，A 在第一层，B,C,D 在第二层。 树中结点的最大层次称为树的深度或高度。 例，树的深度为 4 。 如果将树中结点的各子树看成从左到右是有序的(即不能互换)，则称该树为有序树，否则称为无序树。 一个有序树，父亲结点的儿子也是从左至右有序的。 例，B,C,D 分别称为 A 的第 1，2，3 个儿子 。 6.2 二叉树 6.2.1 二叉树的定义 二叉树是 n(n≥0) 个结点的有限集，它或者是空集，或者是由一个根和称为左、右子树的两个互不相交的二叉树组成。 二叉树是一个递归定义。 根据定义，二叉树通常具有 5 种基本形态: 6.1 节关于树的基本术语也都适用于二叉树。 树的子树次序不作规定， 树中结点的度没有限制， 二叉树的两个子树有左、右之分。 二叉树中结点的度只能取 0、1、2。 抽象数据类型—二叉树的定义: ADT BinaryTree 数据对象 D : D 是具有相同结构的数据元素的集合。 数据关系 R : D ＝ Φ，则为空二叉树。 D ≠ Φ，则 D ＝ ( root，DL，DR )。 root : 根结点 DL : root 的左子树 DR : root 的右子树 基本操作 P : 6.2.2 二叉树的性质 性质1 : 在二叉树的第 i 层上至多有 2i-1 个结点(i≥1)。 归纳法证明: (1) i = 1 ，只有一个根结点，2i-1 = 20 = 1，正确； (2) 假设 i-1 成立，即第 i-1 层上至多有 2i-2 个结点； (3) 由于二叉树的结点的度至多为 2 ，故在第 i 层上的最大结点数为第 i-1 层上的最大结点数的 2 倍，即2 × 2i-2 = 2i-1 。 性质2 : 深度为 k 的二叉树至多有 2k –1 个结点(k≥1) 。 作业: 归纳法证明。 引论: 一棵树有 n 个结点，则必有 n – 1 条分支。 证明: 除根结点外，其它结点都有一个分支进入， 设 B 为分支总数， 则 B = n - 1 性质3 : 对任何一棵二叉树 T ，如果其终端结点数为 n0，度为 2 的结点数为 n2 ，则 n0 = n2 + 1 。 证明: (1) 已知，终端结点数为 n0 ，度为 2 的结点数为 n2 ， 设度为 1 的结点数为 n1 ， 由于二叉树中的所有结点的度只能为 0、1、2 ， 故二叉树的结点总数为 n = n0 + n1 + n2 ； (2) 除根结点外，其它结点都有一个分支进入， 设 B 为分支总数，故 n = B + 1 ， 由于这些分支均是由度为 1 或 2 的结点发出的， 所以有 B = n1 + 2n2 ，故 n = n1 + 2n2 + 1 ， 由 (1) 和 (2) ，可得 n0 + n1 + n2 = n1 + 2n2 + 1 ， 故有 n0 = n2 + 1 。 两种特殊形态二叉树