cse1030.datastructures

Class BinarySearchTree<E extends Comparable<? super E>>

java.lang.Object

cse1030.datastructures.BinarySearchTree<E>

Type Parameters:

E - the type of the data stored in the nodes of the binary search tree

public class BinarySearchTree<E extends Comparable<? super E>>
extends Object

A binary search tree class.

A binary search tree is a binary tree where values are stored in the tree according to three rules:

1. values in the left subtree are less than values in the root node
2. values in the right subtree are greater than or equal to values in the root node
3. rules 1 and 2 apply recursively to every subtree

Author:

CSE1030

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	BinarySearchTree.Node<E> A class that represents nodes in the binary search tree.

Constructor Summary

Constructors

Constructor and Description
BinarySearchTree() Create an empty binary search tree.

Method Summary

Methods

Modifier and Type	Method and Description
void	add(E element) Add an element to the tree.
String	bfs() Returns a string representation of the breadth first search traversal of the tree.
BinarySearchTree.Node<E>	getRoot() Get the root node of the tree.
static void	main(String[] args)
String	preOrder() Returns a string representation of the preorder traversal of the tree.
String	toString() Return a string representation of the inorder traversal of the tree.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

BinarySearchTree

public BinarySearchTree()

Create an empty binary search tree.

Method Detail

getRoot

public BinarySearchTree.Node<E> getRoot()

Get the root node of the tree. For testing purposes only.

Returns:

the root node of the tree.

add

public void add(E element)

Add an element to the tree. The element is inserted into the tree in a position that preserves the definition of a binary search tree.

Parameters:

element - the element to add to the tree

toString

public String toString()

Return a string representation of the inorder traversal of the tree.

The string is made up of the elements stored in the tree separated by commas; the entire list of elements is enclosed in braces. The elements are in ascending sorted order.

Overrides:

toString in class Object

See Also:

Object.toString()

Returns:

a string representation of the tree

preOrder

public String preOrder()

Returns a string representation of the preorder traversal of the tree.

The string is made up of the elements stored in the tree separated by commas; the entire list of elements is enclosed in braces.

Returns:

a string representation of the preorder traversal of the tree

bfs

public String bfs()

Returns a string representation of the breadth first search traversal of the tree.

The string is made up of the elements stored in the tree separated by commas; the entire list of elements is enclosed in braces. The breadth first search traversal for any node of the tree visits the node, followed by the left child of the node, followed by the right child of the node.

Returns:

a string representation of the breadth first search traversal of the tree

main

public static void main(String[] args)