首页 > 代码库 > 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;}
HDU 1622
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。