输入结点的前序序列，构造一棵二叉树

Question

　　构建一棵如下图所示的二叉树：                                  1
                                 / \
                                2   3
                               / \
                              4   5
　　用#代表空结点，则其前序序列为：1 2 4 # # 5 # # 3 # #。如何用终端读取用户输入的前序序列，构建出二叉树？

Answer 1

import java.util.*;
//树的结点类型
class BTNode{
private int elem=0;
private BTNode lChild=null,rChild=null;
BTNode(int elem){
this.elem=elem;
}
public void setLChild(BTNode lChild){
this.lChild=lChild;
}
public void setRChild(BTNode rChild){
this.rChild=rChild;
}
public BTNode getRChild(){
return rChild;
}
public BTNode getLChild(){
return lChild;
}
public int getElem(){
return elem;
}
public void setElem(int elem){
this.elem=elem;
}
}
//二叉树类型
public class BinaryTree{
public BTNode root=null;
BinaryTree(Scanner input){

System.out.println("开始创建二叉树,请按树的前序序列输入各个结点,每输入一个结点后请回车:");
System.out.println("输入的前序序列：把二叉树的所有为空的结点用#代替，再按前序遍历得到的序列");
root=create(input);
}
public BTNode create(Scanner input){
String elemString=input.nextLine();
if(elemString.equals("#")){
return null;
}else{
BTNode root=new BTNode(Integer.parseInt(elemString));
root.setLChild(create(input));
root.setRChild(create(input));
return root;
}
}
public String preorder(BTNode root){
if(root==null){
return "";
}else{
String lstr=preorder(root.getLChild());
String rstr=preorder(root.getRChild());
String estr=String.valueOf(root.getElem());
if(lstr.length()>0){
if(rstr.length()>0){
return estr+" "+lstr+" "+rstr;
}else{
return estr+" "+lstr;
}
}else{
if(rstr.length()>0){
return estr+" "+rstr;
}else{
return estr;
}
}
}
}
public String inorder(BTNode root){
if(root==null){
return "";
}else{
String lstr=inorder(root.getLChild());
String rstr=inorder(root.getRChild());
String estr=String.valueOf(root.getElem());
if(lstr.length()>0){
if(rstr.length()>0){
return lstr+" "+estr+" "+rstr;
}else{
return lstr+" "+estr;
}
}else{
if(rstr.length()>0){
return estr+" "+rstr;
}else{
return estr;
}
}
}
} 
public String postorder(BTNode root){
if(root==null){
return "";
}else{
String lstr=postorder(root.getLChild());
String rstr=postorder(root.getRChild());
String estr=String.valueOf(root.getElem());
if(lstr.length()>0){
if(rstr.length()>0){
return lstr+" "+rstr+" "+estr;
}else{
return estr+" "+lstr;
}
}else{
if(rstr.length()>0){
return rstr+" "+estr;
}else{
return estr;
}
}
}
}
public static void main(String[] args){
BinaryTree tree=new BinaryTree(new Scanner(System.in));
System.out.println("前序序列：");
System.out.println(tree.preorder(tree.root));
System.out.println("中序序列：");
System.out.println(tree.inorder(tree.root));
System.out.println("后序序列：");
System.out.println(tree.postorder(tree.root));
}}
结果:
F:\java>java BinaryTree
开始创建二叉树,请按树的前序序列输入各个结点,每输入一个结点后请回车:
输入的前序序列：把二叉树的所有为空的结点用#代替，再按前序遍历得到的序列
1
2
4
#
#
5
#
#
3
#
#
前序序列：
1 2 4 5 3
中序序列：
4 2 5 1 3
后序序列：
4 5 2 3 1