Tree Recovery--POJ 2255

6322 단어 tree
1. 제목 유형: 두 갈래 나무가 두루 다닌다.
2. 문제 풀이 사고방식: 이미 알고 있는 두 갈래 나무의 앞 순서가 두루 다니고, 중간 순서가 두루 다니며, 뒷 순서가 두루 다니기를 구한다.
3. 주의사항: 두 갈래 나무 구조에서 귀속적인 사용.
4. 구현 방법:

  
    
#include < iostream >
#include
< string >
using namespace std;

struct Node{
char data;
Node
* lchild;
Node
* rchild;
};

string prestr,midstr;

Node
* CreateTree( string pre, string mid)
{
Node
* root = NULL;
if (pre.length() > 0 )
{
root
= new Node;
root
-> data = pre[ 0 ];
int index = mid.find(root -> data);
root
-> lchild = CreateTree(pre.substr( 1 ,index),mid.substr( 0 ,index));
root
-> rchild = CreateTree(pre.substr(index + 1 ),mid.substr(index + 1 ));
}
return root;
}

void PostOrder(Node * root)
{
if (root != NULL)
{
PostOrder(root
-> lchild);
PostOrder(root
-> rchild);
cout
<< root -> data;
}
}
int main()
{
while (cin >> prestr >> midstr)
{
Node
* tmp = CreateTree(prestr,midstr);
PostOrder(tmp);
cout
<< endl;
}
return 1 ;
}

좋은 웹페이지 즐겨찾기