算法：树的遍历方式

[pengjielee]

树结构多种多样，我们最常用的还是二叉树。

特殊二叉树：

1. 满二叉树；
2. 完全二叉树；

二叉树的存储：

1. 基于指针或者引用的二叉链式存储法；
2. 基于数组的顺序存储法；

我们把根节点存储在下标 i = 1 的位置，那左子节点存储在下标 2 * i = 2 的位置，右子节点存储在 2 * i + 1 = 3 的位置。

如果节点x存储在数组中下标为 i 的位置，下标为 2 * i 的位置存储的就是左子节点，下标为 2 * i + 1 的位置存储的就是右子节点。反过来，下标为 i / 2 的位置存储的就是它的父节点。

通过这种方式，我们只要知道根节点存储的位置（一般情况下，为了方便计算子节点，根节点会存储在下标为1的位置），这样就可以通过下标计算，把整棵树都串起来。

二叉树的遍历：

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

前序遍历的递推公式：
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)->postOrder r

// 前序：根 -> 左 -> 右
void preOrder(Node* root){
	if(root == null) return;
	print root;          // 先打印根节点
	preOrder(root->left);
	preOrder(root->right);
}
// 中序： 左 -> 根 -> 右
void inOrder(Node* root){
	if(root == null) return;
	inOrder(root->left);
	print(root);     // 中间打印根节点
	inOrder(root->right);
}
// 后序：左 -> 右 -> 根
void postOrder(Node* root){
	if(root == null) return;
	postOrder(root->left);
	postOrder(root->right);
	print root;   // 最后打印根节点
}

通过遍历序列构造二叉树

给定二叉树: [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7

前序遍历：3,9,null,null,20,15,7
中序遍历：null,9,null,3,15,20,7
后序遍历：null,null,9,15,7,20,3

1. 前序和中序遍历序列构造二叉树：
   前序遍历：根节点是3，根左右的关系
   中序遍历：根节点是3，左根右的关系

2. 中序和后序遍历序列构造二叉树：
   后序遍历：根节点是3，左右根的关系
   中序遍历：根节点是3，左根右的关系