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

UVA122 树的层次遍历 Trees on the level

程序员文章站 2022-03-11 20:58:35
...

题目描述

UVA122 树的层次遍历 Trees on the level

输入格式

UVA122 树的层次遍历 Trees on the level

输出格式

UVA122 树的层次遍历 Trees on the level

输入

(11,LL) (7,LLL) (8,R)
(5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR) ()
(3,L) (4,R) ()

输出

5 4 8 11 13 4 7 2 1
not complete
#include<bits/stdc++.h>
#define read() freopen("input.txt","r",stdin);
#define write() freopen("output.txt","w",stdout);
using namespace std;
const int maxn = 105;
struct node{
	bool have_value;
	int v;
	node* left,* right;
	node():have_value(false),v(0),left(NULL),right(NULL){}
};
void remove_tree(node *p) {
    if(p == NULL) return ;
    remove_tree(p->left);
    remove_tree(p->right);
    delete p;
}
node* newnode(){ return new node();}
node* root;
bool failed;
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;
}
char s[maxn];
bool readinput(){
	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;
}
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;
}
vector<int>ans;
int main()
{
	read();write();
	while(readinput()) {
        if(failed || !bfs(ans)) {
            printf("not complete");
        }else {
            for( int i=0; i<ans.size(); i++ ){
				if(i) printf(" ");printf("%d",ans[i]);
			}
        }
        printf("\n");
    }
    return 0;
}