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