主要内容 #

1. 什么是数组表示法
2. 如何实现数组表示法

1.什么是数组表示法 #

二叉树的存储结构有两种，分别为顺序存储和链式存储。本节介绍二叉树的顺序存储结构，也就是数组表示法。
二叉树的顺序存储，指的是使用数组存储二叉树。需要注意的是，顺序存储只适用于完全二叉树。换句话说，只有完全二叉树才可以使用顺序表存储。因此，如果我们想数组表示普通二叉树，需要提前将普通二叉树转化为完全二叉树。
普通二叉树转完全二叉树的方法很简单，只需给二叉树额外添加一些节点，将其”拼凑”成完全二叉树即可。如图 1 所示：

2.如何实现数组表示法 #

完全二叉树的数组表示法，仅需从根节点开始，按照层次依次将树中节点存储到数组即可。

例如，图 2 所示的完全二叉树，其用数组表示法如图 3 所示：

同样，存储由普通二叉树转化来的完全二叉树也是如此。例如，图 1 中普通二叉树的数组存储状态如图 4 所示：

由此，我们就实现了完全二叉树的顺序存储。
不仅如此，从顺序表中还原完全二叉树也很简单。我们知道，完全二叉树具有这样的性质，将树中节点按照层次并从左到右依次标号（1,2,3,…），若节点 i 有左右孩子，则其左孩子节点为 2*i，右孩子节点为 2*i+1。
此性质可用于还原数组中存储的完全二叉树，也就是实现由图 3 到图 2、由图 4 到图 1 的转变。