本文共 3352 字，大约阅读时间需要 11 分钟。

Statements: This blog was written by me, but most of content  is quoted from book【Data Structure with Java Hubbard】 

Here is a class for binary trees that directly implements the recursive definition. By extending the AbstractCollectionclass, it remains consistent with the Java Collections Framework.

【Implementation】

package com.albertshao.ds.tree;//  Data Structures with Java, Second Edition//  by John R. Hubbard//  Copyright 2007 by McGraw-Hillimport java.util.*;public class BinaryTree
   
     extends AbstractCollection {  protected E root;  protected BinaryTree
    
      left, right, parent;  protected int size;    public BinaryTree() {  }    public BinaryTree(E root) {    this.root = root;    size = 1;  }    public BinaryTree(E root, BinaryTree
     
       left, BinaryTree
      
        right) {    this(root);    if (left != null) {      this.left = left;      left.parent = this;      size += left.size();    }    if (right != null) {      this.right = right;      right.parent = this;      size += right.size();    }  }  public boolean equals(Object object) {    if (object == this) {      return true;    } else if (!(object instanceof BinaryTree)) {      return false;    }    BinaryTree that = (BinaryTree)object;    return that.root.equals(this.root)        && that.left.equals(this.left)        && that.right.equals(this.right)        && that.parent.equals(this.parent)        && that.size == this.size;  }  public int hashCode() {    return root.hashCode() + left.hashCode() + right.hashCode() + size;  }    public int size() {    return size;  }  public Iterator iterator() {    return new java.util.Iterator() { // anonymous inner class      private boolean rootDone;      private Iterator lIt, rIt;  // child iterators      public boolean hasNext() {        return !rootDone || lIt != null && lIt.hasNext()                         || rIt != null && rIt.hasNext();      }      public Object next() {        if (rootDone) {          if (lIt != null && lIt.hasNext()) {            return lIt.next();          }          if (rIt != null && rIt.hasNext()) {            return rIt.next();          }          return null;        }        if (left != null) {          lIt = left.iterator();        }        if (right != null) {          rIt = right.iterator();        }        rootDone = true;        return root;      }      public void remove() {        throw new UnsupportedOperationException();       }    };  }}
      
     
    
   

package com.albertshao.ds.tree;//  Data Structures with Java, Second Edition//  by John R. Hubbard//  Copyright 2007 by McGraw-Hillpublic class TestBinaryTree {  static public void main(String[] args) {    BinaryTree
   
     e = new BinaryTree
    
     ("E");    BinaryTree
     
       g = new BinaryTree
      
       ("G");    BinaryTree
       
         h = new BinaryTree
        
         ("H"); BinaryTree
         
           i = new BinaryTree
          
           ("I"); BinaryTree
           
             d = new BinaryTree
            
             ("D", null, g); BinaryTree
             
               f = new BinaryTree
              
               ("F", h, i); BinaryTree
               
                 b = new BinaryTree
                
                 ("B", d, e); BinaryTree
                 
                   c = new BinaryTree
                  
                   ("C", f, null); BinaryTree
                   
                     tree = new BinaryTree
                    
                     ("A", b, c); System.out.printf("tree: %s", tree); }}
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     
    
   

【Result】

tree: [A, B, D, G, E, C, F, H, I]

The example shows two views of the same tree. The larger view shows all the details, representing each