欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

树的层次遍历

程序员文章站 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;
}