数据结构和算法分析第8章树和二叉树.ppt

第8章 树和二叉树 树型结构是一类非常重要的非线性结构。直观地，树型结构是以分支关系定义的层次结构。 树在计算机领域中也有着广泛的应用，例如在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织信息；在分析算法的行为时，可用树来描述其执行过程等等。 本章将详细讨论树和二叉树数据结构，主要介绍树和二叉树的概念、术语，二叉树的遍历算法。树和二叉树的各种存储结构以及建立在各种存储结构上的操作及应用等。 8.1.2 树的抽象数据类型定义 8.1.3 树的存储结构 8.2 二叉树 8.2.1 二叉树的定义 1 二叉树的定义 二叉树(Binary tree)是n(n≥0)个结点的有限集合。若n=0时称为空树，否则： ⑴ 有且只有一个特殊的称为树的根(Root)结点； ⑵ 若n1时，其余的结点被分成为二个互不相交的子集T1,T2，分别称之为左、右子树，并且左、右子树又都是二叉树。 由此可知，二叉树的定义是递归的。 二叉树在树结构中起着非常重要的作用。因为二叉树结构简单，存储效率高，树的操作算法相对简单，且任何树都很容易转化成二叉树结构。上节中引入的有关树的术语也都适用于二叉树。 2 二叉树的基本形态 二叉树有5种基本形态，如图8-8所示。 8.2.2 二叉树的性质 性质1：在非空二叉树中，第i层上至多有2i-1个结点(i≧1)。 证明：用数学归纳法证明。 当i=1时：只有一个根结点，21-1=20 =1，命题成立。 现假设对i1时，处在第i-1层上至多有2(i-1)-1个结点。 由归纳假设知，第i-1层上至多有2i-2个结点。由于二叉树每个结点的度最大为2，故在第i层上最大结点数为第i-1层上最大结点数的2倍。 即 2×2i-2＝2i-1 证毕 性质2：深度为k的二叉树至多有2k-1个结点（k≧1) 。 证明：深度为k的二叉树的最大的结点数为二叉树中每层上的最大结点数之和。 由性质1知，二叉树的第1层、第2层?第k层上的结点数至多有： 20、21 …2k-1 。 ∴ 总的结点数至多有： 20+21+ …+2k-1=2k-1 证毕 性质3：对任何一棵二叉树，若其叶子结点数为n0，度为2的结点数为n2，则n0=n2+1。 证明：设二叉树中度为1的结点数为n1，二叉树中总结点数为N，因为二叉树中所有结点均小于或等于2，则有：N=n0+n1+n2 再看二叉树中的分支数： 除根结点外，其余每个结点都有唯一的一个进入分支，而所有这些分支都是由度为1和2的结点射出的。设B为二叉树中的分支总数，则有： N=B+1 ∴ B＝n1+2?n2 ∴ N=B+1=n1+2?n2+1 ∴ n0+n1+n2=n1+2?n2+1 即 n0=n2+1 证毕 满二叉树和完全二叉树 一棵深度为k且有2k-1个结点的二叉树称为满二叉树(Full Binary Tree)。 如图8-9(a) 就是一棵深度为4的满二叉树。 满二叉树的特点： ◆ 基本特点是每一层上的结点数总是最大结点数。 ◆ 满二叉树的所有的支结点都有左、右子树。 ◆ 可对满二叉树的结点进行连续编号，若规定从根结点开始，按“自上而下、自左至右”的原则进行。 完全二叉树(Complete Binary Tree)：如果深度为k，由n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1到n的结点一一对应，该二叉树称为完全二叉树。 或深度为k的满二叉树中编号从1到n的前n个结点构成了一棵深度为k的完全二叉树。 其中 2k-1 ≦ n≦2k-1 。 完全二叉树是满二叉树的一部分，而满二叉树是完全二叉树的特例。 完全二叉树的特点： 若完全二叉树的深度为k ，则所有的叶子结点都出现在第k层或k-1层。对于任一结点，如果其右子树的最大层次为l，则其左子树的最大层次为l或l+1。 性质4：n个结点的完全二叉树深度为：?㏒2n? +1。 其中符号： ?x?表示不大于x的最大整数。 ?x? 表示不小于x的最小整数。 证明：假设完全二叉树的深度为k，则根据性质2及完全二叉树的定义有： 2k-1-1n≦2k-1 或 2 k-1≦n2k 取对数得：k－1㏒2nk 因为k是整数。 ∴ k= ?㏒