1. 结点类BinaryNode

public class BinaryNode
    
      {    public T data;    public BinaryNode
     
       left ,right;    public BinaryNode(T data, BinaryNode
      
        left,BinaryNode
       
         right){        this.data = data;        this.left = left;        this.right = right;    }    public BinaryNode(T data){        this(data,null,null);    }    public BinaryNode(){this(null,null,null);};    @Override    public String toString() {        return data.toString();    }}
       
      
     
    

2. 二叉树实现类BinaryTree

import java.util.Deque;import java.util.LinkedList;/** * Created by jagery on 7/5/16. */public class BinaryTree
    
      implements BinaryTTree
     
       {    public BinaryNode
      
        root;    public BinaryTree(){this.root = null;}    //递归前根    public void preOrder() {        System.out.print("pre order:");        preOrder(root);        System.out.println();    }    //非递归前根    public void preOrderTraverse(BinaryNode
       
         p){        Deque
        
         
          > stack = new LinkedList
          
           
            >(); BinaryNode
            
              q = p; System.out.print("pre Order Traverse: "); while(q!=null || !stack.isEmpty()){ if(q!=null){ System.out.print(q.data.toString()+" "); if(q.right!=null){ stack.push(q.right); } q = q.left; }else{ q = stack.pop(); } } System.out.println(); } private void preOrder(BinaryNode
             
               p){ if(p!=null){ System.out.print(p.data.toString()+" "); preOrder(p.left); preOrder(p.right); } } //递归中根 public void inOrder() { System.out.print("in order:"); inOrder(root); System.out.println(); } private void inOrder(BinaryNode
              
                p){ if(p!=null){ inOrder(p.left); System.out.print(p.data.toString()+" "); inOrder(p.right); } } //非递归中根 public void inOrderTraverse(BinaryNode
               
                 p){ Deque
                
                 
                  > stack = new LinkedList
                  
                   
                    >(); BinaryNode
                    
                      q = p; System.out.print("in Order Traverse: "); while(q!=null || !stack.isEmpty()){ if(q!=null){ stack.push(q); q = q.left; }else{ q = stack.pop(); System.out.print(q.data.toString()+" "); q = q.right; } } System.out.println(); } //递归后根 public void postOrder() { System.out.print("post order:"); postOrder(root); System.out.println(); } //非递归后根 public void postOrderTraverse(BinaryNode
                     
                       p) { Deque
                      
                       
                        > stack = new LinkedList
                        
                         
                          >(); BinaryNode
                          
                            q = p; BinaryNode
                           
                             s = null; System.out.print("post Order Traverse: "); while(q!=null || !stack.isEmpty()){ if(q!=null){ stack.push(q); q = q.left; }else{ q = stack.peek(); if(q.right!=null && q.right!=s ){ q = q.right; }else{ q = stack.pop(); System.out.print(q.data.toString()+" "); s = q; q = null; } } } System.out.println(); } private void postOrder(BinaryNode
                            
                              p){ if(p!=null){ postOrder(p.left); postOrder(p.right); System.out.print(p.data.toString()+" "); } }}
                            
                           
                          
                         
                        
                       
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     
    

3. 测试类

public class BinaryTree_make {    public static BinaryTree
    
      make(){        BinaryTree
     
       bitree = new BinaryTree
      
       ();        BinaryNode
       
         child_f,child_d,child_b,child_c;        child_d = new BinaryNode
        
         ("D",new BinaryNode
         
          ("J"),new BinaryNode
          
           ("G")); child_b = new BinaryNode
           
            ("B",child_d,new BinaryNode
            
             ("K")); child_f = new BinaryNode
             
              ("F",new BinaryNode
              
               ("H"),null); child_c = new BinaryNode
               
                ("C",new BinaryNode
                
                 ("E"),child_f); bitree.root = new BinaryNode
                 
                  ("A",child_b,child_c); return bitree; } public static void main(String args[]){ BinaryTree
                  
                    bitree = make(); bitree.preOrder(); bitree.inOrder(); bitree.postOrder(); bitree.inOrderTraverse(bitree.root); bitree.preOrderTraverse(bitree.root); bitree.postOrderTraverse(bitree.root); }}