07 树1.ppt

OS * 数据结构 深圳大学 计算机与软件学院 白鉴聪 * 第六章 树和·二叉树 6.1 树的定义和基本术语 6.2 二叉树 6.3 遍历二叉树和线索二叉树 6.4 树和森林 6.5 树与等价问题 6.6 赫夫曼树及其应用 6.7 回溯法与树的遍历 6.8 树的计数 * 树的定义 树是有n(n≥0)个结点的有限集合。 每个结点都有唯一的直接前驱，但可能有多个后继 6.1 树的定义和二叉树 * 树的定义 如果 n=0，称为空树 如果 n0,称为非空树,对于非空树,有且仅有一个特定的称为根(Root)的节点(无直接前驱) 如果 n1，则除根以外的其它结点划分为 m (m0)个互不相交的有限集 T1, T2 ,…, Tm，其中每个集合本身又是一棵树，并且称为根的子树(SubTree)。 树是可以递归定义的 6.1 树的定义和二叉树 * 树的定义 其中：A是根；其余结点分成三个互不相交的子集 T1={B,E,F,K,L}； T2={C,G}； T3={D,H,I,J,M}, T1,T2,T3都是根A的子树，且本身也是一棵树 6.1 树的定义和二叉树 A 只有根结点的树 A C G B D E F K L H M I J * 树的定义 树状图 广义表形式 嵌套集合 6.1 树的定义和二叉树 A C G B D E F K L H M I J N (a) 嵌套集合形式 (b) 广义表形式 (A(B(E(K,L),F),C(G(M,N)),D(H,I,J) H I J D F B K L E C M N G A * 结构方面的术语 结点：包含一个数据元素及若干指向其子树的分支 分支：结点之间的连接 结点的度：结点拥有的子树数 树的度：树中结点度的最大值称为树的度 叶结点：度为0的结点[没有子树的结点] 分支结点：度不为0的结点[包括根结点]，也称为非终端结点。除根外称为内部结点 6.1 树的定义和二叉树 A C G B D E F K L H M I J * 关系方面的术语 双亲 孩子 兄弟 祖先 子孙 有序树/无序树：孩子的位置是否可以交换 关系：孩子是父亲的质因子，例1/2/5-20，用无序树表示 关系：孩子是父亲的递增质因子，例1/2/5-20，用有序树表示 6.1 树的定义和二叉树 A C G B D E F K L H M I J * 应用方面的术语 层次：根结点为第一层，其孩子为第二层，依此类推 深度：树中结点的最大层次 森林：互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林 6.1 树的定义和二叉树 1层 2层 4层 3层 Height = 4 A C G B D E F K L H M I J A F H B C D G I J E K * 概念练习 已知一颗树如图所示，求 求树的度和深度 树的度为3，深度为5； 求叶子结点和分支结点的数量 叶子结点为5，分支结点为6 求结点H的度 结点H的度为2 求结点B的子孙 结点B的子孙为FG 求结点I的祖先 HDA 6.1 树的定义和二叉树 A B C D F G E H I J K * 二叉树的定义 每个结点最多有２棵子树 二叉树的子树有左右之分 6.2 二叉树 L L R R 空树　　只有根　　只有左子树　 只有右子树　　有左右子树 * 二叉树的性质 在二叉树的第i层上至多有2i-1个结点 深度为k的二叉树至多有2k-1个结点 如果二叉树终端结点数为n0，度为2的结点数为n2，则n0=n2+1 n = n0 +n1+n2 , n = B+1， B= n1+2n2 (B是分支数量) n = n1+2n2+1 n0 +n1+n2 = n1+2n2+1 n0=n2+1 6.2 二叉树 * 满二叉树 一个深度为k且有2k-1个结点的二叉树 每层上的结点数都是最大数、 自上而下、自左至右连续编号 6.2 二叉树 6 2 1 7 5 4 3 8 9 10 11 13 14 15 12 * 完全二叉树 当且仅当每一个结点都与深度相同的满二叉树中编号从1到n的结点一一对应的二叉树 叶子结点只在最大两层上出现，左子树深度与右子树深度相等或大１ 6.2 二叉树 6 2 1 7 5 4 3 8 9 10 11 12 * 完全二叉树 性质4：具有n个结点的完全二叉树,其深度为log2n +1 性质5：在完全二叉树中，结点i的双亲为i/2，结点i的左孩子LCHILD(i)=2i，结点i的右孩子RCHILD(i)=2i+1 6.2 二叉树 6 2 1 7 5 4 3 8 9 10 11 12 2i+2 i 2i+3 2i+1 2i i+1 i/2 * 概念练习 已知一颗完全二叉树第7层有20个结点，则整棵树的结点数 84 在二叉树中，指针p指向的结点是叶子，