基于数组的顺序存储法
若节点X存储在数组中下标为i的位置
2 * i 存储左子节点
2 * i + 1存储右子节点
i/2存储其父节点
由于这是个完全二叉树，所以仅“浪费”了一个下标0的存储位置。若是非完全二叉树，就会浪费较多存储空间：
所以完全二叉树用数组存储最省内存，就不像链式存储法，还要存储左、右子节点的指针。所以完全二叉树要求最后一层的子节点都靠左。
堆也是一种完全二叉树，所以其最常用的存储方式就是数组。
二叉树的遍历
经典遍历
- 前序遍历
对于树中的任意节点来说，先打印这个节点，然后再打印它的左子树，最后打印它的右子树。 - 中序遍历
对于树中的任意节点来说，先打印它的左子树，然后再打印它本身，最后打印它的右子树。 - 后序遍历
对于树中的任意节点来说，先打印它的左子树，然后再打印它的右子树，最后打印这个节点本身。
- 这些都是递归过程。
递归代码的关键就是递推公式，递推公式的关键就是，如果要解决问题A，就假设子问题B、C已经解决，然后再来看如何利用B、C来解决A。
所以可以写出前、中、后序遍历的
递推公式
前序遍历
preOrder(r) = print r->preOrder(r->left)->preOrder(r->right)
中序遍历
inOrder(r) = inOrder(r->left)->print r->inOrder(r->right)
后序遍历
postOrder(r) = postOrder(r->left)->postOrder(r->right)->print r
void preOrder(Node* root) { if (root == null) return; print root // 此处为伪代码，表示打印root节点 preOrder(root->left); preOrder(root->right); } void inOrder(Node* root) { if (root == null) return; inOrder(root->left); print root // 此处为伪代码，表示打印root节点 inOrder(root->right); } void postOrder(Node* root) { if (root == null) return; postOrder(root->left); postOrder(root->right); print root // 此处为伪代码，表示打印root节点 }
时间复杂度
每个节点最多会被访问两次，所以遍历操作的时间复杂度，跟节点的个数n成正比，也就是说二叉树遍历的时间复杂度是O(n)。
参考
