二叉树的性质 性质1:在二叉树的第i层上至多有2个结点 1层:结点个数211=20个 2层:结点个数221=21个 3层:结点个数231=22个 证:k=1时成立,设k=|-1时成立则当k=i时在二叉树的第i层上至多有 2111*2=2H个结点 性质2:高度为k的二叉树至多有2k1个结点 证:利用性质1,将第1层至第k层的最多的结点数进行相加: 1+2+22+……+2k-2+2k1=2k-1 性质3:二叉树的叶子结点数n0等于度为2的结点数n2+1 证:设度为1的结点数为n1,树枝的总数为B则:B=n-1=n0+n1+n21 又B=n1+2×n2;原命题得证。二叉树的性质 •性质1：在二叉树的第 i 层上至多有 2 i-1个结点 B C D E F L A 1层：结点个数 2 1-1=20 个 2层：结点个数 2 2-1=21 个 3层：结点个数 2 3-1=22 个 证：k = 1 时成立，设 k = i-1 时成立 则当 k = i 时在二叉树的第 i 层上至多有 2 i-1-1 * 2 = 2 i-1 个结点 •性质2：高度为 k 的二叉树至多有2 k - 1 个结点 证：利用性质 1 ，将第 1 层至第 k 层的最多的结点数进行相加： 1 + 2 + 22 + ………… + 2k-2 + 2k-1 = 2k - 1 •性质3：二叉树的叶子结点数 n0 等于度为 2 的结点数 n2 + 1 证：设度为 1 的结点数为 n1，树枝的总数为 B 则：B = n-1=n0+n1+n2-1 又 B = n1+2×n2； 原命题得证。 C E F L A