예제 6-7 트리 계층 UVa122

1. 제목 설명: 링크 열기 클릭
2. 문제 풀이 사고방식: 이 문제는 두 갈래 나무를 훈련시키는 좋은 문제이다.먼저 데이터 읽기 문제를 해결하려면 제목에 따라 "()"로 입력할 때, 그룹 데이터 읽기를 끝내고, 문자열이 없을 때, 전체 입력이 끝납니다.따라서readin () 함수를 전문적으로 작성할 수 있습니다. 형식은bool형으로 설정되어 있습니다. 첫 번째 상황이 발생하면true로 돌아가고, 두 번째 상황이 발생하면false로 돌아갑니다. 메인 프로그램에서readin이false로 되돌아오는 것을 발견하면break로 전체 순환을 끝냅니다.
다음에 두 갈래 나무를 세우려면 먼저 두 갈래 나무에 구조체를 작성한 다음에 문자열의 입력 상황에 따라 나무를 짓고'L'이면 왼쪽으로 가고, 걸을 수 없을 때 새 나무를 짓는다. 같은 방법으로 오른쪽 나무를 처리하고 마지막에 결점 값을 읽는다.입력이 틀릴 수 있기 때문에 전역 변수failed로 입력 오류가 있는지 기록합니다. 트리를 만드는 과정에서 이 결점이 값을 부여한 것을 발견하면 전역 변수failed는true로 바뀝니다.
마지막으로 BFS에서 결점 값을 찾습니다. 이때 결점이 결점 값이 없는 상황이 발생할 수 있습니다. 따라서 bfs를 bool형으로 정의하고 이런 불법적인 상황이 발생하면false로 되돌려줍니다.마지막으로 상황에 따라 출력하는 것은 어렵지 않다.
3. 코드:

#define _CRT_SECURE_NO_WARNINGS 
#include<iostream>
#include<algorithm>
#include<string>
#include<sstream>
#include<set>
#include<vector>
#include<stack>
#include<map>
#include<queue>
#include<deque>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<ctime>
#include<functional>
using namespace std;

#define N 256+10
char s[N];
struct Node
{
	int v;
	bool have_value;
	Node*left, *right;
	Node() :have_value(false), left(NULL), right(NULL){}
};
Node*root;// ， 
bool failed;// 
Node*newnode(){ return new Node(); }
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;// 
}
bool readin()// 
{
	failed = false;
	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)// bfs ， vector 
{
	queue<Node*>q;
	ans.clear();
	q.push(root);
	while (!q.empty())
	{
		Node*u = q.front(); q.pop();
		if (!u->have_value)return false;// ， 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()
{
	//freopen("t.txt", "r", stdin);
	while(1)
	{
		root = newnode();
		if (!readin())break;
		vector<int>ans;
		if (!failed&&bfs(ans))
		{
			int len = ans.size();
			for (int i = 0; i < len; i++)
				printf("%d%c", ans[i], i == len - 1 ? '
' : ' ');
		}
		else puts("not complete");
	}
	return 0;
}