二叉树——UVA122

二叉树的层次遍历

#include <iostream>
#include <string>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;



struct Node{
    bool have_value;
    int v;
    struct Node* left,*right;
    Node():have_value(false),left(NULL),right(NULL){}
};
const int maxn = 256;
bool failed;
char s[10000];

Node *root = NULL;


Node* newnode(){
    return new Node();
}


void addnode(int v,char *s){
    int n = strlen(s);
    Node* u = root;
    for(int i = 0;i <n;i++)
        if(s[i] == 'L'){
            if(u->left == NULL) u->left = newnode();
            u = u->left;
        }
        else if(s[i] == 'R'){
            if(u->right == NULL) u->right = newnode();
            u = u->right;
        }
    if(u->have_value) failed = true;
    u->v = v;
    u ->have_value = true;
}

bool bfs(vector<int>& ans){
    queue<Node*> q;
    ans.clear();
    q.push(root);
    while(!q.empty()){
        Node * u = q.front();
        q.pop();
        if(!u->have_value) return false;
        ans.push_back(u->v);
        if(u->left != NULL)
            q.push(u->left);
        if(u->right != NULL)
            q.push(u->right);
    }
    return true;
}



bool read(){
    failed = false;
    root = newnode();
    for(;;){
        if(scanf("%s",&s) != 1)  return false;
        if(!strcmp(s,"()")) break;
        int v;
        sscanf(&s[1],"%d",&v);
        addnode(v,strchr(s,',')+1);
    }
    return true;
}

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

int main(){
    //freopen("in.txt","r",stdin);
    char s[maxn];
    while(1){
        if(!read()) break;
        vector<int>ans;
        if(!failed && bfs(ans)){
            int len = ans.size();
            for(int i = 0;i < len;i++)
                printf("%d%c",ans[i],i == len-1?'
':' ');
        }else printf("not complete
");
    }

    remove_tree(root);
    return 0;
}

参考资料：
[1].《算法竞赛入门经典（第二版）》
[2].http://blog.csdn.net/u014800748/article/details/44733017