UVA 122 树的层次遍历

紫书P150

#include<bits/stdc++.h>using namespace std;const int maxn = 300;bool failed;struct Node{    bool have_value;                                      //是否被赋值过    int v;                                                //结点值    Node *left, *right;                                   //左右子结点    Node():have_value(false), left(NULL), right(NULL){}   //构造函数};Node* root;     //二叉树的根结点Node* newnode(){    //每次需要一个新的Node时，都要用new运算符申请内存，并执行构造函数    return new Node();}void remove_tree(Node* u){    if(u == NULL)   return;                              //提前判断比较稳妥    remove_tree(u->left);                                //递归释放左子树的空间    remove_tree(u->right);                               //递归释放右子树的空间    delete u;                                            //调用u的析构函数并释放u结点本身的内存}//建树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;                               //别忘记做标记}//输入char s[maxn];bool read_input(){    failed = false;    remove_tree(root);                                  //释放二叉树，避免内存泄漏    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;}//按照层次顺序遍历树vector<int>ans;bool bfs(){    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;                                        //输入正确}int main(){    while(read_input()){        if(failed || !bfs())  cout<<"not complete"<<endl;        else{            for(int i = 0;i<(int)ans.size();i++){                cout<<ans[i];                if(i == (int)ans.size()-1)  cout<<endl;                else    cout<<" ";            }        }    }    return 0;}