题意:输入文件尾个序列形如(data,左子树or 右子树),然后让你层次遍历它,如果出现存在某个节点的父节点不存在或者某个节点出现多次,输出:not complete。
难点:输入和建树
wa了一次貌似是没有把树释放。
然后学到两个函数
sscanf(&s[1],"%d",&v);//从char[]中第1个元素开始中的数字部分读入int型变量v
strchr(s,’,’)+1//截取char[]从,后面的字符
代码:
#include<iostream>
#include<string.h>
#include<queue>
#include<string>
using namespace std;
const int maxn=1e3+10;
char s[maxn];
struct node{
int v;
node *l,*r;
bool aleardy;
node():v(0),l(NULL),r(NULL),aleardy(false){}
};
node* newnode(){
return new node();
}
node *root=newnode();
bool addnode(int v,char s[]){
int len=strlen(s);
node *p=root;
for(int i=0;i<len;i++){
if(s[i]=='L'){
if(p->l==NULL){
p->l=newnode();
}
p=p->l;
}else if(s[i]=='R'){
if(s[i]=='R'){
if(p->r==NULL){
p->r=newnode();
}
p=p->r;
}
}
}
if(p->aleardy)return false;
p->v=v;
p->aleardy=true;
return true;
}
bool bfs(){
queue<node>st;
st.push(*root);
if(!root->aleardy)return false;
cout<<root->v;
int flag=0;
while(!st.empty()){
node now=st.front();
if(!now.aleardy)return false;
if(flag)
cout<<" "<<now.v;
flag=1;
st.pop();
if(now.l!=NULL){
st.push(*now.l);
}
if(now.r!=NULL){
st.push(*now.r);
}
}
cout<<endl;
return true;
}
int main(){
while(scanf("%s",s)!=EOF){
root=newnode();
bool flag=true;
int v;
sscanf(&s[1],"%d",&v);
if(addnode(v,strchr(s,',')+1)==false){flag=false;}
for(;;){
if(scanf("%s",s)!=1){flag=false;}
if(!strcmp(s,"()"))break;
int v;
sscanf(&s[1],"%d",&v);
if(addnode(v,strchr(s,',')+1)==false){flag=false;}
}
if(flag==false){
cout<<"not complete"<<endl;
}else{
if(!bfs())cout<<"not complete"<<endl;
}
// destory(root);
}
}