import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class java{
    public static void main(String[] args){
        java Java=new java();
        bitTreeNode root=Java.createTree();
        System.out.println("前序遍历: ");
        Java.preorder(root);
        System.out.println("\n中序遍历：");
        Java.inorder(root);
        System.out.println("\n后序遍历: ");
        Java.lastorder(root);
        System.out.println("\n层次遍历：");
        ArrayList<Object> arrayList=Java.PrintFromTopToBottom(root);
        for (Object o:arrayList){
            System.out.print(o);
        }
    }


    public bitTreeNode createTree(){
        bitTreeNode d = new bitTreeNode('d',null,null);
        bitTreeNode e = new bitTreeNode('e',null,null);
        bitTreeNode f = new bitTreeNode('f',null,null);
        bitTreeNode g = new bitTreeNode('g',null,null);
        bitTreeNode b = new bitTreeNode('b',d,e);
        bitTreeNode c = new bitTreeNode('c',f,g);
        bitTreeNode a = new bitTreeNode('a',b,c);
        return a;
    }
    public ArrayList<Object>  PrintFromTopToBottom(bitTreeNode root){
        ArrayList<Object> arrayList=new ArrayList<>();
        Queue<bitTreeNode> queue=new LinkedList<>();
        if (root!=null){
            queue.offer(root);
        }
        while (!queue.isEmpty()){
            bitTreeNode node=queue.poll();
            arrayList.add(node.val);
            if (node.lchild!=null)
                queue.offer(node.lchild);
            if (node.rchild!=null)
                queue.offer(node.rchild);
        }


        return arrayList;
    }
    public void preorder(bitTreeNode node){
        if (node==null)
            return;
        System.out.print(node.val);
        preorder(node.lchild);
        preorder(node.rchild);
    }
    public void inorder(bitTreeNode node){
        if (node==null)
            return;
        inorder(node.lchild);
        System.out.print(node.val);
        inorder(node.rchild);
    }
    public void lastorder(bitTreeNode node){
        if (node==null)
            return;
        lastorder(node.lchild);
        lastorder(node.rchild);
        System.out.print(node.val);
    }


}
class bitTreeNode{
    Object val;
    bitTreeNode lchild;
    bitTreeNode rchild;
    public bitTreeNode(Object val,bitTreeNode lchild,bitTreeNode rchild){
        this.val=val;
        this.lchild=lchild;
        this.rchild=rchild;
    }
}