|                       
        /-----------10(10)------\           
        |                       |           
/-------5(5)\             /-----15(15)\     
|           |             |           |     
3(3)\       7(7)\         12(12)      18(18)
    |           |                           
    4(4)        8(8)                        

import java.util.LinkedList;
/**
 * 二叉树结点类
 * @author 硅谷探秘者(jia)
 */
class Node{
	public int data;
	public Node left;
	public Node right;
	public Node(Node left,Node right,int data) {
		this.left=left;
		this.right=right;
		this.data=data;
	}
	public Node(int data) {
		this.data=data;
	}
}
public class A1 {
	static Node root;
	public static void main(String[] args) {
		/**
		 * 构造二叉树
		 */
		Node n4=new Node(4);
		Node n8=new Node(8);
		Node n12=new Node(12);
		Node n18=new Node(18);
		Node n3=new Node(null,n4,3);
		Node n7=new Node(null,n8,7);
		Node n5=new Node(n3,n7,5);
		Node n15=new Node(n12,n18,15);
		Node n10=new Node(n5,n15,10);
		root=n10;
		/**
		 * 层次遍历
		 */
		cengDis(root);
	}
	/**
	 * 	层级遍历（用jdk提供的LinkedList充当栈或队列）
	 * @param p
	 */
	public static void cengDis(Node p) {
		LinkedList<Node> stack=new LinkedList<>();
		LinkedList<Node> dui=new LinkedList<>();
		PrintfTree tree = null;
		dui.add(p);
		while(true){
			Node f=null;
			if(dui.size()>0) {
				f=dui.removeFirst();
			}
			if(f==null) {
				Node d=null;
				if(stack.size()>0) {
					d=stack.removeFirst();
				}
				if(d==null) {
					tree.show();
					return ;
				}else {
					dui.addLast(d);
					while(true) {
						d=null;
						if(stack.size()>0) {
							d=stack.removeFirst();
						}
						if(d==null) {
							break;
						}else {
							dui.addLast(d);
						}
					}
				}
			}else {
				if(tree==null) {
					tree=new PrintfTree(""+f.data+"("+f.data+")");
				}else {
					tree.add(new PrintfTree(""+f.data+"("+f.data+")"));
				}
				Node left=f.left;
				if(left!=null) {
					stack.addLast(left);
				}
				Node right=f.right;
				if(right!=null) {
					stack.addLast(right);
				}
			}
		}
	}
}
/**
 * 打印二叉树工具类
 * @author 硅谷探秘者(jia)
 */
class PrintfTree{
	private String v;
	private PrintfTree l;
	private PrintfTree r;
	public PrintfTree(String v){
		this.v = v;
	}
	public void add(PrintfTree the){
		if(new Integer(the.v.substring(0,the.v.lastIndexOf("("))) < new Integer(v.substring(0,v.lastIndexOf("(")))){
			if(l==null) l = the;
			else l.add(the);
		}
		else{
			if(r==null) r = the;
			else r.add(the);
		}
	}
	public int getHeight(){
		int h = 2;
		int hl = l==null? 0 : l.getHeight();
		int hr = r==null? 0 : r.getHeight();
		return h + Math.max(hl,hr);
	}
	public int getWidth(){
		int w = (""+v).length();
		if(l!=null) w += l.getWidth();
		if(r!=null) w += r.getWidth();
		return w;
	}
	public void show(){
		char[][] buf = new char[getHeight()][getWidth()];
		printInBuf(buf, 0, 0);
		showBuf(buf);
	}
	private void showBuf(char[][] x){
		for(int i=0; i<x.length; i++){
			for(int j=0; j<x[i].length; j++)
				System.out.print(x[i][j]==0? ' ':x[i][j]);
			System.out.println();
		}
	}
	private void printInBuf(char[][] buf, int x, int y){
		String sv = "" + v;
		int p1 = l==null? x : l.getRootPos(x);
		int p2 = getRootPos(x);
		int p3 = r==null? p2 : r.getRootPos(p2+sv.length());

		buf[y][p2] = '|';
		for(int i=p1; i<=p3; i++) buf[y+1][i]='-';
		for(int i=0; i<sv.length(); i++) buf[y+1][p2+i]=sv.charAt(i);
		if(p1<p2) buf[y+1][p1] = '/';
		if(p3>p2) buf[y+1][p3] = '\\';

		if(l!=null) l.printInBuf(buf,x,y+2);
		if(r!=null) r.printInBuf(buf,p2+sv.length(),y+2);
	}
	private int getRootPos(int x){
		return l==null? x : x + l.getWidth();
	}
}