UVa 712 - S-Trees解题报告

一道简单二叉树问题，但是要读懂题目意思不容易。

题意：给你一棵二叉树，还有一个序列，如001，对于深度为3的树，第一个0表示在根节点处向左孩子，第二个0表示在第二层处向左孩子，1表示在第三层向右孩子。输出到达叶子节点的值。这道题跟一道小球下落的题目是一样的。

思路：根据给出的n建立二叉树，模拟即可。其中对于节点的方向可以利用map建立映射。另一个思路是用数组模拟，事实上这个过程跟二分很像。

这里我用的是建树模拟，为了熟悉二叉树的建立和遍历。

#include <iostream>
#include <cstring>
#include <map>
#include <cstdlib>
#include <string>
using namespace std;
struct BinTree
{
	char name[10];
	char ch = 0;
	BinTree *left = NULL, *right = NULL;
};
BinTree *CreatTree(BinTree *, char *, int, int);
char found(map<char*, char> &, BinTree *, int);
int cmp(const void *_a, const void *_b)
{
	char *a = (char*)_a;
	char *b = (char*)_b;
	return strcmp(a, b);
}
char nobe[130][10];//存储节点名称
char str[260], command[10];
int i;
int main()
{
	//freopen("data.txt", "r", stdin);
	int n;
	int cases = 1;
	while (scanf("%d", &n) && n)
	{
		for(int i = 0; i < n; i++)
			scanf("%s", nobe[i]);
		scanf("%s", str);
		BinTree *root = NULL;
		i = 0;
		root = CreatTree(root, str, n, 0);
		
		int m;
		scanf("%d", &m);
		printf("S-Tree #%d:\n", cases++);
		for(int i = 0; i < m; i++)
		{
			scanf("%s", command);
			
			qsort(nobe, n, sizeof(nobe[0]), cmp);//对命令进行排序
			map<string, char> s;//建立映射各个节点的命令

			for(int j = 0; j < n; j++)
			{
				string a = nobe[j];//@这里我之前用的是char*，后来发现这样映射的是指针，而不是字符串。用string才行
				s[a] = command[j];
			}
				
			BinTree * tmp = root;
			for(int k = 0; k < n; k++)//遍历树
			{
				string b = tmp->name;
				if(s[b] == '0')
					tmp = tmp->left;
				else
					tmp = tmp->right;
			}
			printf("%c", tmp->ch);
		}
		printf("\n\n");
	}
	return 0;
}

BinTree *CreatTree(BinTree *root, char *str, int n, int level)
{
	if(level == n + 1)//到达最后一层
		return NULL;
	root = new BinTree;
	if(level == n)
		root->ch = str[i++];//到达叶子节点
	else
		strcpy(root->name, nobe[level]);//叶子节点之上的节点
	root->left = CreatTree(root->left, str, n, level + 1);
	root->right = CreatTree(root->right, str, n, level + 1);
	return root;
}