二叉搜索树解决落叶问题

一 原问题链接

Falling Leaves - POJ 1577 - Virtual Judgehttps://vjudge.net/problem/POJ-1577

二 输入和输出

1 输入

输入包含多个测试用例。每个测试用例都是一行或多行大写字母序列，每行都给出按上述步骤从二叉搜索树中删除的叶子，每行给出的字母都按字母升序排列。在测试用例之间以一行分隔，该行仅包含一个星号，在最后一个测试用例后给出一行，该行仅给出一个美元符号。在输入中没有空格或空行。

2 输出

对于每个测试用例，都有唯一的二叉搜索树，单行输出该树的先序遍历。

三 输入和输出样例

1 输入样例

BDHPY

CM

GQ

K

*

AC

B

$

2 输出样例

KGCBDHQMPY

BAC

四 算法设计

最后一个字母一定为树根，先输入的字母在树的深层，可以逆序建树。读入字母序列后用字符串存储，然后逆序创建二叉搜索树，将小的字母插入左子树，将大的字母插入右子树。输出该树的先序遍历：根，左子树，右子树。

五 代码

package poj1577;

import java.util.Scanner;

public class Poj1577 {
    static int cnt = 1;
    static data tree[] = new data[110];

    static void insert(int t, char ch) {
        if (tree[t].c == 0) {
            tree[t].c = ch;
            return;
        }
        if (ch < tree[t].c) {
            if (tree[t].l == 0) {
                tree[++cnt].c = ch;
                tree[t].l = cnt;
            } else
                insert(tree[t].l, ch);
        }
        if (ch > tree[t].c) {
            if (tree[t].r == 0) {
                tree[++cnt].c = ch;
                tree[t].r = cnt;
            } else
                insert(tree[t].r, ch);
        }
    }

    static void preorder(int t) {
        if (tree[t].c == 0)
            return;
        System.out.print(tree[t].c);
        preorder(tree[t].l);
        preorder(tree[t].r);
    }

    public static void main(String[] args) {
        String s1, s;
        while (true) {
            s = "";
            for (int i = 0; i < tree.length; i++) {
                tree[i] = new data();
            }
            Scanner scanner = new Scanner(System.in);
            while (true) {
                s1 = scanner.next();
                if (s1.charAt(0) != '*' && s1.charAt(0) != '$') {
                    s += s1;
                } else {
                    break;
                }
            }

            for (int i = s.length() - 1; i >= 0; i--)
                insert(1, s.charAt(i));
            preorder(1);
            System.out.println();
            if (s1.charAt(0) == '$')
                break;
        }
    }
}

class data {
    int l;
    int r;
    char c;
}

六 测试

绿色为输入，白色为输出。