满江红
查看原帖
满江红
399116
LYqwq楼主2021/10/27 22:23
#include <iostream>
#include <queue>
using namespace std;
struct node{
	string val;
	node *l,*r;
	node(){
		val="kkksc03yyds"; // 初始化为"kkksc03yyds",记录是否有值
		l=r=NULL;
	}
}*root,*now;
int pos;
bool ok=1;
queue<node*> q;

void insert(string val,string lu){ // 插入节点
	now=root;
	for(int i=0,l=lu.size(); i<l; i++){
		if(lu[i]=='L'){ // L情况
			if(now->l==NULL) now->l=new node; // 新建一个结点
			now=now->l;
		}else{ // R情况
			if(now->r==NULL) now->r=new node; // 同上
			now=now->r;
		}
	}
	if(now->val=="kkksc03yyds") now->val=val; // 判断是否无值,如果有,那就出错了
	else ok=false;
}

bool check(node *kkk){ // 判断二叉树是否符合要求
	if(kkk->val=="kkksc03yyds") return 0; // 无值结点
	if(kkk->l!=NULL && !check(kkk->l)) return 0; // 左子树是否满足
	if(kkk->r!=NULL && !check(kkk->r)) return 0; // 右子树是否满足
	return 1;
}

void bfs(){ // 广搜
	q.push(root);
	cout << root->val; // 先输出
	while(!q.empty()){
		now=q.front(); q.pop();
		if(now->l!=NULL){
			cout << " " << now->l->val;
			q.push(now->l);
		}if(now->r!=NULL){
			cout << " " << now->r->val;
			q.push(now->r);
		}
	}
}

void rm(node *p){
	if(!p) return;
	rm(p->l);
	rm(p->r);
	delete p;
}

int main(){
	string s;
	while(cin >> s){ // 这一层循环有几组数据循环几次
		root=new node; // 新建结点
		while(s!="()"){ // 处理输入
			pos=s.find(',');
			// 找到val和路径
			insert(s.substr(1,pos-1),s.substr(pos+1,s.size()-pos-2));
			cin >> s; // 再输入
		}
		if(ok && check(root)){ // 判断是否符合条件
			bfs();
		}else printf("not complete"); // 不符合
		puts(""); // 换行!
		rm(root); // 最后删除结点,干净点
	}
	return 0;
}

qwq不知道哪里错了,调了几天了555
样例过了\texttt{样例过了}

2021/10/27 22:23
加载中...