前面说了那么多关于二叉树的，这篇来写个总结吧！主要是关于二叉树的序列转换。
分别是：已知先序、中序，转后序； 已知先序、中序，转层序；
已知后序、中序，转先序； 已知后序、中序，转层序；
已知二叉搜索树的任何序列，重建二叉搜索树。
其实上面的问题都可以归为：给定二叉树序列，在重新遍历二叉树。
关于二叉树的遍历可以在这篇文章：C语言-二叉树的遍历-斐斐のBlog
下面主要介绍如何重建二叉树。
在重建二叉树之前先定义一个查找函数，在序列中查找某数，然后返回该数的下标。
int find_index(int x, const int *arr){
for(int i = 0; i < MAX_SIZE; i++) //MAX_SIZE根据数组大小修改，防越界
if(arr[i] == x) return i;
return -1;
}0x00、先序、中序 --> 还原二叉树
二叉树的先序序列特点为：{根部，左子树，右子树}
中序序列特点为：{左子树，根部，右子树}
根据这一特点，我们的思路是：以先序序列第一个值为根，将根写入二叉树。接着在中序序列中找到根，根据中序序列起始位置与根节点的距离，递归还原左右子树。
递归的终点就是二叉树起始位置大于终止位置。
具体操作实现代码如下：
/* *
* 二叉树的还原方法
* 参数preL：先序序列的起始位置
* 参数preR：先序序列的结束位置
* 参数inL：中序序列的起始位置
* 参数inR：中序序列的结束位置
* 即：先序序列区间为[preL, preR]，中序序列区间为[inL, inR]
*/
node* void create(int preL, int preR, int inL, int inR){
if(preL > preR) return NULL; //递归终点(返回NULL代表树叶)
node* root = new node; //新建当前根节点
root->data = pre[preL]; //先序序列第一个值就是根节点
int index_inorder = find_index(root->data, in);//找到根节点在中序序列中的位置
int sum_of_left_tree = index_inorder - inL;//计算左子树的大小
/*下面开始确定左子树位置，并构建左子树*/
int L_new_preL = preL + 1; //新的左子树先序序列起始位置为原来起始位置+1。因为第一个位置是当前根节点
int L_new_preR = preL + sum_of_left_tree; //新左子树先序序列终止位置为原来左子树起始位置+左子树大小
int L_new_inL = inL; //新左子树中序序列起始位置为原左子树中序序列起始位置
int L_new_inR = index_inorder - 1; //新左子树中序序列终止位置为原左子树根节点位置-1
root->lchild = create(L_new_preL, L_new_preR, L_new_inL, L_new_inR);//递归构建左子树
/*下面开始确定右子树位置，并构建右子树*/
int R_new_preL = L_new_preR + 1; //左子树在先序序列结束位置往后都是右子树
int R_new_preR = preR;
int R_new_inL = index_inorder + 1; //原中序序列根节点往后都是新右子树
int R_new_inL = inR;
root->rchild = create(R_new_preL, R_new_preR, R_new_inL, R_new_inL);//递归构建右子树
return root; //返回新建二叉树的根节点
}0x01、后序、中序 -->还原二叉树
二叉树的后序序列特点为：{左子树，右子树，根部}
中序序列特点为：{左子树，根部，右子树}
根据这一特点，我们的思路是：以后序序列第一个值为根，将根写入二叉树。接着在中序序列中找到根，根据中序序列起始位置与根节点的距离，递归还原左右子树。
递归的终点就是二叉树起始位置大于终止位置。
具体操作实现代码如下：
/* *
* 二叉树的还原方法
* 参数post_left：后序序列的起始位置
* 参数post_right：后序序列的结束位置
* 参数in_left：中序序列的起始位置
* 参数in_right：中序序列的结束位置
* 即：后序序列区间为[post_left, post_right]，中序序列区间为[in_left, in_right]
*/
node* create(int post_left, int post_right, int in_left, int in_right){
if(post_left > post_right) return NULL;
node* root = new node;
root->data = post_order[post_right];
int root_position_inorder = find_index(in_order, root->data);
int Lchild_sum = root_position_inorder - in_left;
int Lchild_post_left = post_left,
Lchild_post_right = post_left + Lchild_sum - 1,
Lchild_in_left = in_left,
Lchild_in_right = root_position_inorder - 1;
int Rchild_post_left = post_left + Lchild_sum,
Rchild_post_right = post_right - 1,
Rchild_in_left = root_position_inorder + 1,
Rchild_in_right = in_right;
root->lchild = create(Lchild_post_left, Lchild_post_right, Lchild_in_left, Lchild_in_right);
root->rchild = create(Rchild_post_left, Rchild_post_right, Rchild_in_left, Rchild_in_right);
return root;
}所以，"给出中序和其他序列，求另一序列"的还原方法通常是：判断是否达到递归终点、判断根节点、判断左右子树区间、递归构建左右字子树
0x02、给出二叉搜索树的序列，重建二叉搜索树
这个问题其实很好解决，因为二叉搜索树有一个重要的特性：二叉搜索树的中序序列是有序的。
无论给出什么序列，我们只需要进行排序，然后中序遍历并写入二叉树即可。
我们通常来使用静态二叉树来完成。
例如：
//假设前面已经使用sort函数排序好了序列input，现在将input插入到静态二叉树中
typedef struct{
int data, lchild, rchild;
} node;
node tree[8];
int iterator = 0; //迭代器
insert(0); //从输入的第一个节点开始
void insert(int root){
if(root == -1) return;
insert(input[root].lchild);
tree[iterator++] = input[root].data;
insert(input[root].rchild);
}