前言：已知一个二叉树的中序序列和前序序列，或者中序序列和后序序列就可以唯一确定一个二叉树（必须知道中序序列），只知道前序和后序不能创建唯一的二叉树。

1.引例

已知下列某二叉树(8个结点)的两个序列，如何确定一棵唯一的二叉树呢？

①前序序列的第一个结点，就是根结点
②在中序序列中，找到根结点，记录根结点前的结点，即为左子树结点，图中为3(4,7,2)，根结点后的结点，即为右子树结点，图中为(5,3,8,6)
③在前序序列中，根结点往后对应数量的结点，就是左子树的前序序列(2,4,7)
④现在左子树的前序(2,4,7)和中序序列(4,7,2)都有了，再重复步骤①-③,就完成了左子树的创建

⑤找到右子树的前序序列(3,5,6,8),中序序列(5,3,8,6),再重复步骤①-③,就完成了右子树的创建

2.具体代码实现

其实引例中描述的"重复步骤①-③"，就是递归的思想，下面是具体代码
解释：
Formdata和Middledata是前序和中序数组的指针
num是二叉树的结点总数

Bintree_Node* Build(int* Formerdata, int* Middledata, int num)
{if (Formerdata == NULL || Middledata == NULL || num <= 0)return NULL;//先序遍历，第一个值就是根结点Bintree_Node* root = new Bintree_Node;root->data = Formerdata[0];root->left = root->right = NULL;//如果只有一个结点if (num == 1 && *Former == *Middledata)return root;//在中序序列中找到根结点int left_num = 0;//左子树的结点总数int* middle_root = Middledata;//中序序列中的根结点//第二个条件：循环要在Middledata中进行while (*middle_root != Formerdata[0]&&middle_root <= (Middledata + num - 1)){middle_root++;left_num++;}if (*middle_root != Formerdata[0])//未找到根结点，输入错误{cout << "未找到根结点，输入错误" << endl;return NULL;}//创建左子树if (left_num > 0)root->left = Build(Formerdata + 1, Middledata, left_num);//Formerdata+1即为左子树的前序序列的开始//创建右子树if (num - left_num - 1 > 0)root->right = Build(Formerdata + left_num + 1, Middledata+left_num+1, num - left_num - 1);return root;
}

测试

void main()
{int Former[] = { 1,2,4,7,3,5,6,8 };int Middle[] = { 4,7,2,1,5,3,8,6 };Bintree_Node* root=Build(Former, Middle, 8);Show(root);//前序遍历
}