二叉树的先序+中序和后序+中序这两种组合可以确定二叉树的形状
以先序+中序为例。先序序列首元素确定根节点，在中序序列中找到根节点，左边就是左子树，右边就是右子树，然后递归建立。
需要注意是在递归建立左子树和递归建立右子树时计算参数要小心。
#include <stdio.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int TElemtype;
typedef struct BiTNode
{
TElemtype Data;
struct BiTNode* Lchild, * Rchild;
}BiTNode;
typedef BiTNode* BiTree;
int array_length;
int Search(TElemtype item, TElemtype* arr)
{
for (int i = 0; i < array_length; i++) {
if (arr[i] == item)return i;
}
return -1;
}
void Pre_And_IN(BiTree& T, TElemtype* pre, TElemtype* in, TElemtype ps, TElemtype is, int n)//先序中序建树
{
if (n == 0) T = NULL;
else {
int k = Search(pre[ps], in);
if (k == -1) {
T = NULL;
return;
}
else {
T = (BiTree)malloc(sizeof(BiTNode));
T->Data = in[k];
if (k - is == 0) T->Lchild = NULL;
else Pre_And_IN(T->Lchild, pre, in,ps+1,is,k-is );
if (n - 1 - k + is == 0)T->Rchild = NULL;
else Pre_And_IN(T->Rchild, pre, in,ps+k-is+1,k+1,n-1-k+is );
}
}
}
void Post_And_In(BiTree& T, TElemtype* post, TElemtype* in, TElemtype pos, TElemtype is, int n)
{
if (n == 0) {
T = NULL; return;
}
else {
int k = Search(post[pos], in);
if (k == -1) {
T = NULL;
return;
}
else {
T = (BiTree)malloc(sizeof(BiTNode));
T->Data = in[k];
if (k==is)T->Lchild = NULL;
else Post_And_In(T->Lchild, post, in, pos - n + k - is, is, k - is);
if (n==k-is+1)T->Rchild = NULL;
else Post_And_In(T->Rchild, post, in, pos - 1, k + 1, n - k + is - 1);
}
}
}
int main()
{
BiTree N[9];
for (int i = 0; i < 9; i++) { N[i] = CreateNode(i); N[i]->IfVisited = 0; }
N[0]->Lchild = N[1]; N[0]->Rchild = N[2];
N[1]->Lchild = N[3];
N[2]->Lchild = N[4]; N[2]->Rchild = N[5];
N[3]->Rchild = N[6];
N[6]->Lchild = N[7]; N[6]->Rchild = N[8];
int pre[7] = { 23,54,2,6,8,9,13 };
int in[7] = { 2,54,6,23,8,13,9 };
array_length = 7;
int post[7] = { 2,6,54,13,9,8,23 };
BiTree T1, T2;
Pre_And_IN(T1, pre, in, 0, 0, 7);
Post_And_In(T2, post, in, 6, 0, 7);
}