上节内容回顾 树的基本概念 二叉树的基本概念和性质 两种特殊的二叉树
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层是满的，但最底层却允许在右边缺少连续若干个结点。 满二叉树是完全二叉树的一个特例