问题: 二叉树有哪几种存储方式？什么样的二叉树适合用数组来存储？

1.树（Tree）

三个相似概念：

• 高度（Height）
• 深度（Depth）
• 层（Level）
  
  

2. 二叉树（Binary Tree）

满二叉树：除了叶子节点，其他节点都有左右两个子节点。
完成二叉树：叶子节点只出现在最后两层，最后一层叶子节点都靠左，其他层的节点数要达到最大。

为什么特意拎出完成二叉树：如何存储二叉树？

• 基于指针或者引用的二叉链式存储法，比较常见
• 数组，完全二叉树比较省内存，堆和堆排序就基于此实现。

3. 二叉树的遍历

• 前序遍历是指，对于树中的任意节点来说，先打印这个节点，然后再打印它的左子树，最后打印它的右子树。

• 中序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它本身，最后打印它的右子树。

• 后序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它的右子树，最后打印这个节点本身。

递推公式：

前序遍历的递推公式：
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
1
2
3
4
5
6
7
8

代码：

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节点
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

遍历时间复杂度：O(n).