import java.util.*;
public class TreeStruct{

	public class WrapTreeNode{

		//当前节点
		public TreeStruct currentNode;

		//当前节点的位置，从左到右的空格数量
		public int x;

		//当前层前一个节点
		public WrapTreeNode currLevelPrevNode;

		//父节点
		public WrapTreeNode parentNode;

		//当前节点的类型：左/右孩子
		//left  : 0
		//right : 1
		//root  : -1
		public int childType;

		public WrapTreeNode(
			TreeStruct _node,
			int type,
			int _x,
			WrapTreeNode parent,
			WrapTreeNode prevNode){
			currentNode = _node;
			childType = type;
			x = _x;
			currLevelPrevNode = prevNode;
			parentNode = parent;
		}
	}

	public class TreeLine{

		public TreeLine currLevelPrevLine;

		//当前节点的位置，从左到右的空格数量
		public int x;

		//当前节点的类型：左/右孩子
		//left  : 0
		//right : 1
		//root  : -1
		public int childType;
		public TreeLine(int _x,int type){
			x =_x;
			childType = type;
		}
	}

	private String data;
	private TreeStruct left;
	private TreeStruct right;


	public TreeStruct(String v){
		data=v;
		left=null;
		right=null;
	}

	//先序，使用栈的方式
	public  void perOrderByStack(TreeStruct root,ArrayList<String> list){
		Stack<TreeStruct> stack = new Stack<TreeStruct>();

		stack.push(root);
		TreeStruct curr = null;

		while(!stack.isEmpty()){
			curr = stack.pop();
			//System.out.print(curr.data+",");
			list.add(curr.data);
			if(curr.right!=null){
				stack.push(curr.right);
			}
			if(curr.left!=null){
				stack.push(curr.left);
			}
		}
	}

	//先序，递归方式
	public  void preOrder(TreeStruct root,ArrayList<String> list){
		if(root == null)
			return;
		//System.out.print(root.data+",");
		list.add(root.data);
		preOrder(root.left,list);
		preOrder(root.right,list);
	}





	//后序，递归方式
	public  void lastOrder(TreeStruct root,ArrayList<String> list){
		if(root == null) return;

		lastOrder(root.left,list);
		lastOrder(root.right,list);
		list.add(root.data);
	}

	//后序，使用栈的方式
	public  void lastOrderByStack(TreeStruct root,ArrayList<String> list){

		Stack<TreeStruct> stack = new Stack<TreeStruct>();
		Stack<TreeStruct> help = new Stack<TreeStruct>();
		stack.push(root);
		TreeStruct curr = null;
		while(!stack.isEmpty()){
			curr=stack.pop();
			help.push(curr);
			if(curr.left!=null){
				stack.push(curr.left);
			}
			if(curr.right!=null){
				stack.push(curr.right);
			}
		}

		while(!help.isEmpty()){
			list.add(help.pop().data);
		}
	}




	//中序，递归方式
	public  void inOrder(TreeStruct root,ArrayList<String> list){
		if(root == null) return ;
		inOrder(root.left,list);
		list.add(root.data);
		inOrder(root.right,list);
	}

	//中序，使用栈的方式
	public  void inOrderByStack(TreeStruct root,ArrayList<String> list){
		Stack<TreeStruct> stack = new Stack<TreeStruct>();
		TreeStruct curr = root;

		while(!stack.isEmpty() || curr != null){
			if(curr!=null){
				stack.push(curr);
				curr = curr.left;
			}
			else{
				curr = stack.pop();
				list.add(curr.data);
				curr = curr.right;
			}
		}
	}



	//层次遍历树
	public  void levelOrder(TreeStruct root,ArrayList<String> list){
		Queue<TreeStruct> queue = new LinkedList<TreeStruct>();
		queue.offer(root);

		while(!queue.isEmpty()){
			TreeStruct curr = queue.poll();
			//list.add(curr.data);
			System.out.print(curr.data+",");
			if(curr.left != null){
				queue.offer(curr.left);
			}
			if(curr.right!=null){
				queue.offer(curr.right);
			}
		}
	}


	//获取树最大宽度
	public  int getMaxWidth(TreeStruct root){
		TreeStruct currEnd=root;
		TreeStruct nextEnd=null;
		int currCount=0;
		int maxCount=0;
		Queue<TreeStruct> queue = new LinkedList<TreeStruct>();
		queue.offer(root);

		while(!queue.isEmpty()){
			TreeStruct curr = queue.poll();
			currCount++;
			if(curr.left !=null){
				queue.offer(curr.left);
				nextEnd = curr.left;
			}
			if(curr.right !=null){
				queue.offer(curr.right);
				nextEnd = curr.right;
			}

			if(curr == currEnd){
				currEnd = nextEnd;
				maxCount = Math.max(maxCount,currCount);
				currCount = 0;
				nextEnd = null;
			}
		}
		return maxCount;
	}


	//获取树最大高度
	public  int getMaxLevel(TreeStruct root){
		TreeStruct currEnd=root;
		TreeStruct nextEnd=null;
		int maxLevel=0;
		Queue<TreeStruct> queue = new LinkedList<TreeStruct>();
		queue.offer(root);

		while(!queue.isEmpty()){
			TreeStruct curr = queue.poll();
			if(curr.left !=null){
				queue.offer(curr.left);
				nextEnd = curr.left;
			}
			if(curr.right !=null){
				queue.offer(curr.right);
				nextEnd = curr.right;
			}

			if(curr == currEnd){
				currEnd = nextEnd;
				maxLevel++;
				nextEnd = null;
			}
		}
		return maxLevel;
	}

	//将一棵树序列化
	public Queue<String> getSerialization(TreeStruct root){
		if(null == root) return null;
		Queue<String> queue = new LinkedList<String>();
		serialzation(root,queue);
		return queue;
	}

	private void serialzation(TreeStruct root,Queue<String> queue){
		if(root == null)
			queue.offer("#");
		else{
			queue.offer(root.data);
			serialzation(root.left,queue);
			serialzation(root.right,queue);
		}
	}

	//反序列化成一棵树
	public TreeStruct unSerialztaion(Queue<String> queue){
		if(null == queue || queue.size() == 0) return null;
		return unSerial(queue);
	}

	private TreeStruct unSerial(Queue<String> queue){
		String v = queue.poll();
		if(v=="#") return null;
		TreeStruct root = new TreeStruct(v);
		root.left = unSerial(queue);
		root.right = unSerial(queue);
		return root;
	}


	public Boolean isCompleteBinTree(TreeStruct root){
		if(root == null ||
			root.left == null && root.right ==null ||
			root.left !=null && root.right ==null) return true;

		boolean isleaf=false;

		Queue<TreeStruct> queue = new LinkedList<TreeStruct>();
		queue.offer(root);


		while(!queue.isEmpty()){

			TreeStruct curr = queue.poll();
			if(curr.right!=null && curr.left == null) 
				return false;

			if(curr.left == null && curr.right==null){
				isleaf=true;
			}
			if(isleaf && (curr.left !=null || curr.right!=null))
					return false;
			

			if(curr.left !=null)
				queue.offer(curr.left);
			if(curr.right!=null)
				queue.offer(curr.right);
		}
		return true;
	}



	private String getChildStr(TreeStruct root){
		String str=root.data;
		if(root.left != null) str = "^"+str;
		if(root.right != null) str = str+"^";
		return str;
	}

	private void printNode(WrapTreeNode node,int currLevel){

		int perWidth = 20/currLevel;
		if(node.parentNode == null){
			printStr(getStr(getChildStr(node.currentNode),node.x));
			return;
		}

		if(node.currLevelPrevNode == null){
			//left
			if(node.childType == 0){
				int space = node.parentNode.x - perWidth;
				printStr(getStr(getChildStr(node.currentNode),space));
			}
			//right
			else{
				int space = node.parentNode.x + perWidth;
				printStr(getStr(getChildStr(node.currentNode),space));
			}
		}else{
			int space = node.parentNode.x - node.currLevelPrevNode.x+perWidth;
			if(space+node.currLevelPrevNode.x >node.parentNode.x && currLevel > 2){
				space  = node.parentNode.x - node.currLevelPrevNode.x;
			}
			
			printStr(getStr(getChildStr(node.currentNode),space));
		}

	}

	//打印树
	public  void printBinTree(TreeStruct root){

		int maxWidth = 180;
		int perLeftWidth = 10;
		int perRightWidth = 20;
		int usedWidth = 0;
		TreeStruct currEnd=root;
		TreeStruct nextEnd=null;
		int currLevel =1;
		WrapTreeNode currLevelPrev=null;


		Queue<WrapTreeNode> nodeQueue = new LinkedList<WrapTreeNode>();
		Queue<TreeLine> lineQueue = new LinkedList<TreeLine>();

		nodeQueue.offer(
			new WrapTreeNode(
				root,-1,(maxWidth-root.data.length())/2,null,null));

		while(!nodeQueue.isEmpty()){

			WrapTreeNode curr = nodeQueue.poll();
			printNode(curr,currLevel);
			//printStr(getStr(curr.currentNode.data,curr.x));
			int midd = curr.x;

			if(curr.currentNode.left !=null){
				WrapTreeNode l = new 
				WrapTreeNode(curr.currentNode.left,
					0,
					midd-perLeftWidth,
					curr,
					currLevelPrev);
				
				
				nodeQueue.offer(l);
				//lineQueue.offer(new TreeLine(midd-perWidth,0));
				nextEnd = curr.currentNode.left;
				currLevelPrev = l;


			}
			if(curr.currentNode.right !=null){
				WrapTreeNode r = new 
				WrapTreeNode(curr.currentNode.right,
					1,
					midd+perRightWidth,
					curr,
					currLevelPrev);
				

				nodeQueue.offer(r);
				//lineQueue.offer(new TreeLine(midd+perWidth,1));
				nextEnd = curr.currentNode.right;
				currLevelPrev = r;
			}

			if(curr.currentNode == currEnd){
				printLine(lineQueue);
				currEnd = nextEnd;
				nextEnd = null;
				currLevelPrev = null;
				currLevel++;
			}
		}
	}

	private  void printLine(Queue<TreeLine> lineQueue){
		System.out.println();
		System.out.println();
		System.out.println();
		System.out.println();
		// while(!lineQueue.isEmpty()){
		// 	TreeLine line = lineQueue.poll();
		// 	if(line.childType == 1){
		// 		printStr(getStr("/",line.x));
		// 	}else{
		// 		printStr(getStr("\\",line.x));
		// 	}
		// }
		// System.out.println();
	}

	private  String getStr(String str,int spaceCount){
		for (int i=0; i<spaceCount; i++) {
			str= " "+str;
		}
		return str;
	}

	private  void printStr(String v){
		System.out.print(v);
	}




	public static TreeStruct getNode(){
		String v = Character.toString((char)('A'+((int)(Math.random()*26))));
		return new TreeStruct(v);
	}

	public static void randomBinTree(TreeStruct root,int maxLevel){

		TreeStruct p = root;
		int left = maxLevel;


		int random = (int)(Math.random()*9999);
		int ont = (int)(Math.random()*8)+1;

		while(left > 0){
			if(left == maxLevel){
				p.right = getNode();
				p.left=getNode();
				p = p.left;
			}
			else{
				if(random/left % ont >0){
					p.left = getNode();
					p=p.left;
				}
				else{
					p.right = getNode();
					p.left=getNode();
					p = p.right;
				}
			}
			left--;
		}
	}

	public static Boolean compar(ArrayList<String> list,ArrayList<String> list2){
		if(list.size()!= list2.size()) return false;
		int size = list.size()-1;
		while(size >0){
			if(list.get(size) != list2.get(size--)) return false;
		}
		return true;
	}

	public static TreeStruct getRandomBinTree(){
		TreeStruct root = new TreeStruct("AAAA");

		root.left = new TreeStruct("A1");
		root.right = new TreeStruct("A2");
		randomBinTree(root.left,2);
		randomBinTree(root.right,1);

		return root;
	}
	public static Boolean isTrue(){
		int max = 1000000;
		for (int i=0; i<max;i++ ) {
			ArrayList<String> list = new ArrayList<String>();
			ArrayList<String> list2 = new ArrayList<String>();
				
			TreeStruct root = getRandomBinTree();
			root.inOrder(root,list);
			root.inOrderByStack(root,list2);
			if(!compar(list,list2)){
				return false;
			}
		}
		return true;
		
	}

	

	public static void printSerialztion(TreeStruct root){
		//TreeStruct root = getRandomBinTree();
		Queue<String> queue = root.getSerialization(root);
		while(!queue.isEmpty())
		{
			System.out.print(queue.poll()+",");
		}
	}

	public static void getUnSerialzation(Queue<String> queue){
		TreeStruct root = (new TreeStruct("")).unSerialztaion(queue);
		root.printBinTree(root);
	}

	public static TreeStruct printTreeTest(){
		TreeStruct root = getRandomBinTree();
		root.printBinTree(root);
		return root;
	}

	public static void main(String[] args) {

		TreeStruct root = printTreeTest();
		printSerialztion(root);
		System.out.print("result = "+root.isCompleteBinTree(root));
		
	}







}