首页 > 代码库 > HDU 1622

HDU 1622

http://acm.hdu.edu.cn/showproblem.php?pid=1622

白书上6.3.2二叉树层次遍历的例题,层次遍历用bfs,建立二叉树,很基础的题目

#include <iostream>#include <cstdio>#include <cstdlib>#include <cstring>#include <queue>using namespace std;struct node{    int vis,v;    node *l,*r;};node *root;node* newnode(){    node *u=new node;    if(u!=NULL){        u->vis=0;        u->l=u->r=NULL;    }    return u;}int failed;void addnode(int v,char* s){    int len=strlen(s);    node* u=root;    for(int i=0;i<len;i++){        if(s[i]==L){            if(u->l==NULL)u->l=newnode();            u=u->l;        }        else if(s[i]==R){            if(u->r==NULL)u->r=newnode();            u=u->r;        }    }    if(u->vis)failed=1;    u->v=v;    u->vis=1;}char s[305];void remove_tree(node* u){    if(u==NULL)return;    remove_tree(u->l);    remove_tree(u->r);    delete u;}int input(){    failed=0;    remove_tree(root);    root=newnode();    while(1){        if(scanf("%s",s)==EOF)return 0;        if(!strcmp(s,"()"))break;        int v;        sscanf(&s[1],"%d",&v);        addnode(v,strchr(s,,)+1);    }    return 1;}int st,ans[305];int bfs(){    queue <node*> q;    q.push(root);    while(!q.empty()){        node* u=q.front();        q.pop();        if(u->vis==0)return 0;        ans[st++]=u->v;        if(u->l!=NULL)q.push(u->l);        if(u->r!=NULL)q.push(u->r);    }    return 1;}int main(){    while(input()){        if(failed)puts("not complete");        else{            st=0;            if(!bfs())puts("not complete");            else{                for(int i=0;i<st;i++){                    if(!i)                        printf("%d",ans[i]);                    else                         printf(" %d",ans[i]);                }                putchar(\n);            }        }    }    return 0;}
View Code

 

HDU 1622