poj 1577 Falling Leaves
题意：一个二叉搜索树，不断给出并去掉所有的叶节点，输出前序遍历这棵二叉树的结果。
思路：先全部读入，从最后的根节点开始建立二叉搜索树。
#include<cstdio> #include<cstring> using namespace std; struct node{ char c; int lch, rch; }tree[30]; char s[30][30]; int e; void add(int n, char c) { if(tree[n].c > c) { if(!tree[n].lch) { tree[e].c = c; tree[n].lch = e++; } else add(tree[n].lch, c); } else { if(!tree[n].rch) { tree[e].c = c; tree[n].rch = e++; } else add(tree[n].rch, c); } } void pre_order(int n) { printf("%c",tree[n].c); if(tree[n].lch) pre_order(tree[n].lch); if(tree[n].rch) pre_order(tree[n].rch); } int main() { int cnt = 0; while(~scanf("%s",s[cnt++])) { if(s[cnt-1][0] == '*' || s[cnt-1][0] == '$') { e = 0; memset(tree,0,sizeof(tree)); int n = cnt-1; tree[e++].c = s[n-1][0]; for(int i = n-2; i >= 0; i--) { int len = strlen(s[i]); for(int j = 0; j < len; j++) add(0,s[i][j]); } pre_order(0); printf("\n"); if(s[cnt-1][0] == '$') break; cnt = 0; } } return 0; }