bstproject

Class BSTTree

java.lang.Object

bstproject.BSTTree

public class BSTTree
extends java.lang.Object

BSTTree defines a binary search tree - each node contains a list of crime records. The tree is organized on the street address of the crime. Street addresses that are alphabetically less than the current node are placed in the left subtree. Street addresses that are alphabetically greater than the current node are placed in the right subtree. Street addresses that are alphabetically equal to the current node are placed at the end of the list at that node. The class has one internal reference. This is the reference to the root of the tree. The class holds an integer that counts how many total crimes are in the tree. It also holds an integer counting how many nodes are in the tree, i.e., how many distinct addresses there are.

Constructor Summary

Constructors

Constructor and Description
BSTTree() Constructor to set root to null and the two counters to zero
BSTTree(java.lang.String filePathAndName) Constructor to initialize the tree by loading the tree with all data from the crime report file.

Method Summary

Modifier and Type	Method and Description
CrimeRecordList	bruteForceSearch(CrimeRecord n, double distance)
BSTTreeNode	getChampionPtr()
int	getChampionVal()
int	getCrimeCount()
int	getDistinctCrimeLocations()
static void	go(java.lang.String x)
int	inOrderFindChampion() This method would normally be public.
void	inOrderFindChampion(BSTTreeNode t) This method would normally be private.
void	inOrderPrint() This method would normally be public.
void	inOrderPrint(BSTTreeNode t) This method would normally be private.
void	inOrderSearch(BSTTreeNode t, CrimeRecord n, CrimeRecordList resultList, double distance)
CrimeRecordList	lookUp(java.lang.String address) This method finds all crime reports at this address.
void	preOrderPrint() This method would normally be public.
void	preOrderPrint(BSTTreeNode t) This method would normally be private.
void	readTree(java.lang.String crimeDataLocation) This routine handles the actial reading of the file.
static void	sto(java.lang.String x)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

BSTTree

public BSTTree()

Constructor to set root to null and the two counters to zero

BSTTree

public BSTTree(java.lang.String filePathAndName)

Constructor to initialize the tree by loading the tree with all data from the crime report file. pre: filePathname points to the crime file post: the tree is constructed with the crime data

Parameters:

filePathAndName -

Method Detail

getChampionVal

public int getChampionVal()

getChampionPtr

public BSTTreeNode getChampionPtr()

readTree

public void readTree(java.lang.String crimeDataLocation)
              throws java.lang.Exception

This routine handles the actial reading of the file. It is called by a constructor.

Parameters:

crimeDataLocation - is the lcation of the crime file

Throws:

java.lang.Exception

getCrimeCount

public int getCrimeCount()

getDistinctCrimeLocations

public int getDistinctCrimeLocations()

preOrderPrint

public void preOrderPrint(BSTTreeNode t)

This method would normally be private. It is called by preOrderPrint(), passing the root in as the argument. This is a recursive method that visits each node in pre-order. On each visit, the entire list of crimes is displayed.

Parameters:

t -

preOrderPrint

public void preOrderPrint()

This method would normally be public. It calls the recursive pre-orderprint.

inOrderPrint

public void inOrderPrint(BSTTreeNode t)

This method would normally be private. It is called by inOrderPrint(), passing the root in as the argument. This is a recursive method that visits each node in in-order. On each visit, the entire list of crimes is displayed.

Parameters:

t -

inOrderPrint

public void inOrderPrint()

This method would normally be public. It calls the recursive pre-orderprint.

inOrderFindChampion

public void inOrderFindChampion(BSTTreeNode t)

This method would normally be private. It is called by inOrderFindChampion(), passing the root in as the argument. This is a recursive method that visits each node in in-order. On each visit, the size of the list is examined. If this list is larger than the old champion, the new champion becomes this list.

Parameters:

t -

inOrderFindChampion

public int inOrderFindChampion()

This method would normally be public. It calls the recursive pre-orderprint.

lookUp

public CrimeRecordList lookUp(java.lang.String address)

This method finds all crime reports at this address. The input is a simple string with an address. The result returned is a list of crimes at that address, or a null if there are no crimes found.

bruteForceSearch

public CrimeRecordList bruteForceSearch(CrimeRecord n,
                                        double distance)

Parameters:

n - contains a crime record of a crime in the tree

distance - is a distance in feet

Returns:

a crime list with those crimes within this distance from n

inOrderSearch

public void inOrderSearch(BSTTreeNode t,
                          CrimeRecord n,
                          CrimeRecordList resultList,
                          double distance)

Parameters:

t - points to a node in the tree, below which, this code will search all crimes.

n - is a reference to a crime record with (x,y) state plane coordinates

resultList - contains a pointer to the list we are building

distance - the search finds crimes within this distance in feet.

go

public static void go(java.lang.String x)

sto

public static void sto(java.lang.String x)