贵州民族学院数据结构课件 第七章.ppt

第七章 树形结构的概念 第七章 树形结构的概念 树是一类重要的非线性数据结构，是以分支关系定义的层次结构 7.1 树的概念 7.2 二叉的树概念 7.3 树的二叉树表示 7.4 周游树形结构 7.1 树的概念 1. 定义 树(tree)是n(n≥0)个结点的有限集，如果 n = 0，则为空树；如果 n 0，则 有且仅有一个特定的结点，称为树的根(root) 当n1时，除根以外的其他结点又可分为m(m0)个互不相交的有限集T1,T2,…,Tm，其中每一个集合本身又是一棵树，称为根的子树(subtree) 2、树的逻辑结构 包含n个结点的有穷集合K (n0)，且在K上定义了一个关系N，关系N满足以下条件： 有且仅有一个根结点k0∈K，对于关系N来说它没有前驱。 除结点k0外，K中的每个结点对于关系N来说都有且仅有一个前驱 除结点k0外的任何结点k∈K，都存在一个结点序列k0，k1…，ks，使得k0就是树根，且ks=k，其中有序对ki-1 ， ki∈N (1≤i≤s) 这样的结点序列称为从根到结点k的一条路径 3.基本术语 结点(node)——树中的数据元素 边(edge)——结点k，k’的有序对k, k’，称为它们的边 结点的度(degree)——结点拥有的子树棵数 树叶 (leaf)——度为0的结点，也称终端结点 分支结点(branch)——度非0的结点，也称非终端结点 (儿)子结点 (child)——某结点子树的根称为该结点的儿子，也称孩子 双亲(parents)——某结点的直接前趋结点，也称父结点。一个结点的父结点是唯一的 兄弟(sibling)——同一双亲的子结点 祖先——某结点同一分支上的所有上层结点 子孙——以某结点为根的子树中的任一结点称为该结点的子孙 结点的层次(level)——从根结点算起，根为1层，它的孩子为2层，…… 树的度——一棵树中最大的结点度数 结点的层次(level)——从根结点算起，根为1层，它的孩子为2层，··· ··· 深度(depth)——树中结点的最大层次数 森林(树林 forest)——r(r≥0)棵互不相交的树的集合 由森林的概念及树的逻辑关系，我们可给出树的另一定义： 任何一棵树是一个二元组 Tree=(root,F) 其中：root是数据元素，称作树的根； F是m(m≥0)棵树的森林： F=(T1,T2, ··· ,Tm) 其中，Ti=(ri,Fi)称作根root的第i棵子树； 当m≠0时，在树根和其子树森林之间存在如下关系： RF={root, ri|i=1,2, ··· ,m, m0} 7.2 二叉树的概念 7.2.1 二叉树的定义 1.定义 二叉树是n(n≥0)个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成 3. 二叉树的特点 每个结点至多有二棵子树(即不存在度大于2的结点) 二叉树的子树有左、右之分，且其次序不能任意颠倒 7.2.1 二叉树性质 性质1：在二叉树的第i层上至多有2i-1个结点(i≥1) 证明：用归纳法证明之 ? i=1时，只有一个根结点，2i-1 = 20=1是对的 ?假设对所有j(1≤ji)命题成立，即第j层上至多有2j-1个结点，那么， 第i-1层至多有个 2(i-1)-1= 2i-2结点 又二叉树每个结点的度至多为2 ∴ 第i层上最大结点数是第i-1层的2倍，即　 2·2i-2 = 2i-1 故命题得证 性质2：深度为k的二叉树至多有2k-1个结点(k≥1) [证明用求等比级数前k项和的公式] 证明：由性质1，可得深度为k 的二叉树最大结点数是 =20 + 21 + 22 + … + 2k-1=2k -1 两种特殊的二叉树 满二叉树 定义 一棵深度为k且有2k-1结点的二叉树 特点 每一层上的结点数都是最大结点数 （所有结点或为叶结点，或为2度结点） 例 完全二叉树 定义 深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号（按层次从左至右）从1至n的结点一一对应时，则称该二叉树为完全二叉树 特点 叶子结点