题目：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如：输入前序遍历 {1,2,4,7,3,5,6,8} 和中序遍历序列 {4,7,2,1,5,3,8,6}，则重建出图2.6所示的二叉树并输出它的头结点。
对于这个问题，可以分成三步：
1、首先拿到前序遍历序列，其作用就是用来取得根节点。（需要理解，二叉树是一个递归的过程，其子树亦是一个二叉树，每一次都是取得 二叉树的根节点）
2、找到 “前序遍历中取得的根节点” 在中序遍历序列中的位置
3、找到该位置后，就可以确定 该根节点 所接的左右子树，然后对这 子 二叉树进行递归操作。
这样又从第一步开始了，依次取得每一棵子二叉树的根节点。从而完成整棵树的重建。
代码如下：
/*重建二叉树：根据二叉树的前序遍历和中序遍历，重构出二叉树，并输出后序遍历。递归法实现。*/#include<iostream>using namespace std;//定义二叉树节点的结构体struct BiTreeNode{ int value; BiTreeNode *lchild; //使用二叉链表存储左右子树 BiTreeNode *rchild;};/*递归重构二叉树*/BiTreeNode *ConstructCore(int *startPreorder,int *endPreorder,int *startInorder, int *endInorder){ //根据前序遍历找到根节点 int rootValue=startPreorder[0]; BiTreeNode *root=new BiTreeNode(); root->value=rootValue; root->lchild=NULL; root->rchild=NULL; //判断前序和中序输入是否合法 if(startPreorder==endPreorder) { if(startInorder==endInorder && *startPreorder==*startInorder) return root; else cout<<"Invalid Input!"; } //在中序遍历中找到根节点的位置 int *rootInorder=startInorder; //初始化为中序遍历的第一个节点 while(rootInorder<=endInorder && *rootInorder!=rootValue) ++rootInorder; if(rootInorder==endInorder && *rootInorder!=rootValue) //查找到最后仍未找到根节点 cout<<"Invalid Input!"; int leftLength=rootInorder-startInorder; int *leftPreorderEnd=startPreorder+leftLength; //构建左子树 if(leftLength>0) root->lchild=ConstructCore(startPreorder+1,leftPreorderEnd,startInorder,rootInorder-1); //构建右子树 if(leftLength<endInorder-startInorder) root->rchild=ConstructCore(leftPreorderEnd+1, endPreorder,rootInorder+1,endInorder); return root; } /*重构二叉树函数*/ //BiTreeNode *Construct(int preorder[],int inorder[],int length)BiTreeNode *Construct(int *preorder,int *inorder,int length){ if(preorder==NULL || inorder==NULL || length<=0) //若前序数组或中序数组为空 return NULL; return ConstructCore(preorder,preorder+length-1,inorder,inorder+length-1);//调用重构二叉树函数 }/*二叉树后序遍历*/ void postorder(BiTreeNode *root){ if(root==NULL) return; else { postorder(root->lchild); postorder(root->rchild); cout<<root->value<<" "; }}int main(){ int preorder[8]={1,2,4,7,3,5,6,8}; int inorder[8]={4,7,2,1,5,3,8,6}; cout<<"该二叉树的前序遍历：" ; for(int i=0;i<8;i++) cout<<preorder[i]<<" "; cout<<endl; cout<<"该二叉树的中序遍历：" ; for(int i=0;i<8;i++) cout<<inorder[i]<<" "; cout<<endl; BiTreeNode *root=Construct(preorder,inorder,8); cout<<"该二叉树的后序遍历：" ; postorder(root); return 0;} 版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/162926.html
