Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

水题~~

Posted by frankLEE at 2015-05-04 21:27:43 on Problem 2255
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator