二叉树的层次遍历 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#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?'\n':' ');
        }else printf("not complete\n");
    }

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