UVa122二叉樹的層次遍歷

二叉樹的存儲結構，可以采取順序存儲和鏈式存儲。順序存儲對于完全二叉樹來說不浪費空間而且各種運算簡單，求雙親求孩子都是常量算法；對于二叉樹來說，浪費空間的情況下求雙親和求孩子仍然是常量，但是對于單支樹來說浪費大。

采用鏈式存儲，可以用二叉鏈表和三叉鏈表。二叉鏈表的結點類就是指向左孩子的指針lchild，數據值data和指向右孩子的指針rchild。二叉鏈表的情況下，求孩子是常量算法，求雙親是一階算法（所有點走一遍）。三叉鏈表的結點類是在二叉鏈表的基礎上多了一個parent指針，這樣使得找雙親也成為常量算法。

鏈式存儲都可以考慮靜態結構和動態結構。靜態結構就是數組，看房間號。靜態鏈表結構是利用數組定義，數組名就是指針常量，運算過程中存儲空間大小不變，指針為數組下標。線性表和二叉樹這種非線性結構的存儲方式都會考慮順序存儲和鏈式存儲這兩種方式。其實就是前驅共不共享和最后一個元素有幾個的區別。所以數據結構就是畫出一個圖，就對一種寫法。

二叉樹的遍歷，有n個結點就有n!種遍歷方式，研究其中有規律的方式。層次遍歷就是從上到下從左到右。樹就是圖，圖的深度優先遍歷和廣度優先遍歷都不唯一，因為起點的選擇不同，路徑的選擇也不同，二叉樹以根結點為起點是定下來。圖的廣度優先遍歷其實就是圖對應廣度優先生成樹的層次遍歷，因此可以用隊列實現。

對于這道題目來說，靜態結構的順序存儲肯定是存不下了，單支樹的256個結點，編號會大到\(2^{255}\)這么多去。因此，不使用順序存儲，采用鏈式存儲。

對于所有的鏈式結構，都是兩個類，一個鏈表類一個結點類。

輸入數據就是告訴建樹方式，層次遍歷就是讀樹輸出的方式。

讀入方式也很值得學習，以空格為分界來讀，再使用sscanf從字符串中讀出整數值。這樣做就避免了自己寫狀態機來處理。

注意在層次遍歷的時候，要判斷有沒有孩子，也就是沒有訪問過的孩子是沒找到還是沒找完。

使用靜態結構的代碼如下。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int MAXN = 260;
char s[10010];
int root = 1;
int cnt = 1; // 目前所有結點的最大編號 
int lchild[MAXN], rchild[MAXN];
int data[MAXN]; // 如果數據值可以是負數和0，所以要記錄是否賦值過
bool have_value[MAXN]; 
bool failed = false;
int cnt_ans = 0;
int ans[MAXN];
bool vis[MAXN];

void Init() {
	memset(lchild, 0, sizeof(lchild));
	memset(rchild, 0, sizeof(rchild));
	memset(data, 0, sizeof(data));
	memset(have_value, 0, sizeof(have_value));
	memset(vis, 0, sizeof(vis));
	root = 1;
	cnt = 1; 
	lchild[root] = 0;
	rchild[root] = 0; 
	failed = false;
	return; 
}

void addnode(int v, char* s) {
	int n = strlen(s);
	int p = root;
	for (int i = 0; i < n; i++) {
		if (s[i] == 'L') {
			if (lchild[p] == 0) {
				lchild[p] = ++cnt;
			}
			p = lchild[p];
		} else if (s[i] == 'R') {
			if (rchild[p] == 0) {
				rchild[p] = ++cnt;
			}
			p = rchild[p];
		} // 忽略')'的這些情況 
	} 
	if (have_value[p]) {
		failed = true;
	} 
	data[p] = v;
	have_value[p] = true;
	return;
}

void traverse(int root) {
	queue<int> Q;
	Q.push(root);
	cnt_ans = 0;
	vis[root] = 1;
	while (Q.empty() == false) {
		int cur = Q.front();
		Q.pop();
		if (have_value[cur] == false) {
			failed = true;
		}
		ans[cnt_ans++] = cur;

		if (lchild[cur] != 0 && vis[lchild[cur]] == 0) {
			Q.push(lchild[cur]);
			vis[lchild[cur]] = 1;
		}
		if (rchild[cur] != 0 && vis[rchild[cur]] == 0) {
			Q.push(rchild[cur]);
			vis[lchild[cur]] = 1;
		}
	}
	return;
}


int main() {	
	for (;;) {
		bool end = false;
		Init();
		for (;;) {
			if (scanf("%s", s) != 1) {
				end = true;
				break;
			}
			if (strcmp(s, "()") == 0) {
				traverse(root);
				if (failed == true) {
					printf("not complete\n");
				} else {
					for (int i = 0; i < cnt_ans; i++) {
						if (i == 0) {
							printf("%d", data[ans[i]]);
						} else {
							printf(" %d", data[ans[i]]);
						}
					}
					printf("\n");
				}
				break;
			}	
			int v;
			sscanf(&s[1], "%d", &v);
			addnode(v, strchr(s, ',') + 1);		
		}
		
		if (end == true) {
			break;
		}

	}
	return 0;
}