1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253 |
- #include <bits/stdc++.h>
- using namespace std;
- typedef struct BinTree
- {
- char data;
- BinTree* lchild;
- BinTree* rchild;
- } BinTree;
- void RebuildTree(BinTree* &Tree,char *pre,char *in,int len)
- {
- Tree = new BinTree;
- if(Tree!=NULL)
- {
- if(len<=0)//递归截止条件
- {
- Tree = NULL;
- return ;
- }
- int index = 0;
- while(index<len&&*(pre)!=*(in+index))
- {
- //寻找当前的root结点(包含子树)
- index++;
- }
- Tree->data = *(pre);
- RebuildTree(Tree->lchild,pre+1,in,index);//去掉root结点
- RebuildTree(Tree->rchild,pre+1+index,in+1+index,len-(index+1));//去掉左边和根节点
- }
- return ;
- }
- void PostOrderTravese(BinTree* Tree)
- {
- //后序遍历输出
- if(Tree==NULL)
- return;
- PostOrderTravese(Tree->lchild);
- PostOrderTravese(Tree->rchild);
- cout<<Tree->data;
- }
- int main()
- {
- char pre[101]; //string pre;
- char in[101]; //string in;
- while(cin>>pre>>in)
- {
- BinTree* tree;
- int length = strlen(pre);
- RebuildTree(tree,pre,in,length);
- PostOrderTravese(tree);
- cout<<endl;
- }
- return 0;
- }
|