#include <string>
#include <queue>
#define Notc "not complete"
using namespace std;
int to_int(char const *s)
{
if ( s == NULL || s[0] == '\0' )
{
return 0;
}
bool negate = (s[0] == '-');
if ( *s == '+' || *s == '-' )
++s;
int result = 0;
while(*s)
{
if ( *s >= '0' && *s <= '9' )
{
result = result * 10 - (*s - '0');
}
else
return 0;
++s;
}
return negate ? result : -result;
}
class node{
public:
node(){
value=-1;
bLeft=0;
bRight=0;
}
bool bLeft,bRight;
node *left,*right;
int value;
};
int LevelOrderTraversal(node *root){
queue<node*> myqueue;
queue<int> qAnswer;
myqueue.push(root);
while(!myqueue.empty()){
node *ptr=myqueue.front();
myqueue.pop();
if(ptr->value==-1){
cout<<Notc<<endl;
return 1;
}
else{
qAnswer.push(ptr->value);
if(ptr->bLeft)
myqueue.push(ptr->left);
if(ptr->bRight)
myqueue.push(ptr->right);
}
}
bool whiteSpace=false;
while(!qAnswer.empty()){
if(whiteSpace) cout<<" ";
cout<<qAnswer.front();
qAnswer.pop();
whiteSpace=true;
}
cout<<endl;
}
int main(){
string tempV,tempP,bufs;
int count_notc=0;
node *root=new node();
bool bRepeate=false;
while(cin>>bufs){
std::size_t comma=bufs.find(",",0);
if(bufs.length()==2){
if(bRepeate) {
cout<<Notc<<endl;
root->bLeft=false;
root->bRight=false;
root->value=-1;
bRepeate=false;
continue;
}
else{
LevelOrderTraversal(root);
root->bLeft=false;
root->bRight=false;
root->value=-1;
bRepeate=false;
continue;
}
}
tempV=bufs.substr(1,comma-1);
tempP=bufs.substr(comma+1,bufs.find(")",0)-comma-1);
int value=to_int(tempV.c_str());
node *ptr;
ptr=root;
if(tempP!=""){
for(int i=0;i<tempP.length();i++){
if(tempP[i]=='L'){
if(!ptr->bLeft){
ptr->left=new node();
ptr->bLeft=true;
}
ptr=ptr->left;
}
else if(tempP[i]=='R'){
if(!ptr->bRight){
ptr->right=new node();
ptr->bRight=true;
}
ptr=ptr->right;
}
}
}
if(ptr->value!=-1){
bRepeate=true;
continue;
}
else
ptr->value=value;
}
return 0;
}
沒有留言:
張貼留言