2016-08-08 Problem Solving►UVa UVa 122 - Trees on the level Contents 1. Problem2. Solution3. Code Problem中文網址 Solution先 parse 字串,也可用 std::stringstream。將節點依指令插入,記得處理節點已存在時。插完後遍歷一次,再檢查有沒有沒走到的點即可。 CodeUVa 122123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141#include<cstdio>#define Left(n) ((n)<<1)#define Right(n) (((n)<<1)+1)#define N 32768int tree[N];bool isVisit[N];inline bool input(int& val, char *str){ char c; val = 0; while ((c = getchar()) != '(') if (c == EOF) return false; if ((c = getchar()) == ')') return false; else val = c - '0'; while ((c = getchar()) != ',') val = val * 10 + c - '0'; int i; for (i = 0;; i++) { c = getchar(); if (c == ')') { str[i] = NULL; break; } str[i] = c; } return true;}inline bool insert(int val, char* str){ int idx = 1; if (!str[0]) { if (tree[1] != -1) return false; tree[1] = val; return true; } for (int i = 0; str[i]; i++) if (str[i] == 'L') idx = Left(idx); else idx = Right(idx); if (tree[idx] != -1)//處理重複節點 return false; tree[idx] = val; return true;}inline void traverse(int idx)//VLR{ if (idx < N&&tree[idx] != -1) { isVisit[idx] = true; traverse(Left(idx)); traverse(Right(idx)); }}int main(){ int val; char str[10]; while (input(val, str)) { int i, count = 1; bool isOk = true; for (i = 0; i < N; i++) { tree[i] = -1; isVisit[i] = false; } isOk = insert(val, str); while (input(val, str)) { if (isOk) { isOk = insert(val, str); count++; } } if (isOk) { traverse(1); int temp = 0; for (i = 1; i < N&&temp < count; i++) if (tree[i] != -1) { if (isVisit[i]) temp++; else { isOk = false; break; } } } if (isOk) { bool first = true; int temp = 0; for (i = 0; i < N&&temp < count; i++) { if (tree[i] != -1) { if (first) first = false; else putchar(' '); printf("%d", tree[i]); temp++; } } putchar('\n'); } else puts("not complete"); } return 0;} Newer UVa 107 - The Cat in the Hat Older UVa 10954 - Add All