输入某二叉树的前序遍历和中序遍历的结果，重建出这棵二叉树，假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如，输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建出这棵满足前序遍历和中序遍历的二叉树并输出它的头结点。
成都创新互联公司是一家专业提供
元江县企业网站建设,专注与成都网站建设、
成都网站设计、
H5技术、小程序制作等业务。10年已为元江县众多企业、政府机构等服务。创新互联专业网络公司优惠进行中。
对一棵二叉树前序遍历的顺序是“根结点->左结点->右结点”，而中序遍历的顺序是“左结点->根节点->右结点”，因此，一般的思路都是酱紫的：
前序遍历列表中，第一个数据肯定是根节点，而中序遍历列表中，第一个数据肯定是树的最左结点，这样就可以得知，在前序遍历中，从根结点到最左结点一定是树的最左分支，也就是“1->2->4”；
接下来，在中序遍历中，访问完最左结点4之后因为其左结点为NULL要访问的就是4的右分支的最左结点了，为7，而在前序遍历中访问到最左结点之后就要访问右结点，发现也为7，说明7就是最左结点4的右分支上的最左结点，也就是只有7一个右结点；
然后，在中序遍历中访问完最左结点也就是以4为根节点子树之后，就要回到4结点的父节点了，也就是2，再往下访问是根节点1，也就是2并没有右结点；
至此会发现1为根节点的左子树已经全部访问完了；
上面没有再继续往下分析，是因为会发现，上面说的一堆虽然能把树给重建出来，但是很繁琐，逻辑上有关联却难以疏通个条理出来，因此要想转换为代码来实现想必又是要大费周折；
为什么分析到第四点就停下了，是因为第四点的式转换新思路的一个起点：
首先前面第一点中加粗的字体肯定是没有问题的，前序遍历中第一个数据一定是树的根结点；
再结合第四点，在中序遍历中找到这个根结点，会发现以1为根结点前面的数据都是1的左子树，有三个结点，那么在前序遍历中1后面的三个结点都是属于左子树的；因此，在1后面的数据肯定也都是在1的右子树上，有四个结点；
接下来看在前序遍历中跟在1后面的数据2是在1的左边还是右边，在左边就是1的左结点，在右边就是1的右结点；
然后按照前序遍历列表中的顺序将2看为新的根结点，那么在它左边的数据就是它左子树上的，右边的数据就是右子树上的，当然是截止到前一个根结点1为止；然后就再次循环从上一步开始；
可画图如下：
是不是会发现第二次的分析比第一次要简单明了多了？而且逻辑上有重复性，这样的分析用代码实现起来会比较容易，可以用递归来实现：
#include
#include
using namespace std;
typedef int data_type;
//首先定义一个树结点的结构体并实现构造函数
struct BinaryTreeNode
{
data_type _data;
BinaryTreeNode* _Lnode;
BinaryTreeNode* _Rnode;
BinaryTreeNode(data_type data)
:_data(data)
,_Lnode(NULL)
,_Rnode(NULL)
{}
};
//重建二叉树，参数为两个遍历列表，树结点的个数，还有递归所需要知道子树的范围
BinaryTreeNode* RebuildBinaryTree(const data_type* prevlist, const data_type *inlist, const size_t num, size_t head, size_t tail)
{
assert(prevlist && inlist && num); //判断参数有效性
//前序遍历列表中第一个结点一定是树的根结点
BinaryTreeNode *root = new BinaryTreeNode(*prevlist);
size_t root_index;
//在中序遍历列表中找出根结点
for(root_index = 0; root_index < num; ++root_index)
{
if(inlist[root_index] == *prevlist)
break;
}
if(inlist[root_index] != *prevlist) //检查给出的序列是否为有效的遍历序列
{
cout<<"Invalid parameter..."< 0)
root->_Lnode = RebuildBinaryTree(prevlist+1, inlist, num, head, root_index-1);
size_t right_node_num = tail - root_index;//根结点右边的结点个数
if(right_node_num > 0)
root->_Rnode = RebuildBinaryTree(prevlist+left_node_num+1, inlist, num, root_index+1, tail);
return root;
}
//前序遍历检查二叉树是否正确重建
void PreOrder(BinaryTreeNode *root)
{
if(root != NULL)
{
cout<_data<<"->";
PreOrder(root->_Lnode);
PreOrder(root->_Rnode);
}
}
int main()
{
data_type PrevOrderList[] = {1, 2, 4, 7, 3, 5, 6, 8};
data_type InOrderList[] = {4, 7, 2, 1, 5, 3, 8, 6};
size_t node_num = sizeof(PrevOrderList)/sizeof(PrevOrderList[0]);
//这里的首部和尾部的表示范围都是在中序遍历中
size_t head = 0;
size_t tail = node_num-1;
BinaryTreeNode* root = RebuildBinaryTree(PrevOrderList, InOrderList, node_num, head, tail);
cout<<"the root data: "<_data<运行程序：
因为只是检查书是否重建好，用递归写树的先序遍历，输出发现和给定的先序遍历序列一样，则树重建完成。
《完》
另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。
文章标题：用一棵二叉树的前序遍历结果和中序遍历结果还原这棵二叉树——6-创新互联
标题链接：http://bjjierui.cn/article/doepeo.html
