了(3)只有右子树,无左子树的二又树 (4)既有左子树,又有右子树的二又树 (5)无结点的空树。 图55二又树的回种基本形态
武汉理工大学华夏学院-信息工程 系 图5-5 二叉树的四种基本形态 （3）只有右子树，无左子树的二叉树． （4） 既有左子树，又有右子树的二叉树． （5）无结点的空树
二.二叉树的性质 性质1.在二叉树的第i层上,最多有21个 结点。(请思考,为什么?) 性质2.在高度为h(h>0)的二叉树中,结 点总数最多有2h-1个结点。 原因:由性质1,把每层结点加起来即可。 性质3在非空二叉树中,叶结点的个数比度 为2的结点个数多1个。为什么? 武汉理工大学华夏学院-信息工程 系
武汉理工大学华夏学院-信息工程 系 二. 二叉树的性质 性质１．在二叉树的第ｉ层上，最多有２i-1 个 结点。（请思考，为什么？） 性质２．在高度为ｈ（ｈ>0 ）的二叉树中，结 点总数最多有2h -1个结点。 原因：由性质１，把每层结点加起来即可。 性质３．在非空二叉树中，叶结点的个数比度 为2的结点个数多１个。为什么？
证明 设二叉树中结点的总数为n,度为0,1,2的结 点个数分别为no,n1,n2 则有n=no+n1+n2 (1) 另外,又从二叉树的边数来看,可以知道:每一棵 树除根结点外的其余结点都有一条边与其双亲结点相连, ≥则n个结点应有n-1条边,这n-1条边是由分支结点产 生 的,共有:度为1的结点为n个,产生的边的条数为n1 条;度为2的结点为n2个,产生的边的条数为2n2条 ●这样,有n-1=n1+2n2 武汉理工大学华夏学院-信息工程 由(1)(2)两式变换可得和=n2+1(证毕)
武汉理工大学华夏学院-信息工程 系 证明： 设二叉树中结点的总数为ｎ，度为０，１，２的结 点个数分别为ｎ0，ｎ1，ｎ2， 则有ｎ＝ｎ0 +n1+n2 ……………(1) 另外，又从二叉树的边数来看，可以知道：每一棵 树除根结点外的其余结点都有一条边与其双亲结点相连， 则n 个结点应有n-1条边，这n-1条边是由分支结点产 生 的，共有：度为1的结点为n1个，产生的边的条数为n1 条；度为2的结点为n2个，产生的边的条数为2n2条； 这样，有 n -1=n1+2n2 …………(2) 由（1),(2）两式变换可得 n0=n2 + 1 (证毕）
三.满二叉树与完全二叉树 1、满二叉树 (1)定义:当一棵二叉树的每一层的结点个 数都达到该层结点数的最大值,则该树称为 满二叉树。 (2)特点: 在满二叉树中,位于第K层上的结点数应为 2K-1个。 在满二叉树中,每一个结点的度不是0就 是2,没有度为1的结点,且叶结点都在同 层。(最高层) 武汉理工大学华夏学院-信息工程 <心 系
武汉理工大学华夏学院-信息工程 系 1、满二叉树 (１)定义： 当一棵二叉树的每一层的结点个 数都达到该层结点数的最大值，则该树称为 满二叉树。 (２)特点： . 在满二叉树中，位于第K层上的结点数应为 2K－1个。 . 在满二叉树中，每一个结点的度不是０就 是２，没有度为１的结点，且叶结点都在同 一层。（最高层） 三. 满二叉树与完全二叉树
(3)满二叉树的图例如图5-6所示 B 图5-6层次高废为四的满二又树的示意图 武汉理工大学华夏学院-信息工程 系
武汉理工大学华夏学院-信息工程 系 图5－６层次高度为四的满二叉树的示意图 N A B C D E F G H I J K L M O (３) 满二叉树的图例 如图5－6所示