二叉树遍历 先序 中序 后序

http://bbs.tarena.com.cn/archiver/tid-231693.html

 

http://www.ccidedu.com/art/1925/20040923/158319_1.html

 

public class BinaryNode {  
    private int value;//current value  
    private BinaryNode lChild;//left child  
    private BinaryNode rChild;//right child  
      
    public BinaryNode(int value, BinaryNode l, BinaryNode r){  
        this.value = value;  
        this.lChild = l;  
        this.rChild = r;  
    }  
      
    public BinaryNode getLChild() {  
        return lChild;  
    }  
    public void setLChild(BinaryNode child) {  
        lChild = child;  
    }  
    public BinaryNode getRChild() {  
        return rChild;  
    }  
    public void setRChild(BinaryNode child) {  
        rChild = child;  
    }  
    public int getValue() {  
        return value;  
    }  
    public void setValue(int value) {  
        this.value = value;  
    }  
      
    //iterate all node.  
    public static void iterate(BinaryNode root){   //这个遍历方法和中序遍历一样
        if(root.lChild!=null){  
            iterate(root.getLChild());  
        }  
        System.out.print(root.getValue() + " ");   
        if(root.rChild!=null){  
            iterate(root.getRChild());  
        }
    }  
      
    /** 
     * add child to the current node to construct a tree. 
     * Time: O( nlog(n) ) 
     * **/ 
    public void addChild(int n){     //创建二叉树
        if(n<value){  
            if(lChild!=null){  
                lChild.addChild(n); 
            }  
            else{  
                lChild = new BinaryNode(n, null, null);  
            }  
        }  
        else{  
            if(rChild!=null){  
                rChild.addChild(n);  
            }  
            else{  
                rChild = new BinaryNode(n, null, null);  
            }  
        }  
    }  
      
    //test case.  
    public static void main(String[] args){  
        System.out.println();  
        int[] arr = new int[]{23,54,1,65,9,3,100};  
        BinaryNode root = new BinaryNode(arr[0], null, null);    //根结点
        for(int i=1; i<arr.length; i++){  
            root.addChild(arr[i]);                                      //构造二叉树
        }  
        BinaryNode.iterate(root);  //1 3 9 23 54 65 100
       
        System.out.println("*****************");
        root.preorder(root); //23 1 9 3 54 65 100  先序
        root.inorder(root);  //1 3 9 23 54 65 100 中序
        root.postorder(root); //3 9 1 100 65 54 23 后序
    }  
   
    public void preorder(BinaryNode p){   //先根次序遍历二叉树
       if(p!=null){
        System.out.print(p.value+" ");
        preorder(p.lChild);
        preorder(p.rChild);
       }
      }
     
      public void inorder(BinaryNode p){    //中根次序遍历二叉树
       if(p!=null){
        inorder(p.lChild);
        System.out.print(p.value+" ");
        inorder(p.rChild);
       }
      }
     
      public void postorder(BinaryNode p){   //后根次序遍历二叉树
       if(p!=null){
        postorder(p.lChild);
        postorder(p.rChild);
        System.out.print(p.value+" ");
       }
      }
}