import java.io.*;
/*
 * ABC##DE#G##F###(其中#表示空结点)
       则输出结果为:
       先序:ABCDEGF
   中序:CBEGFDA
       后序:CFGEDBA
 */
public class BinaryTree 
{
Note root;
public BinaryTree()throws IOException
{
CreateBitree(root);   //这里不是已经把root赋值了,为什么在调试的时候root到最后都是空的
}
public void CreateBitree(Note root) throws IOException
{
BufferedReader bin = new BufferedReader(new InputStreamReader(System.in));
String str = bin.readLine();
char c = str.charAt(0);
if(c == '#')
root = null;
else
{
root = new Note();
root.c = c;
CreateBitree(root.lchild);
CreateBitree(root.rchild);
}
}
public void preordertravel(Note tree)
{
if(tree!=null)
{
System.out.print(tree.c);
preordertravel(tree.lchild);
preordertravel(tree.rchild);
}
}
public void inordertravel(Note tree)
{
if(tree!=null)
{
inordertravel(tree.lchild);
System.out.print(tree.c);
inordertravel(tree.rchild);
}
}
public void postordertravel(Note tree)
{
if(tree!=null)
{
postordertravel(tree.lchild);
postordertravel(tree.rchild);
System.out.print(tree.c);
}
}
public static void main(String[] args) throws IOException
{
BinaryTree b = new BinaryTree();
System.out.println("前序遍历:");
b.preordertravel(b.root);
System.out.println();
System.out.println("中序遍历:");
b.inordertravel(b.root);
System.out.println();
System.out.println("后序遍历:");
b.postordertravel(b.root);
System.out.println();
}
}
class Note
{
char c;
Note lchild;
Note rchild;
}