已知二叉树的前序与中序遍历创建二叉树-白红宇

已知二叉树的前序与中序遍历创建二叉树

阅读量：5009 次

发布时间：2019-06-12

本文共 1378 字，大约阅读时间需要 4 分钟。

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 using namespace std; 6 struct Node 7 { 8     char data; 9     Node *lchild;10     Node *rchild;11 };12 Node *CreatTree(string pre,string in)13 {14     Node *root=NULL;15     if(pre.length()>0)16     {17         root=new Node;18         root->data=pre[0];19         int index=in.find(root->data);20         root->lchild=CreatTree(pre.substr(1,index),in.substr(0,index));21         root->rchild=CreatTree(pre.substr(index+1),in.substr(index+1));22     }23     return root;24 }25 void Preorder(Node *root)26 {27     if(root)28     {29         putchar(root->data);30         Preorder(root->lchild);31         Preorder(root->rchild);32     }33 }34 void Inorder(Node *root)35 {36     if(root)37     {38         Inorder(root->lchild);39         putchar(root->data);40         Inorder(root->rchild);41     }42 }43 void Postorder(Node *root)44 {45     if(root)46     {47         Postorder(root->lchild);48         Postorder(root->rchild);49         putchar(root->data);50     }51 }52 int main()53 {54     Node *root;55     string pre,in;56     while(cin>>pre>>in)57     {58         root=CreatTree(pre, in);59         Postorder(root);60         putchar('\n');61     }62     return 0;63 }