ツリーの作成と遍歴

package test;

import java.util.ArrayDeque;
import java.util.LinkedList;  
import java.util.List;  
  
/** 
 *   ：             ，    3       
 *  
 *     0:    (C   )    
 *  
 *     1：http://zhidao.baidu.com/question/81938912.html 
 *  
 *     2：http://cslibrary.stanford.edu/110/BinaryTrees.html#java 
 *  
 * @author [email protected] @date: 2011-5-17 
 *  
 */  
public class BinTreeTraverse2 {  
  
    private int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };  
    private static List<Node> nodeList = null;  
  
    /** 
     *    ：   
     *  
     * @author [email protected] @date: 2011-5-17 
     *  
     */  
    private static class Node {  
        Node leftChild;  
        Node rightChild;  
        int data;  
  
        Node(int newData) {  
            leftChild = null;  
            rightChild = null;  
            data = newData;  
        }  
    }  
  
    public void createBinTree() {  
        nodeList = new LinkedList<Node>();  
        //             Node    
        for (int nodeIndex = 0; nodeIndex < array.length; nodeIndex++) {  
        	Node node = new Node(array[nodeIndex]);
            nodeList.add(node);  
        }  
        //   lastParentIndex-1                          
        for (int parentIndex = 0; parentIndex < array.length / 2 - 1; parentIndex++) {  
            //      
            nodeList.get(parentIndex).leftChild = nodeList.get(parentIndex * 2 + 1);  
            //      
            nodeList.get(parentIndex).rightChild = nodeList.get(parentIndex * 2 + 2);  
        }  
        //        :                ，           
        int lastParentIndex = array.length / 2 - 1;  
        //      
        nodeList.get(lastParentIndex).leftChild = nodeList.get(lastParentIndex * 2 + 1);  
        //    ,                  
        if (array.length % 2 == 1) {  
            nodeList.get(lastParentIndex).rightChild = nodeList.get(lastParentIndex * 2 + 2);  
        }  
    }  
  
    /** 
     *      
     *  
     *                ，            
     *  
     * @param node 
     *                  
     */  
    public static void preOrderTraverse(Node node) {  
        if (node == null)  
            return;  
        System.out.print(node.data + " ");  
        preOrderTraverse(node.leftChild);  
        preOrderTraverse(node.rightChild);  
    }  
  
    /** 
     *      
     *  
     *                ，            
     *  
     * @param node 
     *                  
     */  
    public static void inOrderTraverse(Node node) {  
        if (node == null)  
            return;  
        inOrderTraverse(node.leftChild);  
        System.out.print(node.data + " ");  
        inOrderTraverse(node.rightChild);  
    }  
  
    /** 
     *      
     *  
     *                ，            
     *  
     * @param node 
     *                  
     */  
    public static void postOrderTraverse(Node node) {  
        if (node == null)  
            return;  
        postOrderTraverse(node.leftChild);  
        postOrderTraverse(node.rightChild);  
        System.out.print(node.data + " ");  
    }  
  
    
    public static void depthOrderTraversal(Node root){
        if(root==null){
            System.out.println("empty tree");
            return;
        }       
        ArrayDeque<Node> stack=new ArrayDeque<Node>();
        //          deque        。
        stack.push(root);       
        while(stack.isEmpty()==false){
        	//      deque              。
            Node node=stack.pop();
            System.out.print(node.data+"    ");
            if(node.rightChild!=null){
                stack.push(node.rightChild);
            }
            if(node.leftChild!=null){
                stack.push(node.leftChild);
            }           
        }
        System.out.print("
");
    }

    
    /**
     *       
     *        
     *         ：  
     */
    public static void levelOrderTraversal(Node root){
        if(root==null){
            System.out.println("empty tree");
            return;
        }
        ArrayDeque<Node> queue=new ArrayDeque<Node>();
        queue.add(root);
        while(queue.isEmpty()==false){
        	//         deque        。
            Node node=queue.remove();
            System.out.print(node.data+"    ");
            if(node.leftChild!=null){
                queue.add(node.leftChild);
            }
            if(node.rightChild!=null){
                queue.add(node.rightChild);
            }
        }
        System.out.print("
");
    }
    
    public static void main(String[] args) {  
        BinTreeTraverse2 binTree = new BinTreeTraverse2();  
        binTree.createBinTree();  
        // nodeList  0             
        Node root = nodeList.get(0);  
  
        System.out.println("    ：");  
        preOrderTraverse(root);  
        System.out.println();  
  
        System.out.println("    ：");  
        inOrderTraverse(root);  
        System.out.println();  
  
        System.out.println("    ：");  
        postOrderTraverse(root);  
        
        System.out.println("    ：");  
       depthOrderTraversal(root);
        
        System.out.println("    ：");  
       levelOrderTraversal(root);
    }  
  
}