content: package com.algorithdemo.tree;
  
  import java.util.Stack;
  
  public class TreePrint {
  	
  	/**
  	 * ݹ ǰ
  	 * @param head
  	 */
  	public static void preOrderRecur(TreeNode head){
  		if(head==null){
  			return;
  		}
  		System.out.print(head.getValue()+" ");
  		preOrderRecur(head.getLeft());
  		preOrderRecur(head.getRight());
  	}
  	
  	/**
  	 * ݹ 
  	 * @param head
  	 */
  	public static void inOrderRecur(TreeNode head){
  		if(head==null){
  			return;
  		}
  		inOrderRecur(head.getLeft());
  		System.out.print(head.getValue()+" ");
  		inOrderRecur(head.getRight());
  	}
  
  	/***
  	 * ݹ 
  	 * @param head
  	 */
  	public static void posOrderRecur(TreeNode head){
  		if(head == null){
  			return;
  		}
  		posOrderRecur(head.getLeft());
  		posOrderRecur(head.getRight());
  		System.out.print(head.getValue() + " ");
  	}
  	
  	/**
  	 * ǰ ǵݹ
  	 * @param head
  	 */
  	public static void preOrderUnRecur(TreeNode head){
  		System.out.println("pre-order");
  		if(head!=null){
  			Stack<TreeNode> stack = new Stack<TreeNode>();
  			stack.add(head);
  			while(!stack.isEmpty()){
  				head = stack.pop();
  				System.out.print(head.getValue()+" ");
  				if(head.getRight() != null){
  					stack.push(head.getRight());
  				}
  				if(head.getLeft() != null){
  					stack.push(head.getLeft());
  				}
  			}
  		}
  	}
  	
  	/**
  	 *  ǵݹ
  	 * @param head
  	 */
  	public static void inOrderUnRecur(TreeNode head){
  		System.out.println("in-order :");
  		if(head != null){
  		  Stack<TreeNode> stack = new Stack<TreeNode>();
  		  while(!stack.isEmpty() || head!=null ){
  			  if(head!=null){
  				  stack.push(head);
  				  head = head.getLeft();
  			  }else{
  				  head = stack.pop();
  				  System.out.print(head.getValue()+" ");
  				  head = head.getRight();
  			  }
  		  }
  		}
  	}
  	
  	/**
  	 *  ǵݹ
  	 * @param head
  	 */
  	public static void posOrderUnRecur(TreeNode head){
  		System.out.println("pos-order:");
  		if(head!=null){
  			Stack<TreeNode> stack = new Stack<TreeNode>();
  			stack.push(head);
  			TreeNode c = null;
  			while(!stack.isEmpty()){
  				c= stack.peek();
  				if(c.getLeft()!=null && head!=c.getLeft() && head!=c.getRight()){
  					stack.push(c.getLeft());
  				}else if(c.getRight()!=null && head!=c.getRight()){
  					stack.push(c.getRight());
  				}else{
  					System.out.print(stack.pop().getValue()+" ");
  					head = c;
  				}
  				 
  			}
  		}
  	}
  	
  	/**
  	 * 
  	 * @param root
  	 * @return
  	 */
  	public static int TreeDepth(TreeNode root) {
          if(root==null){
              return 0;
          }else{
              int left = 1;
              int right = 1;
              left+=TreeDepth(root.getLeft());
              right+=TreeDepth(root.getRight());
              return left>right?left:right;
          }
      }
  	
  	
  	public static void main(String[] args) {
  		TreeNode tree = new TreeNode(1);
  		TreeNode lt = new TreeNode(2);
  		TreeNode rt = new TreeNode(3);
  		tree.setLeft(lt);
  		tree.setRight(rt);
   		inOrderRecur(tree);
   		preOrderRecur(tree);
  		inOrderUnRecur(tree);
  		System.out.println(TreeDepth(tree));
  	}
  
  }
  