那位给一个二叉树的代吗。java的。

Question

那位给一个二叉树的代吗。java的。急。。

Answer 1

我有一个二叉查找树的代码集合，拿出来分享一下，做得不好还望多指教，呵呵/**
 *: BinarySearchTree.java
 * @author YangJun
 */
import java.io.*;public class BinarySearchTree {
  // -------------- Public methods --------------
  public BinarySearchTree() { root = null; }
  public void clear() { root = null; }
  public boolean isEmpty() { return root == null; }

  public Comparable find( Comparable x ) { return elementAt( find( x, root ) ); }
  public Comparable findMin() { return elementAt( findMin( root ) ); }
  public Comparable findMax() { return elementAt( findMax( root ) ); }

  public void insert( Comparable x ) { root = insert( x, root ); }
  public void remove( Comparable x ) { root = remove( x, root ); }

  // Print the tree contents in sorted order.
  public void printTree() {
    if( isEmpty() )
      System.out.println( "Empty tree." );
    else
      printTree( root, 0 );
  }

  // -------------- Private fields --------------
  private BinaryNode root; // The root
  
  // -------------- Internal methods --------------
  // Various private methods; mostly recursive.
  private Comparable elementAt( BinaryNode t ) {
    return t == null ? null : t.element;
  }

  /**
   * Internal method to find an item in a subtree.
   * @param x is item to search for.
   * @param t the node that roots the tree.
   * @return node containing the matched item.
   */
  private BinaryNode find( Comparable x, BinaryNode t ) {
    if( t == null )
      return null;
    if( x.compareTo( t.element ) < 0 )
      return find( x, t.left );
    else if( x.compareTo( t.element ) > 0 )
      return find( x, t.right );
    else
      return t; // Match
  }
  /**
   * Internal method to find the smallest item in a subtree.
   * @param t the node that roots the tree.
   * @return node containing the smallest item.
   */
  private BinaryNode findMin( BinaryNode t ) {
    if( t == null )
      return null;
    else if( t.left == null )
      return t;
    return findMin( t.left );
  }
  /**
   * Internal method to find the largest item in a subtree.
   * @param t the node that roots the tree.
   * @return node containing the largest item.
   */
  private BinaryNode findMax( BinaryNode t ) {
    if( t != null )
    while( t.right != null )
      t = t.right;
    return t;
  }

  /**
   * Internal method to insert into a subtree.
   * @param x the item to insert.
   * @param t the node that roots the tree.
   * @return the new root.
   */
  private BinaryNode insert( Comparable x, BinaryNode t ) {
    if( t == null )
      t = new BinaryNode( x );
    else if( x.compareTo( t.element ) < 0 )
      t.left = insert( x, t.left );
    else if( x.compareTo( t.element ) > 0 )
      t.right = insert( x, t.right );
    else
      ; // Duplicate; do nothing
    return t;
  }
  /**
   * Internal method to remove from a subtree.
   * @param x the item to remove.
   * @param t the node that roots the tree.
   * @return the new root.
   */
  private BinaryNode remove( Comparable x, BinaryNode t ) {
    if( t == null )
      return t; // Item not found; do nothing.
    if( x.compareTo( t.element ) < 0 )
      t.left = remove( x, t.left );
    else if( x.compareTo( t.element ) > 0 )
      t.right = remove( x, t.right );
    else if( t.left!=null && t.right!=null ) { // Two children
      t.element = findMin( t.right ).element;
      t.right = remove( t.element, t.right );
    }
    else
      t = ( t.left != null ) ? t.left : t.right;
    return t;
  }

  /**
   * Internal method to print a subtree in sorted
   * @param t the node that the roots of the subtree.
   * @param retraction that space between roots of his children.
   */
  private void printTree( BinaryNode t, int retraction ) {
    if( t != null ) {
      printTree( t.left, retraction + 1 );
      String s = "";
      for( int i=0; i<retraction; i++ )
        s += "    ";
      System.out.println( s + t.element );
      printTree( t.right, retraction + 1 );
    }
  }  /**
   *: BinaryNode class
   * Stored information of the node in a tree that
   * element of node,   
   * left child reference and right child reference.
   * @author YangJun
   * @creation 2005/04/04 01:00
   */
  class BinaryNode {
    // Friendly data; accessible by other package routines
    Comparable element; // The data in the node
    BinaryNode left; // Left child
    BinaryNode right;  // Right child

    // Constructors
    BinaryNode( Comparable element ) { this( element, null, null ); }
    BinaryNode( Comparable element, BinaryNode left, BinaryNode right ) {
      this.element = element;
      this.left = left;
      this.right = right;
    }
  }
} /// @.@||~