一棵有 n 个结点的满二叉树有多少个分支结点和多少个叶结点？该满二叉树的高度是多少？

[tag_link]

参考答案

分支结点数为(n−1)/2，叶结点数为(n+1)/2，高度为log2(n+1)。

推导过程

满二叉树n1=0且n0=n2+1；因此n=2n0−1，n2=(n−1)/2，n0=(n+1)/2，且n=2^h−1。

评分要点

使用n0=n2+1；给出两个数量公式；由2^h−1反解高度。

易错点

把满二叉树误写成完全二叉树的范围。