题目
完全二叉树[1]的存储结构通常采用顺序存储[2]结构( )
完全二叉树[1]的存储结构通常采用顺序存储[2]结构( )
题目解答
答案
正确
解析
完全二叉树的结构特点使其非常适合采用顺序存储。因为完全二叉树的节点排列非常规则,可以按层序依次存入数组,无需额外指针,既节省空间,又能通过公式快速定位节点的父子关系。而链式存储虽然灵活,但空间利用率低,不符合完全二叉树的特性。
完全二叉树的定义是:除最后一层外,其他层的节点数均达到最大值,且最后一层的所有节点都集中在最左边。这种结构允许用数组按层序编号存储所有节点,其中:
- 父节点的索引为$i$时,左孩子为$2i+1$,右孩子为$2i+2$;
- 子节点的索引为$i$时,父节点为$\lfloor (i-1)/2 \rfloor$。
这种存储方式无需额外空间记录指针,且节点间关系可通过公式直接计算,因此完全二叉树通常采用顺序存储结构。