UVA 122 二叉树模拟_二叉树 模拟网站

题意：输入一棵二叉树，层序遍历输出二叉树的节点值，结点规模256，如果有结点没有被赋值或者被赋2次以上的值，则输出not complete（照着书做的时候书上输出-1导致程序一直WA）

使用数组模拟二叉树更加简单和方便

#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<vector>
#include<stack>
#include<queue>
#include<algorithm>
#include<sstream>
#define inf 0x3f3f3f3f
#define ll long long
using namespace std;
const int MAXN=300;
int l[MAXN];//存储左结点
int r[MAXN];//存储右节点
int value[MAXN];//存储节点的值
int flag[MAXN];
int cnt;
int newnode()//建立新节点
{
    int u=++cnt;
    l[u]=r[u]=0;
    flag[u]=0;
    return u;
}
int addnode(int v,char *s)
{
    int n=strlen(s);
    int u=1;
    for(int i=0;i<=n-2;i++)
    {
        if(s[i]=='L')
        {
            if(l[u]==0)
                l[u]=newnode();
            u=l[u];
        }
        else
        {
            if(r[u]==0)
                r[u]=newnode();
            u=r[u];
        }
    }
    if(flag[u]==1)
        return -1;
    flag[u]=1;
    value[u]=v;
    return 0;
}
void bfs()
{
    queue<int> q;
    queue<int> qx;
    while(!q.empty())
        q.pop();
    while(!qx.empty())
        qx.pop();
    q.push(1);
    bool ff=0;
    while(!q.empty())
    {
        int t=q.front();
        q.pop();
        if(flag[t]==0)
        {
            ff=1;
            break;
        }
        qx.push(value[t]);
        if(l[t]!=0)
            q.push(l[t]);
        if(r[t]!=0)
            q.push(r[t]);
    }
    if(ff==1)
        cout<<"not complete"<<endl;
    else
    {
        cout<<qx.front();
        qx.pop();
        while(!qx.empty())
        {
            cout<<" "<<qx.front();
            qx.pop();
        }
        cout<<endl;
    }
}
int main()
{
    char s[MAXN];
    while(scanf("%s",s)==1)
    {
        if(strcmp(s,"()")==0)
            continue;
        l[1]=r[1]=0;
        flag[1]=0;
        cnt=1;
        int v;
        sscanf(&s[1],"%d",&v);
        addnode(v,strchr(s,',')+1);
        bool f=0;
        while(scanf("%s",s))
        {
            if(strcmp(s,"()")==0)
                break;
            int v;
            sscanf(&s[1],"%d",&v);
            int x=addnode(v,strchr(&s[1],',')+1);
            if(x==-1)
                f=1;
        }
        if(f==1)
            cout<<"not complete"<<endl;
        else
            bfs();
    }
    return 0;
}