学步园

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-Hill

import java.util.*;

public class BinaryTree<E> extends AbstractCollection {
  protected E root;
  protected BinaryTree<E> left, right, parent;
  protected int size;
  
  public BinaryTree() {
  }
  
  public BinaryTree(E root) {
    this.root = root;
    size = 1;
  }
  
  public BinaryTree(E root, BinaryTree<E> left, BinaryTree<E> 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(); 
      }
    };
  }
}

【Test】

package com.albertshao.ds.tree;

//  Data Structures with Java, Second Edition
//  by John R. Hubbard
//  Copyright 2007 by McGraw-Hill


public class TestBinaryTree {
  static public void main(String[] args) {
    BinaryTree<String> e = new BinaryTree<String>("E");
    BinaryTree<String> g = new BinaryTree<String>("G");
    BinaryTree<String> h = new BinaryTree<String>("H");
    BinaryTree<String> i = new BinaryTree<String>("I");
    BinaryTree<String> d = new BinaryTree<String>("D", null, g);
    BinaryTree<String> f = new BinaryTree<String>("F", h, i);
    BinaryTree<String> b = new BinaryTree<String>("B", d, e);
    BinaryTree<String> c = new BinaryTree<String>("C", f, null);
    BinaryTree<String> tree = new BinaryTree<String>("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
object reference with an arrow.