BCSP-X · 2024 BCSP-X 下半年活动基础知识测评（初中组） 第 9 题

如果一棵二叉树只有根结点，那么这棵二叉树的高度为 $1$。请问高度为 $6$ 的完全二叉树有（ ）种不同的形态？

这题别想遍历了，直接数节点。高度6的完全二叉树，节点数n在31到63之间，形态数就是n/2（n偶）或(n+1)/2（n奇）的总和，快速加一下就行。

学生容易把‘完全二叉树’想成‘满二叉树’，以为只有2^6-1=63这一种，或者误以为高度6就是63个节点。还有会混淆叶子数公式，把n/2和(n+1)/2用反，或者忘记n=31时叶子是16而不是15。

这题考的是完全二叉树的节点数与叶子数的关系，以及高度为h的完全二叉树节点数的取值范围。概念很简单：完全二叉树就是除最后一层外全满，最后一层节点靠左排。高度h的完全二叉树，节点数n最小是2^(h-1)-1（刚好满到h-1层），最大是2^h-1（满到h层）。对于任意n，叶子数L = n/2（n偶）或 (n+1)/2（n奇），这个公式是推导出来的：n-1个非叶子节点，每个非叶子节点贡献1个叶子，所以L = n - (n-1) = 1？不对，重来：非叶子节点数 = n - L，每个非叶子节点有2个孩子，总孩子数2(n-L) = n-1（总节点减根），解得L = (n+1)/2（n奇）或 n/2（n偶）。

命题人喜欢挖坑就坑在‘高度6’不等于‘63个节点’。高度6的完全二叉树，节点数n可以是31到63之间的任意整数。形态数就是每个n对应的叶子数之和。n=31时，L=16；n=32时，L=16；n=33时，L=17；n=34时，L=17；n=35时，L=18；n=36时，L=18；n=37时，L=19；n=38时，L=19；n=39时，L=20；n=40时，L=20；n=41时，L=21；n=42时，L=21；n=43时，L=22；n=44时，L=22；n=45时，L=23；n=46时，L=23；n=47时，L=24；n=48时，L=24；n=49时，L=25；n=50时，L=25；n=51时，L=26；n=52时，L=26；n=53时，L=27；n=54时，L=27；n=55时，L=28；n=56时，L=28；n=57时，L=29；n=58时，L=29；n=59时，L=30；n=60时，L=30；n=61时，L=31；n=62时，L=31；n=63时，L=32。

把这些数加起来：16+16+17+17+18+18+19+19+20+20+21+21+22+22+23+23+24+24+25+25+26+26+27+27+28+28+29+29+30+30+31+31+32 = 32种。所以选B。

避坑：别只算n=63这一种，也别把n=31当成15个叶子。考频上，这类‘高度h的完全二叉树形态数’在BCSP近年出现频次不高，但属于完全二叉树性质的经典应用，和‘叶子数公式’、‘节点数范围’常一起考。趋势看，命题人可能继续用‘高度’换‘节点数’来考完全二叉树，或者结合‘层序遍历’问形态数。暂无足够依据预测未来具体变体，但核心考点（完全二叉树节点数与叶子数关系）会稳定出现。