This project works with binary trees and the multitude of data structures that are related to or associated with them. It explores creative modifications to many of them, such as depth-first additions in the BinarySearchTree
class and a custom sorting convention similar to a PriorityQueue
in the Heap
class.
BinaryTree
BinarySearchTree
andSet
Heap
andPriorityQueue
Stack
Node
LinkedList
Queue
This class was written as part of a group project by Tony Tan, Jimmy Pham, Ward Bradt, and Miles McCain.
This Stack
class contains the following features:
- A no-args constructor
public boolean empty()
-- Tests if this stack is empty.public T peek()
-- Looks at the object at the top of this stack without removing it from the stack.public T pop()
-- Removes the object at the top of this stack and returns that object as the value of this function.public T push(T item)
-- Pushes an item onto the top of this stack.public int search(Object o)
-- Returns the 1-based position where an object is on this stack. If the object o occurs as an item in this stack, this method returns the distance from the top of the stack of the occurrence nearest the top of the stack; the topmost item on the stack is considered to be at distance 1. The equals method is used to compare o to the items in this stack.public String toString()
-- Returns an attractive printout of the whole stack. (Note that this cannot be completed with the public API, unless you make a copy of the stack. No need to stick to only public methods for this implementation!)
A Node
object is very similar to a BinaryTree
and lays out the foundation for many binary tree classes. Each Node
object holds a reference to a T contents
, a Node<T> parent
, a Node<T> left
, and a Node<T> right
.
This is an implementation of a basic linked list data structure.
This LinkedList
class contains:
- A "root contents" constructor
boolean add(T o)
-- Adds the elemento
at the endboolean add(int index, T o)
-- Adds the elemento
at the specified position.T get(int index)
-- Returns the element at the specified position in this list.boolean contains(T o)
-- returnstrue
ifo
is the list.int indexOf(T o)
-- returns the index of the first occurrence of the specified element in this list, or -1 if this list does not contain the element.int size()
-- Returns the number of elements in this list.void clear()
-- Removes all elements of the list.T remove(int index)
-- Removes and returns the element at the specified position in this list.String toString()
-- Returns a String output of the list, suitable for printing.
An object of type Queue
follows a "first-in first-out" convention. Each Queue
holds a reference to a Queue
object next
, thus providing the connections for this data structure.
This Queue
class contains:
- A no-args constructor
- A "root contents" constructor
public Iterator<T> iterator()
-- Returns an iterator over theQueue
object from front to backpublic int size()
-- Returns the number of elements currently in the queue.public boolean isEmpty()
-- Returns if the queue contains any elements.public boolean add(T o)
-- Addso
to the end of the queue.public T peek()
-- Returns the front-most element.public boolean addQueue(Queue<T> other)
-- Appendsother
to the end of the queue.
An object of type BinaryTree
constitutes an entire binary tree. A node of this binary tree will use a helper class Node
. A binary tree is a data structure where every node has two child nodes, usually called left
and right
. The node that other classes have access to is usually called the root
node.
This BinaryTree
class contains:
- A no-args constructor
public boolean empty()
-- Test if this tree is empty.public void clear()
-- Empty the tree.public boolean add(T item)
-- Additem
to the first available spot in a breadth-first traversal of the tree. Returns whetheritem
was successfully added (for now, alwaystrue
).public boolean addLeft(Node<T> n, T item)
-- Additem
as theleft
child ofn
, so long asn.left
is currentlynull
. Returns whetheritem
was successfully added.public boolean addRight(Node<T> n, T item)
-- Additem
as theright
child ofn
, so long asn.right
is currentlynull
. Returns whetheritem
was successfully added.public void remove(T item) throws NullPointerException
-- Remove from the tree the first occurrence ofitem
in a breadth-first traversal of the tree. Returnpublic boolean contains(T item)
-- Determines ifitem
is in the tree. Throws aNullPointerException
if no nodes in the tree containitem
.public Node<T> get(T item) throws NullPointerException
-- Returns (a reference to) the firstNode
in the tree (under a breadth-first search) containingitem
. Throws aNullPointerException
if no nodes in the tree containitem
.public java.util.Iterator<T> breadthFirst()
-- Return an iterator over the tree in a breadth-first order, skippingnull
nodes.public java.util.Iterator<T> depthFirst()
-- Return an iterator over the tree in a depth-first order, skippingnull
nodes.- Any other methods you need in order to make the below classes work!
A binary search tree is a binary tree that is ordered (so it's contents T
must be Comparable
) such that any Node n
satisfies the property: n.left
and any of its children compare to smaller than n
, and n.right
and any of its children compare to larger than n
.
This BinarySearchTree
class contains:
- A no-args constructor
public boolean empty()
-- Test if this tree is empty.public void clear()
-- Empty the tree.public boolean add(T item)
-- Additem
in a valid spot. Returns whetheritem
was successfully added (for now, alwaystrue
).public boolean remove(T item)
-- Remove from the tree one occurrence ofitem
in the tree, without removing anything else (Don't lop off entire limbs).public boolean contains(T item)
-- Determines ifitem
is in the tree.public java.util.Iterator<T> sorted(boolean reversed)
-- Return an iterator over the tree in sorted order, possiblyreversed
.
A set is a container that contains at most one of any element. Thus, your contents T
should have a valid equals
method. A Set
should use a BinarySearchTree
to perform its functionality.
Your Set
class should contain:
- A no-args constructor
public boolean empty()
-- Test if this set is empty.public void clear()
-- Empty the set.public boolean add(T item)
-- Additem
. Returns whetheritem
was successfully added, which isfalse
precisely when another copy ofitem
is already in the set.public void remove(T item)
-- Removeitem
from the set.public boolean contains(T item)
-- Determines ifitem
is in the set.public Set union(Set other)
-- performs the union ofthis
withother
, i.e. the set containing all the elements ofthis
orother
.public Set intersection(Set other)
-- performs the intersection ofthis
withother
, i.e. the set containing all the elements present in boththis
andother
.- Fun Aside: Create a
main
method forSet
that takes in the name of a text file via command-line argument and creates an ordered dictionary of words in the text, output as another text file with one word per line.
This implementation of a binary search tree follows a custom ordering resembling that of a priority queue.
A heap is a tree that satisfies the heap property: every node n
has the property that both n.left
(and all its children) and n.right
(and all its children) compare to being less than n
(This is sometimes referred to as the max-heap property, and their are similarly min-heaps). Note again that T
must be Comparable
to make this happen.
Your Heap
class should contain:
- A no-args constructor
public boolean add(T item)
-- Additem
to the heap in a valid spot. Returns whetheritem
was successfully added (alwaystrue
).public T extractMax()
-- Returns the maximum object, then removes that object from the heap. Note that the maximum object is the root, so this method should reset theroot
.public T max()
-- Returns the maximum objectpublic boolean contains(T item)
-- Determines ifitem
is in the heap.public boolean empty()
-- Test if this heap is empty.public java.util.Iterator<T> iterate()
-- Returns an iterator over its elements in order of largest to smallest.public int size()
-- Returns the number of elements currently in the heap.public void clear()
-- Empty the heap.
A Priority Queue is a queue (first-in, first-out, otherwise known as a line) where items are ordered by their natural comparisons, and instead of taking from the "front of the line" you take the highest priority element. A PriorityQueue
should use a Heap
to perform its functionality.
- A no-args constructor
public boolean add(T item)
-- Additem
to the "back" of the queue, then propagate the item to the proper place in the queue. Returns whetheritem
was successfully added (alwaystrue
).public T next()
-- Return the highest priority item from the queue, removing it in the process.public T peekNext()
-- Return the highest priority item from the queue.public boolean contains(T item)
-- Determines ifitem
is in the queue.public int size()
-- Returns the number of elements currently in the queue.
- All of these classes were written as part of the coursework in my "Data Structures and Algorithms" class. Nicholas Zufelt, the teacher of that class, wrote the descriptions for some of these data structures' methods.
- http://algs4.cs.princeton.edu/32bst/BST.java.html
- http://stackoverflow.com/questions/5262308/how-do-implement-a-breadth-first-traversal