A link to the original question

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

Two Inputs and Outputs

1 input

The input contains multiple test cases.Each test case is a sequence of one or more uppercase letters, each giving the leaves removed from the binary search tree as described above, each giving letters in ascending alphabetical order.Separate the test cases with a line that contains only an asterisk, and give a line after the last test case that contains only a dollar sign.There are no spaces or blank lines in the input.

2 output

For each test case, there is a unique binary search tree, and a single line outputs the preorder traversal of the tree.

Three input and output samples

1 Input example

BDHPY

CM

GQ

K

*

AC

B

$

2 Sample output

KGCBDHQMPY

BAC

Four Algorithms Design

The last letter must be the root of the tree. The letter entered first is in the deep layer of the tree, and the tree can be built in reverse order.After reading the sequence of letters, store them as strings, and then create a binary search tree in reverse order, inserting small letters into the left subtree and inserting larger letters into the right subtree.Output the preorder traversal of the tree: root, left subtree, right subtree.

Five codes

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;} elseinsert(tree[t].l, ch);}if (ch > tree[t].c) {if (tree[t].r == 0) {tree[++cnt].c = ch;tree[t].r = cnt;} elseinsert(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;}

Six Tests

Green is input and white is output.