(二叉搜索树10.1.2)POJ 1577 Falling Leaves(根据删除叶子节点的顺序输出计算一颗二叉树的前序遍历序列)

package com.njupt.acm;

import java.util.Scanner;

public class POJ_1577 {

public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);

int levels = 0;
String line;
String[] leaves = new String[26];

while(scanner.hasNext()){
line = scanner.nextLine().trim();
if(line.equals("*")){
System.out.println(preorder(leaves, levels));
leaves = new String[26];
levels = 0;
}else if(line.equals("$")){
System.out.println(preorder(leaves, levels));
break;
}else{
leaves[levels++] = line;
}
}

}

public static String preorder(String[] leaves,int levels){//将根据leaves中的行序列计算前序遍历序列

while(levels > 0 && leaves[levels-1].length() == 0){//从leaves[]标的最后一项开始找,找到第一个非空项..
levels--;
}
if(levels == 0){
return "";
}
levels--;

char root = leaves[levels].charAt(0);//leaves表尾存储子根
String[] left = new String[levels];
String[] right = new String[levels];

int i;
for(i = 0 ; i < levels ; ++i){
int past = 0;
while(past < leaves[i].length() && leaves[i].charAt(past) < root){//找到左右子树的分界点
past++;
}

left[i] = leaves[i].substring(0,past);
right[i] = leaves[i].substring(past);
}

return root + preorder(left, levels) + preorder(right, levels);
}
}