Below is my project code, I have highline in red color TO DO !! import java.util
ID: 3534340 • Letter: B
Question
Below is my project code, I have highline in red color TO DO !!
import java.util.AbstractSet;
import java.util.Iterator;
import java.util.NoSuchElementException;
/**
* Binary search tree implementation of the Set interface. The contains() and
* remove() methods of AbstractSet are overridden to search the tree without
* using the iterator. Instances of this class always maintain node counts; that
* is, the count() method of the BSTNode interface is implemented to be O(1).
* If constructed with the isSelfBalancing flag true, instances of this tree are
* self-balancing: whenever an add(), remove(), or Iterator.remove() operation
* causes any node to become unbalanced, a rebalance operation is automatically
* performed at the highest unbalanced node.
*/
public class BalancedBSTSet<E extends Comparable<? super E>> extends AbstractSet<E>
{
/**
* Root of this tree.
*/
protected Node root;
/**
* Number of elements in this tree.
*/
protected int size;
/**
* Node type for this implementation.
*/
protected class Node implements BSTNode<E>
{
public Node left;
public Node right;
public Node parent;
public E data;
public Node(E key, Node parent)
{
this.data = key;
this.parent = parent;
}
@Override
public BSTNode<E> left()
{
return left;
}
@Override
public BSTNode<E> right()
{
return right;
}
@Override
public int count()
{
// TODO
return 0;
}
@Override
public E data()
{
return data;
}
@Override
public BSTNode<E> parent()
{
return parent;
}
@Override
public String toString()
{
return data.toString();
}
}
/**
* Constructs an empty binary search tree. This tree will maintain
* node counts but will not automatically perform rebalance operations.
*/
public BalancedBSTSet()
{
}
/**
* Constructs an empty binary search tree. If the isSelfBalancing
* flag is true, the tree will be self-balancing: if so, whenever an add(),
* remove(), or Iterator.remove() operation causes any node to become
* unbalanced, a rebalance operation is automatically performed at the
* highest unbalanced node. The default value alpha = 2/3 is used for
* the balance condition. Maintains node counts whether or not
* isSelfBalancing is true.
*
* @param isSelfBalancing true if this binary search tree is
* to be self-balancing, false otherwise
*/
public BalancedBSTSet(boolean isSelfBalancing)
{
// TODO
}
/**
* Constructs an empty binary search tree. If the isSelfBalancing
* flag is true, the tree will be self-balancing: if so, whenever an add(),
* remove(), or Iterator.remove() operation causes any node to become
* unbalanced, a rebalance operation is automatically performed at the
* highest unbalanced node. The given alpha = top/bottom is used for
* the balance condition. Maintains node counts whether or not
* isSelfBalancing is true.
*
* @param isSelfBalancing true if this binary search tree is
* to be self-balancing, false otherwise
* @param top numerator of the fraction alpha
* @param bottom denominator of the fraction alpha
* @throws IllegalArgumentException if top / bottom is less than 1/2
*/
public BalancedBSTSet(boolean isSelfBalancing, int top, int bottom)
{
//TODO
}
/**
* Returns a read-only view of the root node of this tree.
* @return root node of this tree
*/
public BSTNode<E> root()
{
return root;
}
/**
* Performs a rebalance operation on the given subtree. This operation
* does not create or destroy any nodes and does not change the size of
* this tree.
* @param bstNode root of the subtree to be rebalanced.
* @throws IllegalArgumentException if the given node is not part of this tree.
* @throws ClassCastException if the given node cannot be cast to the
* correct concrete node type for this tree.
*/
public void rebalance(BSTNode<E> bstNode)
{
// TODO
}
@Override
public boolean contains(Object obj)
{
// This cast may cause comparator to throw ClassCastException at runtime,
// which is the expected behavior
E key = (E) obj;
return findEntry(key) != null;
}
@Override
public boolean add(E key)
{
if (root == null)
{
root = new Node(key, null);
++size;
return true;
}
Node current = root;
while (true)
{
int comp = current.data.compareTo(key);
if (comp == 0)
{
// key is already in the tree
return false;
}
else if (comp > 0)
{
if (current.left != null)
{
current = current.left;
}
else
{
current.left = new Node(key, current);
++size;
return true;
}
}
else
{
if (current.right != null)
{
current = current.right;
}
else
{
current.right = new Node(key, current);
++size;
return true;
}
}
}
}
@Override
public boolean remove(Object obj)
{
// This cast may cause comparator to throw ClassCastException at runtime,
// which is the expected behavior
E key = (E) obj;
Node n = findEntry(key);
if (n == null)
{
return false;
}
unlinkNode(n);
return true;
}
/**
* Returns the node containing key, or null if the key is not
* found in the tree.
* @param key
* @return the node containing key, or null if not found
*/
protected Node findEntry(E key)
{
Node current = root;
while (current != null)
{
int comp = current.data.compareTo(key);
if (comp == 0)
{
return current;
}
else if (comp > 0)
{
current = current.left;
}
else
{
current = current.right;
}
}
return null;
}
/**
* Returns the successor of the given node.
* @param n
* @return the successor of the given node in this tree,
* or null if there is no successor
*/
protected Node successor(Node n)
{
if (n == null)
{
return null;
}
else if (n.right != null)
{
// leftmost entry in right subtree
Node current = n.right;
while (current.left != null)
{
current = current.left;
}
return current;
}
else
{
// we need to go up the tree to the closest ancestor that is
// a left child; its parent must be the successor
Node current = n.parent;
Node child = n;
while (current != null && current.right == child)
{
child = current;
current = current.parent;
}
// either current is null, or child is left child of current
return current;
}
}
/**
* Removes the given node, preserving the binary search
* tree property of the tree.
* @param n node to be removed
*/
protected void unlinkNode(Node n)
{
// first deal with the two-child case; copy
// data from successor up to n, and then delete successor
// node instead of given node n
if (n.left != null && n.right != null)
{
Node s = successor(n);
n.data = s.data;
n = s; // causes s to be deleted in code below
}
// n has at most one child
Node replacement = null;
if (n.left != null)
{
replacement = n.left;
}
else if (n.right != null)
{
replacement = n.right;
}
// link replacement into tree in place of node n
// (replacement may be null)
if (n.parent == null)
{
root = replacement;
}
else
{
if (n == n.parent.left)
{
n.parent.left = replacement;
}
else
{
n.parent.right = replacement;
}
}
if (replacement != null)
{
replacement.parent = n.parent;
}
--size;
}
@Override
public Iterator<E> iterator()
{
return new BSTIterator();
}
@Override
public int size()
{
return size;
}
/**
* Returns a representation of this tree as a multi-line string.
* The tree is drawn with the root at the left and children are
* shown top-to-bottom. Leaves are marked with a "-" and non-leaves
* are marked with a "+".
*/
@Override
public String toString()
{
StringBuilder sb = new StringBuilder();
toStringRec(root, sb, 0);
return sb.toString();
}
/**
* Preorder traversal of the tree that builds a string representation
* in the given StringBuilder.
* @param n root of subtree to be traversed
* @param sb StringBuilder in which to create a string representation
* @param depth depth of the given node in the tree
*/
private void toStringRec(Node n, StringBuilder sb, int depth)
{
for (int i = 0; i < depth; ++i)
{
sb.append(" ");
}
if (n == null)
{
sb.append("- ");
return;
}
if (n.left != null || n.right != null)
{
sb.append("+ ");
}
else
{
sb.append("- ");
}
sb.append(n.data.toString() + " (" + n.count() + ")");
sb.append(" ");
if (n.left != null || n.right != null)
{
toStringRec(n.left, sb, depth + 1);
toStringRec(n.right, sb, depth + 1);
}
}
/**
* Iterator implementation for this binary search tree. The elements
* are returned in ascending order according to their natural ordering.
*/
private class BSTIterator implements Iterator<E>
{
/**
* Node to be returned by next call to next().
*/
private Node current;
/**
* Node returned by last call to next() and available
* for removal. This field is null when no node is
* available to be removed.
*/
private Node pending;
/**
* Constructs an iterator starting at the smallest
* element in the tree.
*/
public BSTIterator()
{
// start out at smallest value
current = root;
if (current != null)
{
while (current.left != null)
{
current = current.left;
}
}
}
@Override
public boolean hasNext()
{
return current != null;
}
@Override
public E next()
{
if (!hasNext()) throw new NoSuchElementException();
pending = current;
current = successor(current);
return pending.data;
}
@Override
public void remove()
{
if (pending == null) throw new IllegalStateException();
// Remember, current points to the successor of
// pending, but if pending has two children, then
// unlinkNode(pending) will copy the successor's data
// into pending and delete the successor node.
// So in this case we want to end up with current
// pointing to the pending node.
if (pending.left != null && pending.right != null)
{
current = pending;
}
unlinkNode(pending);
pending = null;
}
}
}
Explanation / Answer
Im answering it as 2 answers since the program wont fit
It consists of 2 parts BinaryTree and BinaryTreeNode:
Filename: BinaryTree
using System;
using System.Collections.Generic;
namespace BinaryTree
{
public class BinaryTree<T> : IEnumerable<T>
where T: IComparable<T>
{
private BinaryTreeNode<T> _head;
private int _count;
#region Add
/// <summary>
/// Adds the provided value to the binary tree.
/// </summary>
/// <param name="value"></param>
public void Add(T value)
{
// Case 1: The tree is empty - allocate the head
if (_head == null)
{
_head = new BinaryTreeNode<T>(value);
}
// Case 2: The tree is not empty so find the right location to insert
else
{
AddTo(_head, value);
}
_count++;
}
// Recursive add algorithm
private void AddTo(BinaryTreeNode<T> node, T value)
{
// Case 1: Value is less than the current node value
if (value.CompareTo(node.Value) < 0)
{
// if there is no left child make this the new left
if (node.Left == null)
{
node.Left = new BinaryTreeNode<T>(value);
}
else
{
// else add it to the left node
AddTo(node.Left, value);
}
}
// Case 2: Value is equal to or greater than the current value
else
{
// If there is no right, add it to the right
if (node.Right == null)
{
node.Right = new BinaryTreeNode<T>(value);
}
else
{
// else add it to the right node
AddTo(node.Right, value);
}
}
}
#endregion
/// <summary>
/// Determines if the specified value exists in the binary tree.
/// </summary>
/// <param name="value">The value to search for.</param>
/// <returns>True if the tree contains the value, false otherwise</returns>
public bool Contains(T value)
{
// defer to the node search helper function.
BinaryTreeNode<T> parent;
return FindWithParent(value, out parent) != null;
}
/// <summary>
/// Finds and returns the first node containing the specified value. If the value
/// is not found, returns null. Also returns the parent of the found node (or null)
/// which is used in Remove.
/// </summary>
/// <param name="value">The value to search for</param>
/// <param name="parent">The parent of the found node (or null)</param>
/// <returns>The found node (or null)</returns>
private BinaryTreeNode<T> FindWithParent(T value, out BinaryTreeNode<T> parent)
{
// Now, try to find data in the tree
BinaryTreeNode<T> current = _head;
parent = null;
// while we don't have a match
while (current != null)
{
int result = current.CompareTo(value);
if (result > 0)
{
// if the value is less than current, go left.
parent = current;
current = current.Left;
}
else if (result < 0)
{
// if the value is more than current, go right.
parent = current;
current = current.Right;
}
else
{
// we have a match!
break;
}
}
return current;
}
#region Remove
/// <summary>
/// Removes the first occurance of the specified value from the tree.
/// </summary>
/// <param name="value">The value to remove</param>
/// <returns>True if the value was removed, false otherwise</returns>
public bool Remove(T value)
{
BinaryTreeNode<T> current, parent;
current = FindWithParent(value, out parent);
if (current == null)
{
return false;
}
_count--;
// Case 1: If current has no right child, then current's left replaces current
if (current.Right == null)
{
if (parent == null)
{
_head = current.Left;
}
else
{
int result = parent.CompareTo(current.Value);
if (result > 0)
{
// if parent value is greater than current value
// make the current left child a left child of parent
parent.Left = current.Left;
}
else if (result < 0)
{
// if parent value is less than current value
// make the current left child a right child of parent
parent.Right = current.Left;
}
}
}
// Case 2: If current's right child has no left child, then current's right child
// replaces current
else if (current.Right.Left == null)
{
current.Right.Left = current.Left;
if (parent == null)
{
_head = current.Right;
}
else
{
int result = parent.CompareTo(current.Value);
if (result > 0)
{
// if parent value is greater than current value
// make the current right child a left child of parent
parent.Left = current.Right;
}
else if (result < 0)
{
// if parent value is less than current value
// make the current right child a right child of parent
parent.Right = current.Right;
}
}
}
// Case 3: If current's right child has a left child, replace current with current's
// right child's left-most child
else
{
// find the right's left-most child
BinaryTreeNode<T> leftmost = current.Right.Left;
BinaryTreeNode<T> leftmostParent = current.Right;
while (leftmost.Left != null)
{
leftmostParent = leftmost;
leftmost = leftmost.Left;
}
// the parent's left subtree becomes the leftmost's right subtree
leftmostParent.Left = leftmost.Right;
// assign leftmost's left and right to current's left and right children
leftmost.Left = current.Left;
leftmost.Right = current.Right;
if (parent == null)
{
_head = leftmost;
}
else
{
int result = parent.CompareTo(current.Value);
if (result > 0)
{
// if parent value is greater than current value
// make leftmost the parent's left child
parent.Left = leftmost;
}
else if (result < 0)
{
// if parent value is less than current value
// make leftmost the parent's right child
parent.Right = leftmost;
}
}
}
return true;
}
#endregion
#region Pre-Order Traversal
/// <summary>
/// Performs the provided action on each binary tree value in pre-order traversal order.
/// </summary>
/// <param name="action">The action to perform</param>
public void PreOrderTraversal(Action<T> action)
{
PreOrderTraversal(action, _head);
}
private void PreOrderTraversal(Action<T> action, BinaryTreeNode<T> node)
{
if (node != null)
{
action(node.Value);
PreOrderTraversal(action, node.Left);
PreOrderTraversal(action, node.Right);
}
}
#endregion
#region Post-Order Traversal
/// <summary>
/// Performs the provided action on each binary tree value in post-order traversal order.
/// </summary>
/// <param name="action">The action to perform</param>
public void PostOrderTraversal(Action<T> action)
{
PostOrderTraversal(action, _head);
}
private void PostOrderTraversal(Action<T> action, BinaryTreeNode<T> node)
{
if (node != null)
{
PostOrderTraversal(action, node.Left);
PostOrderTraversal(action, node.Right);
action(node.Value);
}
}
#endregion
#region In-Order Enumeration
/// <summary>
/// Performs the provided action on each binary tree value in in-order traversal order.
/// </summary>
/// <param name="action">The action to perform</param>
public void InOrderTraversal(Action<T> action)
{
InOrderTraversal(action, _head);
}
private void InOrderTraversal(Action<T> action, BinaryTreeNode<T> node)
{
if (node != null)
{
InOrderTraversal(action, node.Left);
action(node.Value);
InOrderTraversal(action, node.Right);
}
}
/// <summary>
/// Enumerates the values contains in the binary tree in in-order traversal order.
/// </summary>
/// <returns>The enumerator</returns>
public IEnumerator<T> InOrderTraversal()
{
// This is a non-recursive algorithm using a stack to demonstrate removing
// recursion to make using the yield syntax easier.
if (_head != null)
{
// store the nodes we've skipped in this stack (avoids recursion)
Stack<BinaryTreeNode<T>> stack = new Stack<BinaryTreeNode<T>>();
BinaryTreeNode<T> current = _head;
// when removing recursion we need to keep track of whether or not
// we should be going to the left node or the right nodes next.
bool goLeftNext = true;
// start by pushing Head onto the stack
stack.Push(current);
while (stack.Count > 0)
{
// If we're heading left...
if (goLeftNext)
{
// push everything but the left-most node to the stack
// we'll yield the left-most after this block
while (current.Left != null)
{
stack.Push(current);
current = current.Left;
}
}
// in-order is left->yield->right
yield return current.Value;
// if we can go right then do so
if (current.Right != null)
{
current = current.Right;
// once we've gone right once, we need to start
// going left again.
goLeftNext = true;
}
else
{
// if we can't go right then we need to pop off the parent node
// so we can process it and then go to it's right node
current = stack.Pop();
goLeftNext = false;
}
}
}
}
/// <summary>
/// Returns an enumerator that performs an in-order traversal of the binary tree
/// </summary>
/// <returns>The in-order enumerator</returns>
public IEnumerator<T> GetEnumerator()
{
return InOrderTraversal();
}
/// <summary>
/// Returns an enumerator that performs an in-order traversal of the binary tree
/// </summary>
/// <returns>The in-order enumerator</returns>
System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
#endregion
/// <summary>
/// Removes all items from the tree
/// </summary>
public void Clear()
{
_head = null;
_count = 0;
}
/// <summary>
/// Returns the number of items currently contained in the tree
/// </summary>
public int Count
{
get
{
return _count;
}
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.