数据结构ppt(第6章 树和二叉树).pptVIP

第6章 树和二叉树;6.1 树的定义和基本术语;T = { A，B，C，D，E，F，G，H，I，J，K，L，M} A是根，其余结点可以划分为3个互不相交的集合： T1= { B，E，F，K，L } T2 ={ C，G } T3 ={ D，H，I，J，M } 这些集合中的每一集合都本身又是一棵树，它们是A的子树。 对于T1，B是根，其余结点可以划分为2个互不相交的集合： T11 ={ E，K，L } T12 ={ F } T11，T12是B的子树。;1. 树中只有根结点没有前趋；2. 除根外，其余结点都有且仅一个前趋； 3. 树的结点，可以有零个或多个后继；4. 除根外的其它结点，都存在唯一条从 根到该结点的路径； 5. 树是一种分支结构。; 树可表示具有分支结构关系的对象 例1. 家族族谱 设某家庭有13个成员A、B、C、D、E、F、G、H、I、J、K、L、M，他们之间的关系可如图所示的树表示。 例2. 单位行政机构的组织关系; 树是常用的数据组织形式 有些应用中数据元素之间并不存在分支结构关系，但是为了便于管理和使用数据，将它们用树的形式来组织。例3. 计算机的文件系统 不论是DOS文件系统还是window文件系统，所有的文件是用树的形式来组织的。 ;树的结点：包含一个数据元素的 内容及若干指向子树的分支。 孩子结点：结点的子树的根称为 该结点的孩子；如E是B的孩子。 双亲结点：B结点是A结点的孩子， 则A结点是B结点的双亲；如B是E的双亲。 兄弟结点：同一双亲的孩子结点；如H、I、J互为兄弟。 堂兄结点：同一层上结点；如G与E、F、H、I、J互为堂兄。 祖先结点：结点的祖先是从根到该结点所经分支上的所有结点； 如H的祖先为A、D。 子孙结点：以某结点为根的子树中的任一结点称为该结点的子孙；如A的子孙为B、C、D、E、F、G、H、I、J、K、L、M。;结点的度：结点子树的个数； 如D的度为3。 叶子结点：也叫终端结点，是 度为0的结点；如K、L、F、G 、M、I、J。 分支结点：度不为0的结点；如A、B、C、D 结点层次：根结点的层定义为1，根的孩子为第二层结点，依此类推。 树的高度：树中结点的最大层次；如图所示树的高度为4。 树的度： 树中各结点的度的最大值；如图所示树的度为3。 森林：m(m=0)棵互不相交的??的集合；; 线性结构 第一个数据元素 （无前驱）； 最后一个数据元素（无后继）； 其它数据元素（一个前驱、一个后继）。 树型结构 根结点（无前驱）； 多个叶子结点 （无后继）； 其它数据元素（一个前驱、多个后继）。;6.2.1 二叉树的定义 或为空树，或由根及至多两棵互不相交的左子树、右子树构成(即不存在度大于2的结点)，并且左、右子树本身也是二叉树。 说明： 1. 二叉树中每个结点最多有两棵子 树，二叉树每个结点度小于等于2； 2. 左、右子树不能颠倒——有序树； 3. 二叉树是递归结构，在二叉树的定 义中又用到了二叉树的概念。;;性质1 在二叉树的第 i 层上至多有 2i - 1个结点。(i ≥ 1) [证明用归纳法] 证明：当i=1时，只有根结点，2 i-1=2 0=1。 假设对所有j， 1≤j﹤i，命题成立，即第j层上至多有2 j-1 个结点。 由归纳假设第i-1 层上至多有 2i -2个结点。 由于二叉树的每个结点的度至多为2，故在第i层上的最大结点数为第i-1层上的最大结点数的2倍，即2×2i -2= 2 i-1。 ;性质2 深度为 k 的二叉树至多有 2 k-1个结点(k ≥1)。 证明：由性质1可见，深度为k的二叉树的最大结点数为 ;性质3 对任何一棵二叉树T，如果其叶结点数为 n0，度为2的结点数为 n2，则n0＝n2＋1。 证明：设二叉树中度为1的结点数为n1，二叉树中总结点数为： n＝n0＋n1＋n2 二叉树中的分支数，除根结点外，其余结点都有一个进入分支，设B为二叉树中的分支总数， 则有：n＝B＋1。 由于这些分支都是由度为1和2的结点射出的，所以有： B＝n1+2 × n2 ; n＝B＋1＝n1＋2×n2＋1 得到：n0＝n2＋1;满二叉树：深度为k的二叉树，有2k-1个结点则称为满二叉树； 完全二叉树：如果深度为k、由n个结点的二叉树中个结点能够与深度为k的顺序编号的满二叉树从1到n标号的结点相对应，则称为完全二叉树。 完全二叉树的特点是： 1. 所有的叶结点都出现在第k层或k－1层。 2. 对任一结点，如果其右子树的最大层次为l ，则其左子树的最大层次为 l 或 l ＋1。;6;性质 4 ：具有 n 个结点的完全二叉树的深度为