🏷️ 知识点：满二叉树

设一棵非空完全二叉树 T 的所有叶结点均位于同一层，且每个非叶结点都有 2 个子结点。若 T 有 k 个叶结点，则 T 的结点总数是（ ）。

满二叉树

A. (2k-1) B. (2k) C. (2k+1) D. (2^k-1)

[tag_link]

正确答案：A

非叶结点的度均为 2, 且所有叶结点都位于同一层的完全二叉树就是 满二叉树 。对一棵高度为 h 的满二叉树（空树h=0）, 其最后一层全部是叶结点，数量为2h−1; 总结点数为2h−1。因此当2h−1=k时，可以得到2h−1=2k−1。

对于一组权值都相等的 16 个字母，构造相应的哈夫曼树，这棵哈夫曼树是一棵（　）。

A. 完全二元树 B. 一般二元树 C. 满二元树 D. 以上都不正确

哈夫曼树 满二叉树

[tag_link]

正确答案：C

哈夫曼树的构造过程中，每次合并都是将两个权值最小的节点合并为一个新的内部节点，因此每个内部节点都恰好有两个子节点，而叶子节点则没有子节点。 根据二叉树的定义，如果一棵二叉树中的每个节点要么是叶子节点（无子节点），要么是有两个子节点的内部节点，那么这棵树称为满二叉树（或称严格二叉树）。 因此，无论权值是否相等，哈夫曼树总是满足这一条件，它必然是一棵满二叉树。

对于本题中权值相等的16个字母，构造出的哈夫曼树同样符合这一性质：每个内部节点都有两个子节点，所以它是一棵满二叉树。 虽然权值相等时，通过特定的合并顺序可能使树的结构更加平衡（例如形成完全二叉树），但满二叉树这一性质是始终成立的。 其他选项如完全二叉树或一般二叉树不一定必然满足，而满二叉树则是哈夫曼树的固有特征，故选项C正确。