Opus5
Class BinaryTree

java.lang.Object
  |
  +--Opus5.AbstractObject
        |
        +--Opus5.AbstractContainer
              |
              +--Opus5.AbstractTree
                    |
                    +--Opus5.BinaryTree

All Implemented Interfaces:

Comparable, Container, Tree

Direct Known Subclasses:

BinarySearchTree, ExpressionTree, LeftistHeap

public class BinaryTree

extends AbstractTree

A node in a binary tree.

Version:

$Id: BinaryTree.java,v 3.2 1998/07/28 13:18:42 brpreiss Exp $

Author:

Bruno R. Preiss, P.Eng.

Inner classes inherited from class Opus5.AbstractTree

AbstractTree.TreeEnumeration

Field Summary

protected java.lang.Object	key The key in this node.
protected BinaryTree	left The the left subtree of this node.
protected BinaryTree	right The the right subtree of this node.

Fields inherited from class Opus5.AbstractContainer

count

Fields inherited from interface Opus5.Tree

copyright

Constructor Summary

BinaryTree()
Constructs an empty BinaryTree.

BinaryTree(java.lang.Object key)
Constructs a BinaryTree with the specified key.

BinaryTree(java.lang.Object key, BinaryTree left, BinaryTree right)
Constructs a BinaryTree with the specified key, and the specified left and right subtree.

Method Summary

void	attachKey(java.lang.Object object) Attaches the specified object as the key of this node.
void	attachLeft(BinaryTree t) Attaches the specified binary tree as the left subtree of this node.
void	attachRight(BinaryTree t) Attaches the specified binary tree as the right subtree of this node.
protected int	compareTo(Comparable object) Compares this binary tree with the specified comparable object.
void	depthFirstTraversal(PrePostVisitor visitor) Causes a visitor to visit the nodes of this tree in depth-first traversal order starting from this node.
java.lang.Object	detachKey() Detaches the key from this node; making it the empty node.
BinaryTree	detachLeft() Detaches and returns the left subtree of this node.
BinaryTree	detachRight() Detaches and returns the right subtree of this node.
int	getDegree() Returns the degree of this node.
java.lang.Object	getKey() Returns the key in this node.
BinaryTree	getLeft() Returns the left subtree of this node.
BinaryTree	getRight() Returns the right subtree of this node.
Tree	getSubtree(int i) Returns the specified subtree of this node.
boolean	isEmpty() Tests whether this node is empty.
boolean	isLeaf() Tests whether this node is a leaf node.
void	purge() Purges this binary tree node, making it empty.

Methods inherited from class Opus5.AbstractTree

accept, breadthFirstTraversal, getCount, getEnumeration, getHeight

Methods inherited from class Opus5.AbstractContainer

hashCode, isFull, toString

Methods inherited from class Opus5.AbstractObject

compare, equals, isEQ, isGE, isGT, isLE, isLT, isNE

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface Opus5.Container

isFull

Methods inherited from interface Opus5.Comparable

compare, isEQ, isGE, isGT, isLE, isLT, isNE

Field Detail

key

protected java.lang.Object key

The key in this node.

left

protected BinaryTree left

The the left subtree of this node.

right

protected BinaryTree right

The the right subtree of this node.

Constructor Detail

BinaryTree

public BinaryTree(java.lang.Object key,
                  BinaryTree left,
                  BinaryTree right)

Constructs a BinaryTree with the specified key, and the specified left and right subtree.

Parameters:

key - The key in this node.

left - The left subtree of this node.

right - The left subtree of this node.

BinaryTree

public BinaryTree()

Constructs an empty BinaryTree.

BinaryTree

public BinaryTree(java.lang.Object key)

Constructs a BinaryTree with the specified key. The left and right subtrees default to empty trees.

Method Detail

purge

public void purge()

Purges this binary tree node, making it empty.

isLeaf

public boolean isLeaf()

Tests whether this node is a leaf node.

Returns:

True if this node is a non-empty node with two empty subtrees; false otherwise.

getDegree

public int getDegree()

Returns the degree of this node.

Returns:

2 if this node is non-empty; 0 otherwise.

isEmpty

public boolean isEmpty()

Tests whether this node is empty.

Overrides:

isEmpty in class AbstractContainer

Returns:

True if this node is empty; false otherwise.

getKey

public java.lang.Object getKey()

Returns the key in this node.

Returns:

The key in this node.

Throws:

InvalidOperationException - If this node is empty.

getSubtree

public Tree getSubtree(int i)

Returns the specified subtree of this node.

Parameters:

i - The number of the subtree to return.

Returns:

The specified subtree of this node.

attachKey

public void attachKey(java.lang.Object object)

Attaches the specified object as the key of this node. The node must be initially empty.

Parameters:

object - The key to attach.

Throws:

InvalidOperationException - If this node is not empty.

detachKey

public java.lang.Object detachKey()

Detaches the key from this node; making it the empty node.

Throws:

InvalidOperationException - If this is not a leaf node.

getLeft

public BinaryTree getLeft()

Returns the left subtree of this node.

Returns:

The left subtree of this node.

Throws:

InvalidOperationException - If this node is empty.

attachLeft

public void attachLeft(BinaryTree t)

Attaches the specified binary tree as the left subtree of this node.

Parameters:

t - The new left subtree of this node.

Throws:

InvalidOperationException - If this node is empty or if this node is node empty and the left subtree is also not empty.

detachLeft

public BinaryTree detachLeft()

Detaches and returns the left subtree of this node.

Returns:

The left subtree of this node.

Throws:

InvalidOperationException - If this node is empty.

getRight

public BinaryTree getRight()

Returns the right subtree of this node.

Returns:

The right subtree of this node.

Throws:

InvalidOperationException - If this node is empty.

attachRight

public void attachRight(BinaryTree t)

Attaches the specified binary tree as the right subtree of this node.

Parameters:

t - The new right subtree of this node.

Throws:

InvalidOperationException - If this node is empty or if this node is node empty and the right subtree is also not empty.

detachRight

public BinaryTree detachRight()

Detaches and returns the right subtree of this node.

Returns:

The right subtree of this node.

Throws:

InvalidOperationException - If this node is empty.

depthFirstTraversal

public void depthFirstTraversal(PrePostVisitor visitor)

Causes a visitor to visit the nodes of this tree in depth-first traversal order starting from this node. This method invokes the preVisit, inVisit and postVisit methods of the visitor for each node in this tree.

Overrides:

depthFirstTraversal in class AbstractTree

Parameters:

visitor - The visitor to accept.

compareTo

protected int compareTo(Comparable object)

Compares this binary tree with the specified comparable object. The specified comparable object is assumed to be a BinaryTree

Overrides:

compareTo in class AbstractObject

Parameters:

object - The comparable object with which to compare this binar tree.

Returns:

A number less than zero if this binary tree is less than the specified binary tree; greater than zero if this binary tree is greater than the specified binary tree; zero if the two trees are identical.