| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
水题~~#include <iostream>
#include <string>
using namespace std;
struct BTreeNode
{
char data;
BTreeNode *LChild;
BTreeNode *RChild;
};
void PostOrder(BTreeNode *BTree);
BTreeNode *RecoveryTree(string s1, string s2);
void DestroyTree(BTreeNode *&BTree);
int main()
{
string s1, s2;
while (cin >> s1 >> s2)
{
BTreeNode *BT = RecoveryTree(s1, s2);
PostOrder(BT);
cout << endl;
DestroyTree(BT);
}
return 0;
}
void PostOrder(BTreeNode *BTree)
{
if (BTree != NULL)
{
PostOrder(BTree -> LChild);
PostOrder(BTree -> RChild);
cout << BTree -> data;
}
}
BTreeNode *RecoveryTree(string s1, string s2)
{
BTreeNode *Root = new BTreeNode;
Root -> data = s1[0];
Root -> LChild = NULL;
Root -> RChild = NULL;
int index = 0;
for (int i=0; i<s2.size(); i++)
{
if (s2[i] == s1[0])
{
index = i;
break;
}
}
if (index > 0)
Root -> LChild = RecoveryTree(s1.substr(1, index), s2.substr(0, index));
if (index < int(s2.size()-1))
Root -> RChild = RecoveryTree(s1.substr(index+1), s2.substr(index+1));
return Root;
}
void DestroyTree(BTreeNode *&BTree)
{
if (BTree != NULL)
{
DestroyTree(BTree -> LChild);
DestroyTree(BTree -> RChild);
delete BTree;
BTree = NULL;
}
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator