UVA 122(フォークツリー+文字列入力)

2007 ワード

件名:
一本の二叉の木の上のいくつかのノードの値(全部正数)をあげて、ルートからすべての所与の点までの経路上のノードに値があるかどうかを判断して、一回だけ与えられます.
この問題は難しくないです.主に細かいところの処理です.勉強してください.
#include
using namespace std;
#define inf 0x3f3f3f3f
#define ll long long
const int maxn=200005;
const double eps=1e-8;
const double PI = acos(-1.0);
#define lowbit(x) (x&(-x))
struct node
{
    int v;
    bool have_value;
    node *left,*right;
    node():have_value(false),left(NULL),right(NULL) {}
};
node *root;
bool fail;
node *newnode()
{
    return new node();
}
char s[1000];
void addnode(int v,char *s)
{
    int n=strlen(s);
    node *u=root;
    for(int i=0; ileft==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)
        fail=true;
    u->v=v;
    u->have_value=true;
}
bool read()
{
    fail=false;
    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;
}
bool bfs(vector &ans)
{
    queue 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)
            q.push(u->left);
        if(u->right)
            q.push(u->right);
    }
    return true;
}
int main()
{
    while(1)
    {
        root=newnode();
        if(!read())
            break;
        vector ans;
        if(!fail&&bfs(ans))
        {
            int len=ans.size();
            for(int i=0; i