#include <iostream> #include <cstdio> #include <cstring> using namespace std; struct node { char ch; int l, r; }nodePool[10000]; char str[100][100]; int root; int cnt; int flag = 1; void init() { root = 0; cnt = root; memset(nodePool, 0, sizeof nodePool); } int newNodeL(char ch, int par) { cnt++; nodePool[par].l = cnt; nodePool[cnt].ch = ch; return cnt; } int newNodeR(char ch, int par) { cnt++; nodePool[par].r = cnt; nodePool[cnt].ch = ch; return cnt; } void insert(char ch) { int u = root; for (;;) { if (ch > nodePool[u].ch) { if (nodePool[u].r != 0) u = nodePool[u].r; else { newNodeR(ch, u); break; } } else if (ch < nodePool[u].ch) { if (nodePool[u].l != 0) u = nodePool[u].l; else { newNodeL(ch, u); break; } } } } int input() { int i; for (i = 0;; i++) { scanf("%s", str[i]); if (strcmp(str[i], "*") == 0) break; else if (strcmp(str[i], "$") == 0) { flag = 0; break; } } return i; } void create(int layer) { nodePool[root].ch = str[layer - 1][0]; for (int i = layer - 2; i >= 0; i--) { for (int j = 0; str[i][j]; j++) insert(str[i][j]); } } void preOrder(int root) { printf("%c", nodePool[root].ch); if (nodePool[root].l != 0) preOrder(nodePool[root].l); if (nodePool[root].r != 0) preOrder(nodePool[root].r); return; } int main(void) { int layer; for (;;) { init(); layer = input(); create(layer); preOrder(root); printf("\n"); if (flag == 0) break; } return 0; } |
Double click to view unformatted code.