学步园

#include <iostream>
#include <string>
#include <stack>
#include <queue>

using namespace std;
struct Node {
char ch;
Node * left;
Node * right;
};
Node * root=NULL;

bool CreateBiTree(string Pre,string In,Node *& p)
{
 if(Pre.empty()&&In.empty()) return true;
 else if(Pre.empty()&&!In.empty()||!Pre.empty()&&In.empty()) return false;
 else
 {
  if(In.find(Pre[0])==-1)
   return false;
  int temp=In.find(Pre[0]);
  bool flag1,flag2;
  string pre1,pre2,in1,in2;
  if(temp!=0)
   in1=In.substr(0,temp);
  if(temp!=In.length()-1)
   in2=In.substr(temp+1,In.length()-temp-1);
  if(!in1.empty())
   pre1=Pre.substr(1,in1.length());
  if(!in2.empty())
   pre2=Pre.substr(1+in1.length(),in2.length());
  p=new Node;
  p->ch=Pre[0];
  p->left=NULL;p->right=NULL;
  flag1=CreateBiTree(pre1,in1,p->left);
  flag2=CreateBiTree(pre2,in2,p->right);
  return flag1&&flag2;

 }
}
void freeBiTree(Node * root)
{
 if(root==NULL) return;
 freeBiTree(root->left);
 freeBiTree(root->right);
 delete root;
}
void PreTraverse(Node * root)
{
    if(root==NULL) return;
 cout<<root->ch;
 PreTraverse(root->left);
 PreTraverse(root->right);
}
void main()
{
 string PreOrder;
 string InOrder;
 cin>>PreOrder>>InOrder;
 if(CreateBiTree(PreOrder,InOrder,root))
  PreTraverse(root);
 else
 {
  freeBiTree(root);
  root=NULL;
  cout<<"输入序列不正确！\n";
 }

 ::system("pause");
}