CSP真题——二叉树

高大力

CCF推出CSP认证（Certified Softwmare Professional， 软件能力认证），以评价计算机专业人士或准专业人士计算机科学的基础能力——算法和编程能力。CSP已成为一些企业及许多大学评价计算机专业大学生专业能力的重要工具。

这是CSP2021初赛的一道选择题，涉及知识点为二叉树形态。

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

A. 16

B. 15

C. 17

D. 32

二叉树（Binary tree）是树形结构的一个重要类型。二叉树特点是每个节点最多只能有两棵子树，通常子树被称作“左子树”（left subtree）和“右子树”（right subtree），且左右次序不能颠倒。二叉树的第i层至多有2^（i-1）个结点;深度为k的二叉树至多有2^k-1个结点;深度为k，有n個节点的二叉树，当且仅当其每一个节点都与深度为k的满二叉树中，序号为1至n的节点对应时，称之为完全二叉树。

满二叉树的特点在于“满”，即每层的结点数都是最大结点数。

完全二叉树是相对于满二叉树来说的。二叉树是有序树，对一棵满二叉树和一棵完全二叉树按“自上向下，自左向右”的顺序进行编号。完全二叉树中的所有结点的编号必须和满二叉树的相同编号的结点在位置上完全相同。换句话说，完全二叉树的结点按“自上向下，自左向右”的顺序不能中断。T3 的结点C 没有左叶子，显然按那个顺序是中断的。

回到本题，高度为5的完全二叉树，在第5层至多有2^（5-1）=16个节点，从1个节点到16个节点，可以至多有16种形态。