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;
}