数据结构 622二叉树的性质 性质1:在二叉树的第层上至多有2个结点(i>=1)。 证明:用归纳法证明之: ①i=1时,只有一个根结点,21=20=1是对的 ②假设对所有j(1≤<)命题成立,即第层上至多有 2-1个结点,那么,第i层至多有21-2个结 点。又二叉树每个结点的度至多为2, 第i层上最大结点数是第i-1层的2倍,即2.22=21 故命题得证。 性质2:深度为k的二叉树至多有2k个结点(k>=1) 证明:由性质1,可得深度为k的二叉树最大结点数是 ∑(第层的最大结点数)=∑2=2-1
数据结构 tjm 6.2.2 二叉树的性质 证明：用归纳法证明之： i=1时，只有一个根结点， 是对的 假设对所有j(1j<i)命题成立，即第j层上至多有 个结点，那么，第i-1层至多有 个结 点。又二叉树每个结点的度至多为2， 第i层上最大结点数是第i-1层的2倍，即 故命题得证。 2 2 1 1 0 = = i− 1 2 j− 2 2 i− 2 1 2 2 2 − − = i i 性质1：在二叉树的第i层上至多有 个结点（i>=1）。 1 2 i− 证明：由性质1，可得深度为k 的二叉树最大结点数是 ( ) 2 2 1 1 1 1 = = − = = − k k i k i i 第i层的最大结点数 性质2：深度为k的二叉树至多有 2 k −个结点（ 1 k>=1）
数据结构 性质3:对任何一棵二叉树T,如果其终端结点数为no, 度为2的结点数为n2,则no=n2+1 证明:设n为二叉树T中度为1的结点数。 因为二叉树中所有结点的度均小于或等于2, 所以其结点总数n=n0+n1+n2 又:二叉树中,除根结点外,其余结点都只有 个分支进入。设B为分支总数,则n=B+1 又:分支由度为1和度为2的结点射出, B=n, +2n 于是,n=B+1=n1+2n2+1=no+n1+n .n0=n2+1
数据结构 tjm 性质3：对任何一棵二叉树T，如果其终端结点数为n0， 度为2的结点数为n2，则n0=n2+1。 证明：设n1为二叉树T中度为1的结点数。 因为二叉树中所有结点的度均小于或等于2， 所以其结点总数n=n0+n1+n2。 又：二叉树中，除根结点外，其余结点都只有 一个分支进入。设B为分支总数，则n=B+1。 又：分支由度为1和度为2的结点射出， B=n1+2n2 于是，n=B+1=n1+2n2+1=n0+n1+n2 n0=n2+1