🏷️ 知识点：二叉树存储

对于任意一棵高度为 5 且有 10 个节点的二叉树，若采用顺序存储结构保存，每个结点占 1 个存储单元（仅存放结点的数据信息），则存放该二叉树需要的存储单元数量至少是（ ）。

二叉树存储

A. 31 B. 16 C. 15 D. 10

[tag_link]

正确答案：A

二叉树采用 顺序存储 时，用数组下标来表示结点之间的父子关系。对于一棵高度为 5 的二叉树，为了满足任意性，其 1~5 层的所有结点都要被存储起来，即考虑为一棵高度为 5 的满二叉树，总共需要存储单元的数量为 1 + 2 + 4 + 8 + 16 = 31。

若二叉树的节点值均为正整数，采用顺序存储方式保存在数组 R 中，用 -1 表示节点不存在，则下列数组中，不能表示一棵二叉树的是（）。

二叉树存储

A. R[] = {20, 15, 40, -1, -1, 35} B. R[] = {15, 40, 10, 18, 35, -1, -1} C. R[] = {15, 40, 10, -1, -1, -1, 12} D. R[] = {17, 20, 35, -1, 18, 45, -1, -1, 19, 27}

[tag_link]

正确答案：D

在二叉树的顺序存储表示中，数组中的每个位置对应二叉树中特定节点。若节点值非负（-1 表示不存在），则非 -1 节点的父节点必须存在（根节点除外）。对于选项 D，索引 8 处的节点值为 19，其父节点索引为 3（由公式⌊(8−1)/2⌋=3计算），但索引 3 处的值为 -1，即父节点不存在，违反了二叉树顺序存储的规则。因此，选项 D 不能表示一棵二叉树。

其他选项均满足每个非 -1 节点（除根节点）都有存在的父节点，是有效的二叉树顺序存储表示。