POJ 1577 二叉搜索树

这题前边说了一堆废话

大意就是给出了一个二叉搜索树，但给出的方式比较奇怪，是删除叶子的顺序。 即把树上的叶子结点给出，然后揪掉这些叶子，把剩下的结点中变成叶子结点的再给出，这样一直到所有的结点都被揪掉。 最后要求这个二叉搜索树的先序遍历

这题解决的方式很简单，按照他给的那些东西，倒着建立二叉搜索树就行了。

为什么呢？ 我们观察一下，可以发现，最后一个揪掉的一定是根节点，再往上，每一次揪掉的结点，之间一定是互相没有父子关系的。这是显然的。 而且所有的结点会先于他们的父亲结点被揪掉，这也是显然的。 那么倒序建二叉搜索树的时候，会跟原来的二叉搜索树是一样的，因为所有有父子关系的结点之间的相对位置没有变化。

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#define eps 1e-5
#define MAXN 1111
#define MAXM 55555
#define INF 1000000000
using namespace std;
struct Tree
{
    char c;
    int lch, rch;
    void init()
    {
        lch = rch = 0;
    }
}tree[33];
char s[33][33];
int e;
void add(int u, char c)
{
    if(c < tree[u].c)
    {
        if(!tree[u].lch)
        {
            tree[e].c = c;
            tree[u].lch = e++;
        }
        else add(tree[u].lch, c);
    }
    else
    {
        if(!tree[u].rch)
        {
            tree[e].c = c;
            tree[u].rch = e++;
        }
        else add(tree[u].rch, c);
    }
}
void preorder(int u)
{
    printf("%c", tree[u].c);
    if(tree[u].lch) preorder(tree[u].lch);
    if(tree[u].rch) preorder(tree[u].rch);
}
int main()
{
    int cnt = 0;
    while(scanf("%s", s[cnt++]) != EOF)
    {
        if(s[cnt - 1][0] == '*' || s[cnt - 1][0] == '$')
        {
            e = 0;
            for(int i = 0; i < 30; i++) tree[i].init();
            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]);
            }
            preorder(0);
            printf("\n");
            if(s[cnt - 1][0] == '$') break;
            cnt = 0;
        }
    }
    return 0;
}