存储结构

顺序存储

用数组存储完全二叉树:根结点存下标 1,结点 i 的左孩子为 2i,右孩子为 2i+1,双亲为 ⌊i/2⌋\lfloor i/2 \rfloor。适合完全二叉树,普通二叉树会浪费大量空间。

链式存储

每个结点有数据域、左指针和右指针:

typedef struct BiTNode {
    int data;
    struct BiTNode *lchild, *rchild;  // 左、右孩子指针
} BiTNode, *BiTree;

习题

习题 1

如何用数组存储完全二叉树?

完全二叉树顺序存储下标关系链式存储

解题思路:

本题考查完全二叉树的数组存储。思路是利用完全二叉树结点编号连续这一特点,直接用下标算术表达左孩子、右孩子和双亲的位置,再比较它与普通二叉树在存储方式上的取舍。

详细步骤:

  1. 用一维数组按下标顺序存储完全二叉树,根结点存放在下标 1 处。
  2. 由完全二叉树的编号规律,任意结点 ii 的左孩子下标为 2i2i,右孩子下标为 2i+12i+1,双亲下标为 ⌊i/2⌋\lfloor i/2 \rfloor。
  3. 由于完全二叉树的结点在数组中依次连续存放,下标 1 到 n 恰好对应全部结点,顺序存储不会浪费空间。
  4. 普通二叉树的结点在数组中可能大量空缺,顺序存储会浪费大量空间,因此宜用链式存储。

最终答案:

用一维数组按下标顺序存储完全二叉树:根结点存下标 1,任意结点 i 的左孩子为 2i,右孩子为 2i+1,双亲为 ⌊i/2⌋\lfloor i/2 \rfloor。完全二叉树适合顺序存储,不会浪费空间;普通二叉树顺序存储会浪费大量空间,宜用链式存储。

发现内容有问题?

告诉我们哪里需要改进。