重建二叉树---根据前序和中序遍历结果重建二叉树
一颗二叉树：
前序遍历结果： abdcef
中序遍历结果：dbaecf
基于递归的思想：在前序遍历中的第一个结点是根结点，然后在中序遍历中找到此根节点，然后递归的对左右子树分别重建。
顺说一下，知道前序和后序遍历结果，我无法重建二叉树的，因为当某个结点只有一个儿子结点的时候，无法区分出到底是左还是右结点。
#include <iostream>#include <cstring>using namespace std;struct Binode{ char data; Binode *lhs; Binode *rhs;};void Rebuild_tree(char *preorder,char *inorder,int len,Binode *& root){if(preorder==NULL || inorder==NULL) return ;// 检查边界条件root=new Binode;root->data=preorder[0]; //前序遍历的第一个结点作为根结点。 root->lhs=root->rhs=NULL;if(len==1) return ; //当前树的长度为1，那么已经是最后一个结点。int leftlen=0;char *pleftend=inorder;while(*preorder!=*pleftend){if(preorder==NULL || pleftend==NULL) return ;pleftend++;} leftlen=(int)(pleftend-inorder); //左子树长度int rightlen=len-leftlen-1; //右子树长度 //重建左子树 if(leftlen>0){Rebuild_tree(preorder+1,inorder,leftlen,root->lhs);} //重建右子树 if(rightlen>0){Rebuild_tree(preorder+leftlen+1,pleftend+1,rightlen,root->rhs);}}void Post_Traversal(Binode *root){if(root->lhs) Post_Traversal(root->lhs);if(root->rhs) Post_Traversal(root->rhs);cout<<root->data<<" ";}int main(){ char *preorder="abdcef"; char *inorder="dbaecf"; int len=strlen(inorder); Binode *root; Rebuild_tree(preorder,inorder,len,root); Post_Traversal(root);return 0;}