uva-122 樹的層次遍歷

uva-122 樹的層次遍歷

題意概要：輸入二叉樹的每一個節點的信息，建樹完畢後，按照層次順序遍歷這棵樹，然後將每一個節點的權值給輸出來！

注意：如果從根到某個葉節點的路徑上有的節點沒有在輸入中給出或者給出超過一次，

應該輸出“not complete”.節點數不超過256個！

代碼如下：（代碼中有詳細的注釋！）此份代碼用時為 9ms ！

#include
#include
#include
#include
#include
using namespace std;
const int maxn=52014;
char str[maxn];
bool failed=false;
vectorans;
struct Node//節點結構體！
{
    bool have_value;
    int value;
    Node *left,*right;
    Node():have_value(false),value(0),left(NULL),right(NULL) {}
};
struct Node *root;//建立根節點！
void remove_tree(Node *now)//將樹所占用的內存釋放掉！
{
    if(now==NULL)
        return ;
    remove_tree(now->left);
    remove_tree(now->right);
    delete now;
}
Node *newnode()//建立新節點！
{
    return new Node();
}
void addnode(int num,char *s)//增加節點，同時賦值！
{
    int len=strlen(s);
    Node *now=root;
    for(int i=0; ileft==NULL)
                now->left=newnode();//建立心新節點！
            now=now->left;
        }
        else if(s[i]=='R')
        {
            if(now->right==NULL)
                now->right=newnode();//建立新節點！
            now=now->right;
        }
    }
    if(now->have_value)failed=true;//如果該節點已經賦值了，那麼表示輸入有誤！
    now->value=num;//給節點賦值！
    now->have_value=true;//標記該節點已經賦值了！
}
bool input()//將樹j節點的信息給輸入！
{
    failed=false;
    root=newnode();
    while(1)
    {
        if(scanf("%s",str)!=1)return false;//錯誤輸入
        if(!strcmp(str,"()"))break;//結束輸入！
        int num;//對於字符串“(11,,LL)”來說，
        sscanf(&str[1],"%d",&num);//此操作是取出節點權值【11】！
        addnode(num,strchr(str,',')+1);//strchr(str,',')函數是
        //返回字符串str中從左到右第一個字符‘，’的指針，因此strchr(str,',')+1所對應的字符串就是"LL)".
    }
    return true;
}
bool bfs()
{
    queueQ;//建立隊列！
    Q.push(root);
    ans.clear();//將容器初始化！
    while(!Q.empty())
    {
        Node *now=Q.front();
        Q.pop();
        if(!now->have_value)
            return false;//如果這個節點的值還沒有的話，那麼表示輸入有誤！
        ans.push_back(now->value);//將值存進容器！
        if(now->left!=NULL)
            Q.push(now->left);
        if(now->right!=NULL)
            Q.push(now->right);
    }
    return true;
}
void print()
{
    for(int i=0; i