下面介绍二叉树的性质: 性质1在二叉树中,第层的结点数最多为2(≥1) 证明:应用归纳法有,=1时,为第1层,只有一个根结点, 显然21=20=1正确;现假定对所有的1≤j< 命题成立,即第/层上至多有2个结点,那么可证明 j=i时命题也成立由归纳假设:第—1层上至多有 2-2个结点,因二叉树中的每个结点的度最大为2,故在第讠 层上的最大结点数为第一1层上的最大结点数的2倍,即 2×21-2=21 性质2深度为/的二叉树至多有2-1(k≥1)个结点 证明:由性质1,深度为的二叉树的最大结点数为 ∑(第i层上的最大结点数) ∑2 2-1(q=2,a1=1)
下面介绍二叉树的性质： 性质1 在二叉树中, 第 i 层的结点数最多为 2 ( 1). 1 − i i 证明: 应用归纳法有, i =1 时, 为第1层,只有一个根结点, 显然 2 2 1 1 0 = = i− 正确; 现假定对所有的 j,1 j i 命题成立, 即第 j 层上至多有 1 2 j− 个结点, 那么可证明 j = i 时命题也成立.由归纳假设: 第 i −1 层上至多有 2 2 i− 个结点,因二叉树中的每个结点的度最大为2, 故在第 i 层上的最大结点数为第 i −1 层上的最大结点数的2倍, 即 2 2 2 . −2 −1 = i i 性质2 深度为 k 的二叉树至多有 2 −1(k 1) k 个结点. 证明: 由性质1,深度为 k 的二叉树的最大结点数为: = k i 1 (第 i 层上的最大结点数) 2 1( 2, 1) 1 (1 ) 2 1 1 1 1 = − = = − − = = = − q a q a q k k k i i
性质3对任何一棵二叉树T,如果其终端结点数(即叶子 数)为m,度为2的结点数为n2,则m=n2+1 证明:设m1为二叉树T中度为1的结点数(即此结点仅有 棵子树,左子树或右子树,但非叶子),因二叉树中所有 结点的度均小于或等于2,所以其结点数为n=n0+n1+n2 又因为,除根结点外,其余结点都有一条分支进入,设B为 分支总数,则n=B+1,由于这些分支是由度为1或2射出的 所以又有B=n1+2n2,从而n=n+2n2+1,故可得 b+n1+n2=n1+2n2+1,m0=n2+1 下面介绍两种特殊形态的二叉树,即满二叉树和完全二 叉树.定义一棵深度为k且有2-1个结点的二叉树为满二叉 树,其特点是每一层上的结点数都是最大结点数
性质3 对任何一棵二叉树T, 如果其终端结点数(即叶子 数)为 0 n ,度为2的结点数为 2 n , 则 n0 = n2 +1 证明: 设 1 n 为二叉树T中度为1的结点数(即此结点仅有一 棵子树, 左子树或右子树, 但非叶子), 因二叉树中所有 结点的度均小于或等于2, 所以其结点数为 n = n0 + n1 + n2 : 又因为, 除根结点外, 其余结点都有一条分支进入, 设B为 分支总数, 则 n = B +1 ,由于这些分支是由度为1或2射出的 所以又有 B = n1 + 2n2 , 从而 n = n1 + 2n2 +1 , 故可得 n0 + n1 + n2 = n1 + 2n2 +1, n0 = n2 +1 下面介绍两种特殊形态的二叉树, 即满二叉树和完全二 叉树. 定义一棵深度为 k 且有 2 −1 k 个结点的二叉树为满二叉 树, 其特点是每一层上的结点数都是最大结点数
下面这棵树就是满二叉树,对左边的满二叉树的结点进行 连续编号,并约定编号顺序是 从根结点起,自上而下,自左 至右进行.则可引出 另一种特殊形态的二 叉树,即完全三 (⑨①@③④④定义:深度为 k的有n个结点的二叉树,当且仅当其每一个结点都与深度 为k的满二叉树中编号从1至n的结点一一对应,称此二叉 树为完全二叉树.如下图所示
下面这棵树就是满二叉树, 对左边的满二叉树的结点进行 连续编号, 并约定编号顺序是 从根结点起, 自上而下, 自左 1 2 15 4 5 8 9 11 12 13 14 3 10 6 7 至右进行. 则可引出 另一种特殊形态的二 叉树, 即完全二 叉树. 定义: 深度为 k 的有 n 个结点的二叉树, 当且仅当其每一个结点都与深度 为 k 的满二叉树中编号从1至 n 的结点一一对应, 称此二叉 树为完全二叉树. 如下图所示. 1 2 4 5 8 9 3 10 6 7
下图是非完全二叉树,即为一棵一般的二叉树 有10个结点的完全二叉树重新显示 在下面.可分析出其特点为 1.叶子结点只可能在第 k层及第k-1层上出现 G⑨(为最大层次 2对任一结点,若其右分支下的子孙 的最大层次为l,则其左分支下的子孙 ①的最大层次必为域或H 3.完全二叉树可从满二 3)叉树中,自最高层次向 上,且每层自右至 左顺序删除叶子结 点而获得 8)⑧@注意:满足特点1或2,或满足特点1和2的二 叉树不一定是完全二叉树,但若二叉树是完全二叉树,则一定
下图是非完全二叉树, 即为一棵一般的二叉树. 1 有10个结点的完全二叉树重新显示 2 4 5 8 9 11 3 6 7 在下面. 1 2 4 5 8 9 3 10 6 7 可分析出其特点为: 1.叶子结点只可能在第 k层及第k -1层上出现 (k为最大层次). 2.对任一结点, 若其右分支下的子孙 的最大层次为l, 则其左分支下的子孙 的最大层次必为l或l+1. 3.完全二叉树可从满二 叉树中, 自最高层次向 上, 且每层自右至 左顺序删除叶子结 点而获得. 注意: 满足特点1或2, 或满足特点1和2的二 叉树不一定是完全二叉树, 但若二叉树是完全二叉树, 则一定
满足特点1和2.而从特点3得到的二叉树一定是完全二叉 树.完全二叉树有两个重要的性质 性质4具有n个结点的完全二叉树的深度为Log2n」+1 证明:假设具有n个结点的完全二叉树的深度为k,则由 性质2和完全二叉树的定义有2k-1-1<n≤2-1(注意到 深度为k如24-1=n,则深度为k-1)由上式得 2≤n<2,则k-1≤log2n<k,因为k是整数,所以 k=og2n」+1 性质5如果对一棵具有n个结点的完全二叉树(其深度为 log2n」+1)的结点按层序编号(从第一层到第Log2n」+1 层,每层从左到右),则对任一结点(1≤i≤n),有 (1)如果i=1,则结点是二叉树的根,无双亲;如果>1 则其双亲是结点i/2」
满足特点1和2. 而从特点3得到的二叉树一定是完全二叉 树. 完全二叉树有两个重要的性质. 性质4 具有n个结点的完全二叉树的深度为 log2 n +1 证明: 假设具有n个结点的完全二叉树的深度为 k , 则由 性质2和完全二叉树的定义有 2 1 2 1 1 − − k− k n (注意到 深度为 k , 如 n k − = − 2 1 1 , 则深度为 k −1) 由上式得 k k 2 n 2 1 − ,则 k − n k 2 1 log ,因为 k 是整数, 所以 log 1. k = 2 n + 性质5 如果对一棵具有n个结点的完全二叉树(其深度为 log 1) 2 n + 的结点按层序编号(从第一层到第 log2 n +1 层, 每层从左到右),则对任一结点 i(1 i n) , 有 (1) 如果 i =1 ,则结点是二叉树的根, 无双亲; 如果 i 1 则其双亲是结点 i / 2