这里使用数组来实现二叉树，用整数表示节点编号，left[u]和right[u]分别表示u节点的左孩子和右孩子的节点编号。 这里关键是按照输入建立出二叉树。 对应代码如下：
#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<string> #include<vector> #include<queue> using namespace std; const int maxn = 300; int Left[maxn], Right[maxn],Value[maxn]; bool hasValue[maxn]; int root; int cnt; bool failed; void newTree(){ cnt = 0; root = ++cnt; Left[root] = Right[root] = 0; hasValue[root] = false; } int newNode(){ ++cnt; Left[cnt] = Right[cnt] = 0; hasValue[cnt] = 0; return cnt; } void addnode(int v, char *s){ int t = root; for (int i = 0; i < strlen(s)-1; i++){ if (s[i] == 'L'){ if (Left[t] == 0) Left[t] = newNode(); t = Left[t]; } else{ if (Right[t] == 0) Right[t] = newNode(); t = Right[t]; } } if (hasValue[t]) failed = true; hasValue[t] = true; Value[t] = v; } bool getinput(){ char s[maxn]; failed = false; newTree(); for (;;){ if (scanf("%s", s) != 1) return false; if (!strcmp(s, "()")) break; int v; sscanf(&s[1], "%d", &v); addnode(v, strchr(s, ',') + 1); } return true; } void bfs(vector<int> &ans){ queue<int> q; ans.clear(); q.push(root); while (!q.empty()){ int p = q.front(); q.pop(); if (!hasValue[p]){ failed = true; return; } ans.push_back(Value[p]); if (Left[p] != 0) q.push(Left[p]); if (Right[p] != 0) q.push(Right[p]); } return; } int main() { while (getinput()){ vector<int> ans; bfs(ans); if (failed) cout << "not complete" << endl; else{ cout << ans[0]; for (int i = 1; i < ans.size(); i++) cout << " " << ans[i]; cout << endl; } memset(hasValue, 0, sizeof(hasValue)); } return 0; }