Tree.java

public interface Tree
     
       extends Iterable
      
        {                                                                              public int depth();                                         public int leafCount();                                     }
      
     

BTree.java

import java.util.Iterator;import java.util.NoSuchElementException;import java.util.Stack;public class BTree
     
       implements Tree
      
       {    /**     * @param args     */                                      private BNode
       
         root;                                      public BTree(BNode
        
          root){        this.root=root;    }                                      public  BTree(){        root= null;    }                                      public BNode
         
           getRoot(){        return root;    }    public void setRoot(BNode
          
            root){ this.root=root; } @Override public int depth() { // TODO Auto-generated method stub return depth(root); } private int depth(BNode
           
             node){ if(node==null){ return -1; } int leftdepth=depth(node.getLeft()); int rightdepth=depth(node.getRight()); return 1+(leftdepth > rightdepth?leftdepth:rightdepth); } @Override public int leafCount() { // TODO Auto-generated method stub return leafCount(root); } private int leafCount(BNode
            
              node){ if(node.getLeft()==null&&node.getRight()==null){ return 1; } return leafCount(node.getLeft()) + leafCount(node.getRight()); } @Override public Iterator
             
               iterator() { // TODO Auto-generated method stub return new InorderIterator(); } private class InorderIterator implements Iterator
              
               { private Stack
               
                
                 > s ; BNode
                 
                   curr; public InorderIterator() { s = new Stack
                  
                   
                    >(); curr = getFarLeft(root); } @Override public boolean hasNext() { return curr != null; } @Override public T next() { if(curr == null){ throw new NoSuchElementException("没有节点"); } T value = curr.getValue(); if(curr.getRight() != null){ curr = getFarLeft(curr.getRight()); }else if(!s.isEmpty()){ curr = s.pop(); }else{ curr = null; } return value; } @Override public void remove() { throw new RuntimeException("不支持该方法"); } /** * 得到左子树最远的左节点 * @return */ private BNode
                    
                      getFarLeft(BNode
                     
                       node){ if(node == null){ return null; } while(node.getLeft() != null){ s.push(node); node = node.getLeft(); } return node; } } }
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     

测试

import java.util.Iterator;     import junit.framework.TestCase;     public class TreeTest extends TestCase {     BinaryTree tree = new BinaryTree();     @Override     protected void setUp() throws Exception {         Tnode
     
       root = new Tnode
      
       ("root");         Tnode
       
         a = new Tnode
        
         ("a");         Tnode
         
           b = new Tnode
          
           ("b"); Tnode
           
             c = new Tnode
            
             ("c"); Tnode
             
               d = new Tnode
              
               ("d"); a.setLeft(b); a.setRight(c); root.setLeft(a); root.setRight(d); tree.setRoot(root); } public void testTree(){ System.out.println("tree height:" + tree.depth()); System.out.println("leaf node:" + tree.leafCount()); System.out.println("先序排列"); NLR(tree.getRoot()); System.out.println("中序排列"); LNR(tree.getRoot()); System.out.println("后序排列"); LRN(tree.getRoot()); System.out.println("测试遍历"); for (Iterator iterator = tree.iterator(); iterator.hasNext();) { String nodeValue = (String) iterator.next(); System.out.print(nodeValue + " "); } } /** * 先序排列 * @param node */ public void NLR(Tnode node){ if(node == null){ return; } visit(node); NLR(node.getLeft()); NLR(node.getRight()); } /** * 中序排列 * @param node */ public void LNR(Tnode node){ if(node == null){ return; } LNR(node.getLeft()); visit(node); LNR(node.getRight()); } /** * 后序排列 * @param node */ public void LRN(Tnode node){ if(node == null){ return; } LRN(node.getLeft()); LRN(node.getRight()); visit(node); } public void visit(Tnode node){ System.out.println(node.getValue()); } @SuppressWarnings("unchecked") public void testIterator(){ for (Iterator iterator = tree.iterator(); iterator.hasNext();) { String str = (String) iterator.next(); System.out.print(str + " "); } } }