package cunchu;
import java.util.Scanner;
class Node{
char data;
Node lchild;
Node rchild;
}
public class ErchaLianbiao {
//前序输入树
static char[] arr;
public static void input(){
System.out.println("请前序输入树，#代表左右子树为空：");
Scanner in = new Scanner(System.in);
arr = in.next().toCharArray();
in.close();
}
//构建树
static int i=0;
public static Node createTree(Node node){
if(i<arr.length){
if(arr[i] == '#'){
node = null;
i++;
}else{
node = new Node();
node.data=arr[i];
i++;
node.lchild = createTree(node.lchild);
node.rchild = createTree(node.rchild);
}
}
return node;
}
//前序遍历
public static void preOrder(Node node){
if(node == null){
return;
}
System.out.print(node.data+" ");
preOrder(node.lchild);
preOrder(node.rchild);
}
//中序遍历
public static void inOrder(Node node){
if(node == null){
return;
}
inOrder(node.lchild);
System.out.print(node.data+" ");
inOrder(node.rchild);
}
//后续遍历
public static void postOrder(Node node){
if(node == null){
return;
}
postOrder(node.lchild);
postOrder(node.rchild);
System.out.print(node.data+" ");
}
public static void main(String[] args) {
/*AB#D##C##*/
/*ABDH#K###E##CFI###G#J##*/
input();
Node node = null;
Node reNode = createTree(node);
System.out.print("前序遍历：");
preOrder(reNode);
System.out.println();
System.out.print("中序遍历：");
inOrder(reNode);
System.out.println();
System.out.print("后序遍历：");
postOrder(reNode);
}
}
