存储结构

顺序存储

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

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

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

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

答案与解析

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