61树 树形结构是一类重要的非线性结构,树形结构是结 点之间有分支、分层关系的结构 树的定义:树是n(n20)个结点的有限集。 它满足以下两个条件: (1)有且仅有一个特定的称为根的结点。 (2)其余的结点可分为m个互不相交的有限集合T 其中,每个集合又都是一棵树(子 树) 树的表示
6.1 树 树形结构是一类重要的非线性结构，树形结构是结 点之间有分支、分层关系的结构。 ⚫ 树的定义：树是n(n≥0)个结点的有限集。 它满足以下两个条件： （1）有且仅有一个特定的称为根的结点。 （2）其余的结点可分为m个互不相交的有限集合T1 , T2 ,…,Tm，其中，每个集合又都是一棵树（子 树）。 ⚫ 树的表示
61树 结点的度:一个结点的子树个数称为该结点的度。 树的度:一棵树中结点度的最大值。 叶子(终端结点):度为0的结点。 分支结点(非终端结点):度不为0的结点。 内部结点:除根结点之外的分支结点。 孩子:树中某个结点的子树的根称为个结点的孩子 双亲:该结点则为孩子的双亲 兄弟:同一个双亲的孩子 路径:若树中存在一个结点序列k1k2…k,使得k是k+的双亲 (1≤i<j),称该结点序列是从k到的条路径。 祖先:若树中结点k到k存在一条路径,则称k是ks的祖先 子孙:k是k的子孙
6.1 树 结点的度：一个结点的子树个数称为该结点的度。 树的度：一棵树中结点度的最大值。 叶子（终端结点）：度为0的结点。 分支结点（非终端结点）：度不为0的结点。 内部结点：除根结点之外的分支结点。 孩子：树中某个结点的子树的根称为个结点的孩子。 双亲：该结点则为孩子的双亲。 兄弟：同一个双亲的孩子。 路径：若树中存在一个结点序列k1 ,k2 ,…,kj，使得ki是ki+1的双亲 (1≤i<j)，称该结点序列是从k1到kj的一条路径。 祖先：若树中结点k到ks存在一条路径，则称k是ks的祖先。 子孙：ks是k的子孙
61树 层次:结点的层次是从根开始算起(根为1层) 高度:树中结点的最大层次称为树的高度或深度 有序树:若将树中每个结点的各子树看成是从左到右有 秩序的。 无序树:否则称为无序树。 森林:是m(m0棵互不相交的树的集合 (树形结构的逻辑特征可用树中结点之间的父子关系来描 述)
6.1 树 层次：结点的层次是从根开始算起(根为1层)。 高度：树中结点的最大层次称为树的高度或深度。 有序树：若将树中每个结点的各子树看成是从左到右有 秩序的。 无序树：否则称为无序树。 森林：是m(m≥0)棵互不相交的树的集合。 (树形结构的逻辑特征可用树中结点之间的父子关系来描 述)
61树 树的基本操作有下列几种 (1)初始化操作。 (2)求根函数。 3)求双亲函数 (4)求孩子结点函数 (5)求右兄弟函数 (6)建树函数 7)插入子树操作。 (8)删除子树操作。 (9)遍历操作。 (10)清除结构操作
6.1 树 树的基本操作有下列几种： （1）初始化操作。 （2）求根函数。 （3）求双亲函数。 （4）求孩子结点函数。 （5）求右兄弟函数。 （6）建树函数。 （7）插入子树操作。 （8）删除子树操作。 （9）遍历操作。 （10）清除结构操作
62二叉树 概念 ●性质 ●存储结构 遍历 ●线索化
6.2 二叉树 ⚫ 概念 ⚫ 性质 ⚫ 存储结构 ⚫ 遍历 ⚫ 线索化
62二叉树 概既 定义:二叉树是个结点的有限集,它或者是空集, 或者由一个根结点及两棵不相交的分别称作 这个根的左子树和右子树的二叉树组成。 二叉树的五种基本形态
6.2 二叉树 ⚫ 概念 定义：二叉树是个结点的有限集，它或者是空集， 或者由一个根结点及两棵不相交的分别称作 这个根的左子树和右子树的二叉树组成。 ⚫ 二叉树的五种基本形态
62二叉树 ●二叉树的性质 1、二叉树第层上的结点数目最多为21(i≥0) 归纳法证明 归纳基础:i=1时,有21=20=1。 归纳假设:假设对所有的j(1j<)命题成立,即第层上至多 有21个结点,证明=时命题成立 归纳步骤:根据归纳假设,第ⅰ-1层上至多有22个结点,由于 二叉树的每个结点至多有两个孩子,故第层上的 结点至多是第层上的最大结点数的2倍,=时 该层上至多有2*22=21个结点,故命题成立
6.2 二叉树 ⚫ 二叉树的性质 1、二叉树第i层上的结点数目最多为2 i-1 (i≥0)。 归纳法证明： 归纳基础：i=1时，有2 i-1=20=1。 归纳假设：假设对所有的j(1≤j<i)命题成立，即第j层上至多 有2 j-1个结点，证明j=i时命题成立。 归纳步骤：根据归纳假设，第i-1层上至多有2 i-2个结点，由于 二叉树的每个结点至多有两个孩子，故第i层上的 结点至多是第i层上的最大结点数的2倍，即j=i时 该层上至多有2*2i-2=2i-1个结点，故命题成立
62二叉树 深度为k的二叉树至多有2k1个结点 证明:在具有相同深度的二叉树中,仅当每一层都含有最多结点时, 其树中结点数最多。因此,利用性质1可得,深度为的二叉树 中至多含有的结点数为: 20+21++2k1=2k-1 故命题正确。 3、在任意一棵二叉树中,若终端结点的个数为ηo,度为 的结点数为n2,则no=n2+1。 证明:因为二叉树中所有结点的度数均不大于2,所以结点总数应等 于0度结点数、1度结点数和2度结点数之和,即 n=no+ntn
6.2 二叉树 2、深度为k的二叉树至多有2 k-1个结点。 证明：在具有相同深度的二叉树中，仅当每一层都含有最多结点时， 其树中结点数最多。因此，利用性质1可得，深度为的二叉树 中至多含有的结点数为： 2 0+21+…+2k-1=2k-1 故命题正确。 3、在任意一棵二叉树中，若终端结点的个数为n0，度为 2 的结点数为n2，则n0=n2+1。 证明：因为二叉树中所有结点的度数均不大于2，所以结点总数应等 于0度结点数、1度结点数和2度结点数之和，即： n=n0+n1+n2 ①
62二叉树 另一方面,1度结点有一个孩子,2度结点有两个孩子。所以 二叉树中孩子结点总数是n+2n2,二又树中只有根结点不是任何结点 的孩子,故二又树中的结点总数又可以表示为 n=n1+2n2+1 ② 由式①和式②得到 n=n,+l 两种特殊形式的二叉树 满二叉树:一棵深度为k且有2k1个结点的二叉树。 完全二叉树:若棵二又树至多只有最下面两层上结点的度数可以 小于2,并且最下层上的结点都集中在该层最左边的若 干位置上,则此二叉树称为完全二叉树
6.2 二叉树 另一方面，1度结点有一个孩子，2度结点有两个孩子。所以， 二叉树中孩子结点总数是n1+2n2，二叉树中只有根结点不是任何结点 的孩子，故二叉树中的结点总数又可以表示为： n=n1+2n2+1 ② 由式①和式②得到： n0=n2+1 两种特殊形式的二叉树： 满二叉树：一棵深度为k且有2 k -1个结点的二叉树。 完全二叉树：若一棵二叉树至多只有最下面两层上结点的度数可以 小于2，并且最下层上的结点都集中在该层最左边的若 干位置上，则此二叉树称为完全二叉树
62二叉树 4、具有n个结点的完全二叉树的深度为og2n+1 证明:设所有完全二又树的深度为k,由完全二叉树的定义可知,它 的前k1层是深度为k-1的满二叉树,一共有2k1-1个结点。由 于完全二叉树深度为k,故第k层上还有若干个结点,因此, 该完全二叉树的结点个数n>2k1-1。 另一方面,由性质2可知n≤2k-1,即: 2k-1-1<n≤2k1 由此可推出:2k1≤n<2<1 取对数后有:k1≤log2n<k 因为k为整数,故有k1=log2n由此可得 k= log2n +1
6.2 二叉树 4、具有n个结点的完全二叉树的深度为log2n +1 证明：设所有完全二叉树的深度为k，由完全二叉树的定义可知，它 的前k-1层是深度为k-1的满二叉树，一共有2 k-1-1个结点。由 于完全二叉树深度为k，故第k层上还有若干个结点，因此， 该完全二叉树的结点个数n>2k-1-1。 另一方面，由性质2可知n≤2k-1，即： 2 k-1-1< n ≤2k-1 由此可推出： 2 k-1 ≤ n < 2k-1 取对数后有: k-1 ≤ log2n < k 因为k为整数，故有 k-1= log2n ,由此可得： k= log2n +1