UVa 122 - Trees on the level

题目：给你一颗二叉树上面的若干节点上的值（均为正数），判断从根到所有的给定的点的路径上的节点，

            是不是都有值，且只被赋值一次。

分析：递归，搜索，树。

            首先，利用递归建树，过程中记录是否有节点赋值两次；

            然后，利用递归判断，查找是否有未被赋值的节点；

            最后，利用bfs安深度输出每层的值。

说明：强大的sscanf函数╮(╯▽╰)╭。

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>

using namespace std;

typedef struct tnode
{
	int    V;
	tnode* L;
	tnode* R;
}tree;
tree node[300];
tree*root;
int  tree_size,complete;

int test(tree *root)
{
	if (!root->V) return 0;
	int ans = 0;
	if (!root->L || test(root->L))
		ans ++;
	if (!root->R || test(root->R))
		ans ++;
	return ans == 2;
}

void madetree(tree *root, char* str, int v)
{
	if (*str == 'R') {
		if (!root->R)
			root->R = &node[++ tree_size];
		madetree(root->R, str+1, v);
	}else if (*str == 'L') {
		if (!root->L)
			root->L = &node[++ tree_size];
		madetree(root->L, str+1, v);
	}else {
		if (root->V)
			complete = 0;
		root->V = v;
	}
}

tree*Q[300];
void output(tree *root)
{
	int move = 0,save = 0;
	Q[save ++] = root;
	printf("%d",root->V);
	while (move < save) {
		tree* now = Q[move ++];
		if (now->L) {
			printf(" %d",now->L->V);
			Q[save ++] = now->L;
		}
		if (now->R) {
			printf(" %d",now->R->V);
			Q[save ++] = now->R;
		}
	}printf("\n");
}

int main()
{
	char buf[256],leaf[256];
	int  value;
	
	complete = 1;
	root = &node[tree_size = 0];
	while (~scanf("%s",buf)) {
		if (!strcmp(buf,"()")) {
			if (!complete || !test(root))
				printf("not complete\n");
			else output(root);
			
			memset(node, 0, sizeof(node));
			root = &node[tree_size = 0];
			complete = 1;
		}else {
			sscanf(buf,"(%d,%s",&value,leaf);
			madetree(root, leaf, value);
		}
	}
    return 0;
}

UVa 122 - Trees on the level

原文：http://blog.csdn.net/mobius_strip/article/details/44629873