Binary Tree

BinaryNode.java

public class BinaryNode<E> {
    E element;
    BinaryNode<E> left, right;

    public BinaryNode(E element) {
	this.element = element;
	left = right = null;
    }

    public E getElement() {
	return element;
    }

    public BinaryNode<E> getLeft() {
	return left;
    }

    public BinaryNode<E> getRight() {
	return right;
    }
}

BinarySearchTree.java

import java.util.*;

public class BinarySearchTree<E extends Comparable<? super E>> {
    private BinaryNode<E> root;

    /**
     * Construct an empty binary searchtree
     */
    public BinarySearchTree() {
	root = null;
    }

    /**
     * Return a reference to the root of the tree
     */
    public BinaryNode<E> getRoot() {
	return root;
    }
    
    /**
     * Insert a new item in tree.
     * @param x the item to insert.
     */
    public void insert(E x) {
	
	if(root == null) {
	    
	    root = new BinaryNode<E>(x);
	}
	else
	insert(x,root);		
    }
	
    private void insert(E x, BinaryNode<E> node) {

	if(x.compareTo(node.getElement()) < 0) {
	    
	    if(node.left == null)
	    node.left = new BinaryNode<E>(x);
	    else
		insert(x,node.getLeft());
	}
	else if(x.compareTo(node.getElement()) >= 0){

	    if(node.getRight() == null)
	    node.right = new BinaryNode<E>(x);
	    else 
		insert(x,node.getRight());
	}
    }
   
    /**
     * Compute height of tree.
     */
    public int height() {
	return height(root);
    }

    /**
     * Print tree contents inorder.
     */
    public void printTree() {
	if (root != null) {
	    printTree(root);
	}
    }
   
    /**
     * Rebuild tree. The result is a complete tree.
     */
    public void rebuild() {
	E[] contents = inorderArray();
	root = buildTree(contents, 0, contents.length-1);
    }

    /* ----------------   Auxiliary private methods -----------------*/

    private int height(BinaryNode<E> n) {
	if (n == null) {
	    return -1;
	} else {
	    return 1 + Math.max(height(n.left), height(n.right));
	}
    }

   
    private void printTree(BinaryNode<E> n) {
	if (n.left != null) {
	    printTree(n.left);
	}
	System.out.println(n.element);
	if (n.right != null) {
	    printTree(n.right);
	}
    }
   
      
    /* Construct an array of items in tree in ascending order */
    private E[] inorderArray() {
	LinkedList<E> list = new LinkedList<E>();
	if (root != null) {
	    inorderList(root,list);
	}
	return  (E[]) list.toArray((E[]) new Comparable[1]);
    }

    /* Add items from tree rooted at n in inorder to the linked list */
    private void inorderList(BinaryNode<E> n, LinkedList<E> list) {
	if (n.left != null) {
	    inorderList(n.left,list);
	}
	list.add(n.element);
	if (n.right != null) {
	    inorderList(n.right,list);
	}
    }

    /* Build a complete tree from the elements a[first]..a[last].
       Elements in a are assumed to be in ascending order.
       Return root of tree.                               
    */
    private BinaryNode<E> buildTree(E[] a, int first, int last) {

	if(last - first == 1) {
	    
	    BinaryNode<E> node = new BinaryNode<E>(a[first]);
	    node.right = new BinaryNode<E>(a[last]);

	    return node;
	}
	else if(last - first == 0) {

	    return new BinaryNode<E>(a[first]);
	}
	else {

	    int mindex = (first + last)/2;
	
	    BinaryNode<E> node = new BinaryNode<E>(a[mindex]);
	
	    node.left = buildTree(a,first, mindex-1);
	    node.right = buildTree(a,mindex+1, last);
	    return node;
	}

    }
	
   
}

BinaryTest.java

public class BinaryTest {

public static void main(String[] args) {

    BinarySearchTree<Integer> tree = new BinarySearchTree<Integer>();

    BinaryNode<Integer> nodes[] = (BinaryNode<Integer>[])(new BinaryNode[10]);

    //for(int i=0;i<5;i++) {
	//nodes[i] = new BinaryNode<Integer>(new Integer(i));
    //tree.insert(nodes[i].element);
    //}

    tree.insert(new Integer(1));
    tree.insert(new Integer(3));
    tree.insert(new Integer(5));
    tree.insert(new Integer(7));
    tree.insert(new Integer(9));
    tree.insert(new Integer(11));
    tree.insert(new Integer(13));

    tree.rebuild();

    BSTVisualizer vis = new BSTVisualizer("Test", 300, 200);
    vis.drawTree(tree);
    

}

}

BSTVisualizer.java

import java.awt.*;

import se.lth.cs.ad.drawing.*;

public class BSTVisualizer {
    private DrawingArea canvas;

    // diameter of nodes;
    private final static int DIAMETER = 20;
    // horizontal distance  between nodes on same level
    private final static int HORIZONTAL_DIST = 10;
    // vertical distance between levels
    private final static int VERTICAL_DIST = 10;
    // distance between node (circle) center and content string 
    private final static int OFFSET = -10;

    /**
     * Create a canvas with a certain title, width, height.
     */
    public BSTVisualizer(String title, int width, int height) {
	canvas = new DrawingArea(title, width, height, Color.white);
    }

    /**
     * Draw a binary search tree on the canvas.
     */
    public void drawTree(BinarySearchTree<?> bst) {

	int inorder=0;
	System.out.println(bst.getRoot().getClass().getName());
	drawNode(bst.getRoot(), (int)Math.pow(2,bst.height()), 1, bst.height(), 0, 0);

    }

    private void drawNode(BinaryNode node, int nbr, int level, int height, int x, int y) {

	int ix = computeXpos(nbr);
	int iy = computeYpos(level);

	if(x != 0 && y != 0)
	    canvas.drawLine(x,y,ix,iy);

	canvas.fillCircle(Color.red, ix, iy, DIAMETER);	
	
	canvas.drawString(node.getElement().toString(),ix+10,iy+3);

	if(node.getLeft() != null)
	      drawNode(node.getLeft(), nbr - (int)Math.pow(2,height-1), level+1,height-1,ix,iy);

	if(node.getRight() != null)
	    drawNode(node.getRight(), nbr + (int)Math.pow(2,height-1), level+1,height-1,ix,iy);
    }

    /* ------   Private auxiliary methods --------------*/

    /* Compute y-position of a node from its level. */
    private int computeYpos(int level) {
	return level*(DIAMETER+VERTICAL_DIST);
    }

    /* Compute x-position of a node from its inordernumber. */
    private int computeXpos(int actNodeNbr) {
	return actNodeNbr*(DIAMETER + HORIZONTAL_DIST);
    }
    
}