uva122

제목 설명:http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=19630
/* 1:newNode()           2:  c         ,     “       ”            ,     '\0' */
#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>

using namespace std;

const int maxn = 256 + 10;

struct Node {
    int val;
    Node* left, *right;
    bool valued;
    Node() : left(NULL), right(NULL), valued(false) {}
};
Node * root;

Node* newNode() {
    return new Node();      //          
}

void clear_tree(Node * n) {
    if(n == NULL)   return;
    clear_tree(n->left);
    clear_tree(n->right);
    delete n;
}

char cmd[maxn];
bool creat_failed;
bool make_tree() {      //     
    creat_failed = false;
    clear_tree(root);
    root = newNode();   //new node
    while(true) {
        if(scanf("%s", cmd) != 1)   return false;
        if(!strcmp(cmd, "()"))  break;

        int v;
        sscanf(&cmd[1], "%d", &v);       //  value 
        char * pos;
        pos = strchr(cmd, ',') + 1;       //      (                 )

        //      
        int len = strlen(pos);
        Node * r = root;
        for(int i = 0; i < len; i++) {
            if(pos[i] == 'L') {
                if(r->left == NULL)     r->left = newNode();
                r = r->left;
            }
            else if(pos[i] == 'R') {
                if(r->right == NULL)    r->right = newNode();
                r = r->right;
            }                                           //       “)”   
        }
        if(r->valued == true)   creat_failed = true;
        r->val = v;
        r->valued = true;

    }
    return true;
}

bool bfs(vector<int> &ans) {
    queue<Node*> q;
    ans.clear();
    q.push(root);

    while(!q.empty()) {
        Node* node = q.front();     q.pop();
        if(node->valued == false)   return false;
        ans.push_back(node->val);
        if(node->left != NULL)  q.push(node->left);
        if(node->right != NULL) q.push(node->right);
    }
    return true;
}

int main()
{
    vector<int> ans;    //         
    while(make_tree()) {
        ans.clear();
        if(!bfs(ans))   creat_failed = true;
        if(creat_failed) {
            printf("not complete
"
); } else { for(int i = 0; i < ans.size(); i++) { if(i != 0) printf(" "); printf("%d", ans[i]); } printf("
"
); } } return 0; }

좋은 웹페이지 즐겨찾기