树的层次遍历
程序员文章站
2022-03-14 17:52:25
...
网址:https://vjudge.net/contest/243027#problem/G
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=300;
char s[maxn];
bool failed;
vector<int>a;
struct Node{
bool have_value;
int v;
Node *left,*right;
Node():have_value(false),left(NULL),right(NULL){}
};
Node* root;
Node* newnode(){
return new Node;
}
//ok
void addnode(int v,char* s){
int n=strlen(s);
Node *u=root;
for(int i=0;i<n;i++)
{if(s[i]=='L')
{ if(u->left==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)failed=true;
u->v=v;
u->have_value=true;
}
void remove_tree(Node* u)
{ if(u==NULL)return;
remove_tree(u->left);
remove_tree(u->right);
delete u;
}
//ok
bool read_input()
{ failed=false;
remove_tree(root);
root=newnode();
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;
}
//ok
bool bfs(vector<int>& ans)
{queue<Node*>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!=NULL)q.push(u->left);
if(u->right!=NULL)q.push(u->right);
}
return true;
}
int main()
{ while(read_input())
{ if(bfs(a)&&!failed)
{for(int i=0;i<a.size();i++)
{ if(i>0)printf(" ");
printf("%d",a[i]);
}
printf("\n");
}
else
{printf("not complete\n"); }
}
return 0;
}