上节内容回顾 树的基本概念 二叉树的基本概念和性质 两种特殊的二叉树
1 上节内容回顾 ➢树的基本概念 ➢二叉树的基本概念和性质 ➢两种特殊的二叉树
问题1:什么是二叉树?简述树和二叉树的不同点。 答 (1)树 (2)二叉树 (3)二叉树 二叉树是由n(n≥0)个结点的有限集合构成,此集合或 者为空集,或者由一个根结点及两棵互不相交的左右子树组 成,并且左右子树都是二叉树。 树与二叉树是两类不同的树型结构。树中并没有限定每 个子树的位置,通常是无序的,即使在有序树中,也只是限 定了各子树之间的相次序,而没有限定子树所在的位置;而 叉树的每个结点至多有两个子树,且每个结的子树有严格 的左、右位置
2 问题1：什么是二叉树？简述树和二叉树的不同点。 答： (1)树 (2)二叉树 (3)二叉树 二叉树是由n(n≥0)个结点的有限集合构成，此集合或 者为空集，或者由一个根结点及两棵互不相交的左右子树组 成，并且左右子树都是二叉树。 树与二叉树是两类不同的树型结构。树中并没有限定每 个子树的位置，通常是无序的，即使在有序树中，也只是限 定了各子树之间的相次序，而没有限定子树所在的位置；而 二叉树的每个结点至多有两个子树，且每个结的子树有严格 的左、右位置。 a b c d a b c a b e f d
问题2:二叉树的性质? 答:性质1:在一棵非空二叉树的第i层上至多有21个结点(i≥0) 性质2:深度为k的二叉树至多有2+1-1个结点(k≥-1)。 性质3:对于任何一棵非空的二叉树,若度为2的结点数有n2个, 则叶子数(n0)必定为n2+1(即n0=n2+1) 性质4:具有n个结点的完全二叉树的深度k必为1og2(n+1)11 性质5:对于一棵有n个结点的完全二叉树的结点按照从上至下 和从左至右的顺序对所有结点从0开始顺序编号,则对于序号为 i的结点(0≤i≤n),有 (1)如果i=0,则结点i无双亲,是二叉树的根;如果i>0,则 其双亲是结点(i-1)/2(/表示整除)。 左孩乎是结量1则结点1为叶子结点,无左孩子;否则,其 点2果2+2≥2m,则结点1无右孩子:否则,其右孩子是结
3 问题2：二叉树的性质？ 答：性质1:在一棵非空二叉树的第i层上至多有2 i个结点（i≥0）。 性质2:深度为k的二叉树至多有2 k+1-1个结点(k≥-1)。 性质3: 对于任何一棵非空的二叉树，若度为2的结点数有n2个， 则叶子数（n0）必定为n2＋1 （即n0=n2+1） 性质4: 具有n个结点的完全二叉树的深度k必为log2(n+1)-1 性质5:对于一棵有n个结点的完全二叉树的结点按照从上至下 和从左至右的顺序对所有结点从0开始顺序编号,则对于序号为 i的结点(0≤i≤n),有： (1)如果i=0，则结点i无双亲，是二叉树的根；如果i>0，则 其双亲是结点(i-1)/2(“/”表示整除）。 (2)如果2i+1≥n，则结点i为叶子结点，无左孩子；否则，其 左孩子是结点2i+1。 (3)如果2i＋2≥n，则结点i无右孩子；否则，其右孩子是结 点2i＋2
问题3:什么是两种特殊形态的二叉树?它们的区别? 答:满二叉树与完全二叉树。 在一棵二叉树中,如果所有分支结点都 存在左子树和右子树,并且所有叶子结点都 在同一层上,这样的二叉树称为满二叉树。 如果一棵深度为k,有n个结点的二叉树 中各结点能够与深度为k的顺序编号的满二叉 树从1到n标号的结点相对应的二叉树称为完 全二叉树。其特点: (1)所有的叶结点都出现在第k层或k-1层。(4 (2)若任一结点,如果其右子树的最大层次为i, 则其左子树的最大层次为i或i+1
4 问题3：什么是两种特殊形态的二叉树？它们的区别？ 答：满二叉树与完全二叉树。 在一棵二叉树中，如果所有分支结点都 存在左子树和右子树，并且所有叶子结点都 在同一层上，这样的二叉树称为满二叉树。 如果一棵深度为k，有n个结点的二叉树 中各结点能够与深度为k的顺序编号的满二叉 树从1到n标号的结点相对应的二叉树称为完 全二叉树。其特点: (1)所有的叶结点都出现在第k层或k－1层。 (2)若任一结点，如果其右子树的最大层次为i， 则其左子树的最大层次为i或i＋1。 a b d c e f g 1 2 3 4 5 6
满二叉树与完全二叉树的区别是: 满二叉树是叶子一个也不少的树,而完全二叉树虽然前 k-1层是满的,但最底层却允许在右边缺少连续若千个结点 满二叉树是完全二叉树的一个特例
5 满二叉树与完全二叉树的区别是： 满二叉树是叶子一个也不少的树，而完全二叉树虽然前 k-1层是满的，但最底层却允许在右边缺少连续若干个结点。 满二叉树是完全二叉树的一个特例
问题4、对于任何一棵非空的二叉树,若度为2的结点数有 n2个,叶子数n0必定为n2+1。试证明此结论是正确的。 证明:∵二叉树中全部结点数n=no+n1+n2 (叶子数+1度结点数+2度结点数=全部结点数 又:二叉树中全部结点数n=B+1(总分支数+根结点) (除根结点外,每个结点必有一个直接前趋,即一个分支) 而总分支数B=n1+n2(1度结点必有1个直接后继,2度结点必 有2个) 由此可得:mo+n1+2=n1+2n2+1,即no=2+1
6 问题4、对于任何一棵非空的二叉树，若度为2的结点数有 n2个，叶子数n0必定为n2＋1。试证明此结论是正确的。 证明：∵ 二叉树中全部结点数n＝n0+n1+n2 (叶子数＋1度结点数＋2度结点数=全部结点数) 又∵二叉树中全部结点数n＝B+1 ( 总分支数＋根结点 ) （除根结点外，每个结点必有一个直接前趋，即一个分支） 而 总分支数B= n1+2n2 (1度结点必有1个直接后继，2度结点必 有2个) 由此可得： n0+n1+n2= n1+2n2 +1, 即n0=n2+1
问题5、针对二叉树,回答下列问题: (1)具有n个结点的非空二叉树的最小深度是多少?最 大深度是多少? (2)具有n个结点的完全二叉树中有多少个叶子结点? 有多少个度为2的结点? (3)具有n个叶子结点的完全二叉树中共有多少个结 点? 答:(1)其最小深度是1og2(n+1)+1,最大深度是n (2)具有n个结点的完全二叉树中有n/2叶子结点, 有n/211个度为2的结点 (3)具有n个叶子结点的完全二叉树中共有2n0 个结点或2n0-1个结点
7 问题5、针对二叉树，回答下列问题： (1)具有n个结点的非空二叉树的最小深度是多少？最 大深度是多少？ （2）具有n个结点的完全二叉树中有多少个叶子结点？ 有多少个度为2的结点？ （3）具有n0个叶子结点的完全二叉树中共有多少个结 点？ 答:(1)其最小深度是log2(n+1)-1，最大深度是n。 (2)具有n个结点的完全二叉树中有n/2叶子结点， 有n/2-1个度为2的结点。 （3）具有n0个叶子结点的完全二叉树中共有2n0 个结点或2n0-1个结点
练习: 棵完全二叉树有1000个结点,则它必有 叶子结点,有个度为2的结点,有个结点只 有非空左子树,有个结点只有非空右子树 正确答案 全部叶子数=1000/2=500个。 度为2的结点=叶子总数-1=499个。 因为最后一个结点坐标是偶数,所以必为左子树。有1 个结点只有非空左子树,有0个结点只有非空右 子树
8 一棵完全二叉树有1000个结点，则它必有 个 叶子结点，有 个度为2的结点，有 个结点只 有非空左子树，有 个结点只有非空右子树。 练习： 正确答案： 全部叶子数＝1000/2 =500个。 度为2的结点＝叶子总数－1=499个。 因为最后一个结点坐标是偶数，所以必为左子树。有 1 个结点只有非空左子树，有 0 个结点只有非空右 子树
7.3二叉树的设计和实现 7.3.1二叉树的顺序存储结构 二叉树的存储结构主要有三种:顺序存储结构、链式存储 结构和仿真指针存储结构 叉树的顺序存储结构 完全二叉树的结点可按从上至下和从左至右的次序存储在 维数组中,其结点之间的关系可由公式计算得到,这就是二 叉树的顺序存储结构。图7-4在数组中的存储结构为: 数组 a bcde fg 下标0123456
9 7.3 二叉树的设计和实现 7.3.1 二叉树的顺序存储结构 二叉树的存储结构主要有三种：顺序存储结构、链式存储 结构和仿真指针存储结构。 1. 二叉树的顺序存储结构 完全二叉树的结点可按从上至下和从左至右的次序存储在 一维数组中，其结点之间的关系可由公式计算得到，这就是二 叉树的顺序存储结构。图7-4在数组中的存储结构为： 数组 下标 0 1 2 3 4 5 6 a b c d e f g
问题:对于一般的二叉树如何存储呢? 显然不能直接使用二叉树的顺序存储结构。我们可以采取 下面这种办法:首先在非完全二叉树中增添一些并不存在的空结 点使之变成完全二叉树的形态,然后再用顺序存储结构存储。 00600⊙ 数组LAB ICADEAAAFAAG 下标0123456789101112(c) (a)一般二叉树(b)完全二叉树(c)在数组中的存储形式 图7.6一般二叉树的顺序存储结构
10 问题：对于一般的二叉树如何存储呢？ 显然不能直接使用二叉树的顺序存储结构。我们可以采取 下面这种办法：首先在非完全二叉树中增添一些并不存在的空结 点使之变成完全二叉树的形态，然后再用顺序存储结构存储。 数组 下标 0 1 2 3 4 5 6 7 8 9 10 11 12 (c) (a)一般二叉树 (b)完全二叉树 （c)在数组中的存储形式 图7.6 一般二叉树的顺序存储结构 A B C Λ D E Λ Λ Λ F Λ Λ G