Class BinaryTree<V>

java.lang.Object
  extended by BinaryTree<V>
Type Parameters:
V - The type of values contained in this BinaryTree.

public class BinaryTree<V>
extends java.lang.Object

A BinaryTree consists of "nodes"--each "node" is itself a BinaryTree. Each node has a parent (unless it is the root), may have a left child, and may have a right child. This class implements loop-free binary trees, allowing shared subtrees.

Version:
Jan 25, 2004
Author:
David Matuszek

Field Summary
 V value
          The value (data) in this node of the binary tree; may be of any object type.
 
Constructor Summary
BinaryTree(V value)
          Constructor for a BinaryTree leaf node (that is, with no children).
BinaryTree(V value, BinaryTree<V> leftChild, BinaryTree<V> rightChild)
          Constructor for BinaryTree.
 
Method Summary
protected static boolean contains(BinaryTree tree, BinaryTree targetNode)
          Tests whether the tree argument contains within itself the targetNode argument.
 boolean containsEqualValue(V value)
          Returns true if and only if some node in this binary tree contains a value that is equal to the parameter.
 boolean containsSameValue(V value)
          Returns true if and only if some node in this binary tree contains the same object (not just an equal object) as the one given for the value parameter.
 BinaryTree<V> copy()
          Returns a new BinaryTree equal to (but not the same as) this binary tree.
 int depth()
          Returns the depth of this binary tree.
 boolean equals(java.lang.Object o)
          Tests whether this BinaryTree is equal to the given object.
 java.util.List<V> fringe()
          Returns a List of the values (of type V) in the leaves of this binary tree, in left-to-right order.
 BinaryTree<V> getLeftChild()
          Getter method for left child of this BinaryTree node.
 BinaryTree<V> getRightChild()
          Getter method for right child of this BinaryTree node.
 V getValue()
          Getter method for the value in this BinaryTree node.
 int hashCode()
          Computes a hash code for the complete binary tree rooted at this BinaryTree node.
 boolean isLeaf()
          Tests whether this node is a leaf node.
 java.util.Set<BinaryTree<V>> leaves()
          Returns a Set of all the leaves of this binary tree.
 BinaryTree<V> leftmostDescendant()
          Returns the leftmost descendant of this binary tree.
 int numberOfNodes()
          Returns the total number of nodes in this binary tree (include the root in the count).
 void print()
          Prints the binary tree rooted at this BinaryTree node.
 BinaryTree<V> reverse()
          Returns a new binary tree which is the mirror image of the binary tree whose root is at this binary tree.
 void reverseInPlace()
          Rearranges the binary tree rooted at this binary tree to be the mirror image of its original structure.
 BinaryTree<V> rightmostDescendant()
          Returns the rightmost descendant of this binary tree.
 void setLeftChild(BinaryTree<V> subtree)
          Sets the left child of this BinaryTree node to be the given subtree.
 void setRightChild(BinaryTree<V> subtree)
          Sets the right child of this BinaryTree node to be the given subtree.
 void setValue(V value)
          Sets the value in this BinaryTree node.
 java.lang.String toString()
          Returns a String representation of this BinaryTree.
 java.util.Set<V> valuesOf()
          Returns a Set of the values (of type V) in this binary tree.
 
Methods inherited from class java.lang.Object
clone, finalize, getClass, notify, notifyAll, wait, wait, wait
 

Field Detail

value

public V value
The value (data) in this node of the binary tree; may be of any object type.

Constructor Detail

BinaryTree

public BinaryTree(V value,
                  BinaryTree<V> leftChild,
                  BinaryTree<V> rightChild)
Constructor for BinaryTree.

Parameters:
value - The value to be placed in the root.
leftChild - The left child of the root (may be null).
rightChild - The right child of the root (may be null).

BinaryTree

public BinaryTree(V value)
Constructor for a BinaryTree leaf node (that is, with no children).

Parameters:
value - The value to be placed in the root.
Method Detail

getValue

public V getValue()
Getter method for the value in this BinaryTree node.

Returns:
The value in this node.

getLeftChild

public BinaryTree<V> getLeftChild()
Getter method for left child of this BinaryTree node.

Returns:
The left child (null if no left child).

getRightChild

public BinaryTree<V> getRightChild()
Getter method for right child of this BinaryTree node.

Returns:
The right child (null if no right child).

setLeftChild

public void setLeftChild(BinaryTree<V> subtree)
                  throws java.lang.IllegalArgumentException
Sets the left child of this BinaryTree node to be the given subtree. If the node previously had a left child, it is discarded. Throws an IllegalArgumentException if the operation would cause a loop in the binary tree.

Parameters:
subtree - The node to be added as the new left child.
Throws:
java.lang.IllegalArgumentException - If the operation would cause a loop in the binary tree.

setRightChild

public void setRightChild(BinaryTree<V> subtree)
                   throws java.lang.IllegalArgumentException
Sets the right child of this BinaryTree node to be the given subtree. If the node previously had a right child, it is discarded. Throws an IllegalArgumentException if the operation would cause a loop in the binary tree.

Parameters:
subtree - The node to be added as the new right child.
Throws:
java.lang.IllegalArgumentException - If the operation would cause a loop in the binary tree.

setValue

public void setValue(V value)
Sets the value in this BinaryTree node.

Parameters:
value - The new value.

isLeaf

public boolean isLeaf()
Tests whether this node is a leaf node.

Returns:
true if this BinaryTree node has no children.

equals

public boolean equals(java.lang.Object o)
Tests whether this BinaryTree is equal to the given object. To be considered equal, the object must be a BinaryTree, and the two binary trees must have equal values in their roots, equal left subtrees, and equal right subtrees.

Overrides:
equals in class java.lang.Object
Returns:
true if the binary trees are equal.
See Also:
Object.equals(java.lang.Object)

contains

protected static boolean contains(BinaryTree tree,
                                  BinaryTree targetNode)
Tests whether the tree argument contains within itself the targetNode argument.

Parameters:
tree - The root of the binary tree to search.
targetNode - The node to be searched for.
Returns:
true if the targetNode argument can be found within the binary tree rooted at tree.

toString

public java.lang.String toString()
Returns a String representation of this BinaryTree.

Overrides:
toString in class java.lang.Object
Returns:
A String representation of this BinaryTree.
See Also:
Object.toString()

hashCode

public int hashCode()
Computes a hash code for the complete binary tree rooted at this BinaryTree node.

Overrides:
hashCode in class java.lang.Object
Returns:
A hash code for the binary tree with this root.
See Also:
Object.hashCode()

print

public void print()
Prints the binary tree rooted at this BinaryTree node.


leftmostDescendant

public BinaryTree<V> leftmostDescendant()
Returns the leftmost descendant of this binary tree. That is, return the leaf that is the left child of the left child of ... the left child of this binary tree. If this binary tree has no left child, return this binary tree.

Returns:
The leftmost descendant of this BinaryTree.

rightmostDescendant

public BinaryTree<V> rightmostDescendant()
Returns the rightmost descendant of this binary tree. That is, return the leaf that is the right child of the right child of ... the right child of this binary tree. If this binary tree has no right child, return this binary tree.

Returns:
The rightmost descendant of this BinaryTree.

numberOfNodes

public int numberOfNodes()
Returns the total number of nodes in this binary tree (include the root in the count).

Returns:
The number of nodes in this BinaryTree.

depth

public int depth()
Returns the depth of this binary tree. The depth of a binary tree is the length of the longest path from this node to a leaf. The depth of a binary tree with no descendants (that is, just a leaf) is zero.

Returns:
The depth of this BinaryTree.

containsEqualValue

public boolean containsEqualValue(V value)
Returns true if and only if some node in this binary tree contains a value that is equal to the parameter.

Parameters:
value - The value to be searched for.
Returns:
true if this BinaryTree contains an equal value.

containsSameValue

public boolean containsSameValue(V value)
Returns true if and only if some node in this binary tree contains the same object (not just an equal object) as the one given for the value parameter.

Parameters:
value - The value to be searched for.
Returns:
true if this BinaryTree contains the identical value.

leaves

public java.util.Set<BinaryTree<V>> leaves()
Returns a Set of all the leaves of this binary tree.

Returns:
The leaves of this BinaryTree.

valuesOf

public java.util.Set<V> valuesOf()
Returns a Set of the values (of type V) in this binary tree.

Returns:
The values in this BinaryTree.

fringe

public java.util.List<V> fringe()
Returns a List of the values (of type V) in the leaves of this binary tree, in left-to-right order.

Returns:
The values in the leaves of this BinaryTree.

copy

public BinaryTree<V> copy()
Returns a new BinaryTree equal to (but not the same as) this binary tree. Every node in this new BinaryTree will be created by the copy method; values will be identical (==) to values in the given binary tree.

Returns:
An exact copy of this BinaryTree; the values in the new BinaryTree are == to the values in this BinaryTree.

reverse

public BinaryTree<V> reverse()
Returns a new binary tree which is the mirror image of the binary tree whose root is at this binary tree. That is, for every node in the new binary tree, its children are in reverse order (left child becomes right child, right child becomes left child).

Returns:
A mirror image copy of this BinaryTree; values in the new BinaryTree are == to the values in this BinaryTree.

reverseInPlace

public void reverseInPlace()
Rearranges the binary tree rooted at this binary tree to be the mirror image of its original structure. No new BinaryTree nodes are created in this process.