存储结构
用数组存储完全二叉树:根结点存下标 1,结点 i 的左孩子为 2i,右孩子为 2i+1,双亲为 。适合完全二叉树,普通二叉树会浪费大量空间。
每个结点有数据域、左指针和右指针:
typedef struct BiTNode {
int data;
struct BiTNode *lchild, *rchild; // 左、右孩子指针
} BiTNode, *BiTree;
习题 1
如何用数组存储完全二叉树?
解题思路:
本题考查完全二叉树的数组存储。思路是利用完全二叉树结点编号连续这一特点,直接用下标算术表达左孩子、右孩子和双亲的位置,再比较它与普通二叉树在存储方式上的取舍。
详细步骤:
- 用一维数组按下标顺序存储完全二叉树,根结点存放在下标 1 处。
- 由完全二叉树的编号规律,任意结点 的左孩子下标为 ,右孩子下标为 ,双亲下标为 。
- 由于完全二叉树的结点在数组中依次连续存放,下标 1 到 n 恰好对应全部结点,顺序存储不会浪费空间。
- 普通二叉树的结点在数组中可能大量空缺,顺序存储会浪费大量空间,因此宜用链式存储。
最终答案:
用一维数组按下标顺序存储完全二叉树:根结点存下标 1,任意结点 i 的左孩子为 2i,右孩子为 2i+1,双亲为 。完全二叉树适合顺序存储,不会浪费空间;普通二叉树顺序存储会浪费大量空间,宜用链式存储。
