Wednesday, September 1, 2010

Binary Search Tree Assignment for Data Structures Class 235

The following has two classes: Tree and BinarySearchTreeHeightCalculator

/**
* BinarySearchTreeHeightCalculator by Jaimmie Riley
*
*/

//allows the program to generate random integers
import java.util.Random;

public class BinarySearchTreeHeightCalculator
{
public static void main(String[]args){
//Class to 'Tree' class by creating a new binary tree
Tree binTree = new Tree ();
//generates a random number
Random number = new Random();
int i;
//iterates 100 times to add 100 random numbers to the binary tree
for(i = 1; i<100; i++){
int randNum = number.nextInt(101);
if(randNum == 0){//ensures numbers inserted to tree are 1-100
i--;//ensures 100 numbers are placed into the tree
}//end if
else{
binTree.insert(randNum);//calls function in Tree to insert numbers into
//the binary tree.
}//end else
}//end for

//calls a function in Tree that will calculate the Right height and Left height
//of the binary tree. It will then print out the results.
binTree.calculateHeights();
}//end main
}


/**
* Tree by Jaimmie Riley with code by Doug Wightman
*
*/
/******************************Doug's Code Starts*************************************/
public class Tree
{
private class Node
{
public Node left;
public Node right;
public int data;

Node( int data ) {
this.data = data;
this.left = null;
this.right = null;
} //end Node
}//end class Node

private Node head;

public Tree() {
head = null;
} //end public Tree

/******************************Doug's Code ends*************************************/

//Function to insert an integer into a binary tree
public void insert(int num){
//if this is the first node, creating a node to add the numer
if(head == null) {
head = new Node(num);
}//end if
else {
//creates a place-holder for the root note of the binary tree
Node traverse = head;
while (traverse != null){
//Go left if the number is smaller than the placeholder
if(num < traverse.data){
if (traverse.left == null){
traverse.left = new Node(num);
return;//exit function
}//end if
else{
//advance the placeholder to the node to it's left
//until a null is found, and a new node can be added
traverse = traverse.left;
}//end else
}//end if
//Go right if the number is larger than the placeholder
else{
//if there is space for a new node to the right of the binary tree
// attach the node with the number
if (traverse.right == null){
traverse.right = new Node(num);
return;//exit function
}//end if
else{
//advance the placeholder to the node to it's right
//until a null is found, and a new node can be added
traverse = traverse.right;
}//end else
}//end else
}//end while
}//end else
}//end insert

//function used to calculate the height of tree.
//the height of the tree is calculated when this function calls countingHeight
public void calculateHeights(){
Node rightHeight = head.right;
Node leftHeight = head.left;
int rightCount;
int leftCount;

//1 must be added to the count, to include the node
//to the right of the root node in the height count
if(rightHeight != null){
rightCount = 1;
}//end if
else{
rightCount = 0;
}//end else

//1 must be added to the count, to include the node
//to the left of the root node in the height count
if(leftHeight != null){
leftCount = 1;
}//end if
//if there is no left node the neight is 0
else{
leftCount = 0;
}//end else

//calls recursive function, countingHeight, that calculates
//the height of the right-side of the tree
rightCount += countingHeight(rightHeight);

//calls recursive function, countingHeight, that calculates
//the height of the left-side of the tree
leftCount += countingHeight(leftHeight);

System.out.println("The Right-Height of the tree is: " + rightCount);
System.out.println("The Left-Height of the tree is: " + leftCount);
}//end calculateHeights

//This recursive function is used by the function calculatingHeights
//to calculate the right height and the left height of the binary search tree
public int countingHeight(Node current){
if(current == null){
return 0;
}//end if
else{
return Math.max(countingHeight(current.left), countingHeight(current.right) + 1);
}//end else
}//end countingHeight

} //end Tree

No comments:

Post a Comment