二叉木はノード、深さ、前の順序、中の順序、後の順序の遍歴を求めます

package xcc.test;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

import xcc.bean.TreeNode;

public class TestErCha {
	
	/**
	 *            (    )
	 * (1)       ，     0
	 * (2)        ，     =     +     +1
	 *   ：    root.left root.right        。    +1  
	 */
	public static int getNodeNumRec(TreeNode root) {  
        if (root == null) {  
            return 0;  
        } else {  
            return getNodeNumRec(root.left) + getNodeNumRec(root.right) + 1;  
        }  
    } 
	
	/**
	 *            (    )
	 * (1)       
	 * (2)      ，    
	 * (3)      ，    
	 *   ：       ，       ，    queue ，     ，    queue ，       。
	 */
	public static int getNodeNumIte(TreeNode root){
		if(root == null){
			return 0;
		}
		int count = 1;
		Queue queue = new LinkedList();
		queue.add(root);
		while(!queue.isEmpty()){
			TreeNode treeNode = queue.remove();
			if(treeNode.left != null){
				queue.add(treeNode.left);
				count++;
			}
			if(treeNode.right != null){
				queue.add(treeNode.right);
				count++;
			}
		}
		return count;
	}
	
	/**
	 *          (    )
	 * (1)       ，   0
	 * (2)        ，       = max(     ，      ) + 1
	 */
	public static int getDepthRec(TreeNode root) {  
        if (root == null) {  
            return 0;  
        } 
        int left = getDepthRec(root.left);
        int right = getDepthRec(root.right);
        return Math.max(left, right) + 1;
    } 
	
	/**
	 *          (    )
	 * (1)      
	 * (2)    node  
	 * (3)       ，           queue ，     
	 * (4)  node   0 ，          
	 * (5)       ，       
	 */
	public static int getDepthIte(TreeNode root) {  
        if (root == null) {  
            return 0;  
        } 
        int depth = 0;             //  
        int currentLevelNodes = 1; //  Level，node   
        int nextLevelNodes = 0;    //   node   
        Queue queue = new LinkedList();
		queue.add(root);
        while(!queue.isEmpty()){
        	TreeNode treeNode = queue.remove();
        	currentLevelNodes--;
        	if(treeNode.left != null){
				queue.add(treeNode.left);
				nextLevelNodes++;
			}
			if(treeNode.right != null){
				queue.add(treeNode.right);
				nextLevelNodes++;
			}
			if(currentLevelNodes == 0){//                
				depth++;               //     
				currentLevelNodes = nextLevelNodes;//            
				nextLevelNodes = 0;
			}
        }
        return depth;
    } 
	
	/**
	 *        (  )
	 * (1)       ，   
	 * (2)        ，     ，       ，       
	 */
	public static void preorderTraversalRec(TreeNode root) {  
        if (root == null) {  
            return;  
        }  
        System.out.print(root.val + " ");  
        preorderTraversalRec(root.left);  
        preorderTraversalRec(root.right);  
    }  
	
	/**
	 *        (  )
	 * (1)       ，   
	 * (2)  stack（ ）   ，    
	 * (3)       ，       
	 */
	public static void preorderTraversalIte(TreeNode root) {  
        if (root == null) {  
            return;  
        }  
        Stack stack = new Stack();      //   stack  
        stack.push(root);  
          
        while( !stack.isEmpty() ){  
            TreeNode cur = stack.pop();     //         
            System.out.print(cur.val + " ");  
              
            //    ：       ，      ，                     
            if(cur.right != null){  
                stack.push(cur.right);  
            }  
            if(cur.left != null){  
                stack.push(cur.left);  
            }  
        }    
    }
	
	/**
	 *        (  )
	 * (1)       ，   
	 * (2)        ，       ，      ，       
	 */
	public static void inorderTraversalRec(TreeNode root) {  
        if (root == null) {  
            return;  
        }  
        inorderTraversalRec(root.left);  
        System.out.print(root.val + " ");  
        inorderTraversalRec(root.right);  
    }  
	
	/**
	 *        (  )
	 * (1)                   
	 * (2)        ，           
	 */
	public static void inorderTraversalIte(TreeNode root){  
        if(root == null){  
            return;  
        }  
        Stack stack = new Stack();  
        TreeNode cur = root;  
          
        while( true ){  
            while(cur != null){     //                    
                stack.push(cur);  
                cur = cur.left;  
            }  
              
            if(stack.isEmpty()){  
                break;  
            }  
                  
            //             ，          
            cur = stack.pop();  
            System.out.print(cur.val + " ");  
            cur = cur.right;    //          
        }  
    }
	
	/** 
     *        (  )  
     * （1）       ，     
     * （2）        ，       ，       ，      
     */  
    public static void postorderTraversalRec(TreeNode root) {  
        if (root == null) {  
            return;  
        }  
        postorderTraversalRec(root.left);  
        postorderTraversalRec(root.right);  
        System.out.print(root.val + " ");  
    } 
    
    /** 
     *        (  )  
     * （1）       ，     
     * （2）        ，       ，       ，      
     */ 
    public static void postorderTraversalIte(TreeNode root) {  
        if (root == null) {  
            return;  
        }  
          
        Stack s = new Stack();      //    stack    node         
        Stack output = new Stack();//    stack       stack    
          
        s.push(root);  
        while( !s.isEmpty() ){      //                 stack  
            TreeNode cur = s.pop(); //            stack  
            output.push(cur);         
              
            if(cur.left != null){       //                      stack  
                s.push(cur.left);  
            }  
            if(cur.right != null){  
                s.push(cur.right);  
            }  
        }  
          
        while( !output.isEmpty() ){ //        stack，        
            System.out.print(output.pop().val + " ");  
        }  
    }  

	public static void main(String[] args) {
		/*
                 1  
                / \  
               2   3  
              / \   \  
             4  5   6
		 */
		TreeNode r1 = new TreeNode(1);  
        TreeNode r2 = new TreeNode(2);  
        TreeNode r3 = new TreeNode(3);  
        TreeNode r4 = new TreeNode(4);  
        TreeNode r5 = new TreeNode(5);  
        TreeNode r6 = new TreeNode(6);   
          
        r1.left = r2;  
        r1.right = r3;  
        r2.left = r4;  
        r2.right = r5;  
        r3.right = r6; 
 
        
        TestErCha.postorderTraversalRec(r1);	
	}
}