|
|||||||||
| PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
| SUMMARY: INNER | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD | ||||||||
java.lang.Object | +--jdsl.core.ref.BTNodeBinaryTree
A linked implementation of a BinaryTree. This container may become invalid
if it is used as the parameter to a link or
replaceSubtree call. An invalidated
BTNodeBinaryTree will throw a
InvalidContainerException in response to any method call.
InvalidContainerException,
link,
replaceSubtree| Constructor Summary | |
BTNodeBinaryTree()
Class Constructor. |
|
| Method Summary | |
java.util.Enumeration |
children(Position p)
The returned Enumeration is guaranteed to give the children in left-to-right order. |
BinaryTree |
cut(Position subtreeRoot)
Position subtreeRoot and all its children are removed from this tree and replaced with a new external node with a null element. |
java.util.Enumeration |
elements()
Return the elements stored in this container. |
void |
expandExternal(Position mustBeExternal)
The external position specified is transformed into an internal, and it gains two children. |
jdsl.core.ref.BTHeadNode |
head()
Returns the head node of this tree. |
boolean |
isEmpty()
Tests if this container is empty. |
boolean |
isExternal(Position p)
Checks if a given Position is an external node in this tree. |
boolean |
isInternal(Position p)
Checks if a given Position if an internal node in this tree. |
boolean |
isRoot(Position p)
|
Position |
leftChild(Position p)
Returns the left child of a Position |
void |
link(Position mustBeExternal,
BinaryTree newSubtree)
Position mustBeExternal is removed from the tree. |
Container |
newContainer()
Returns a new, empty instance of this container. |
Position |
parent(Position p)
Returns the parent of a Position in the tree. |
java.util.Enumeration |
positions()
Returns the Positions of this BinaryTree in
preorder order. |
void |
removeAboveExternal(Position mustBeExternal)
The parent of Position mustBeExternal is deleted, and the sibling subtree of mustBeExternal takes the parent's place as the left/right child of the parent's parent. |
java.lang.Object |
replace(Position p,
java.lang.Object newElement)
Replaces the element of a Position. |
BinaryTree |
replaceSubtree(Position subtreeRoot,
BinaryTree newSubtree)
Swaps a subtree of the tree on which the method is called with a "subtree" passed in. |
Position |
rightChild(Position p)
Returns the right child of a Position |
Position |
root()
Returns the root, or top node, of the tree. |
Position |
sibling(Position p)
Returns the sibling of a Position |
java.util.Enumeration |
siblings(Position p)
The returned Enumeration is guaranteed to give the siblings in left-to-right order. |
int |
size()
Returns the size of this container. |
void |
swap(Position a,
Position b)
Swaps the elements associated with the two Positions,
leaving the Positions themselves "where" they were. |
| Methods inherited from class java.lang.Object |
equals,
getClass,
hashCode,
notify,
notifyAll,
toString,
wait,
wait,
wait |
| Constructor Detail |
public BTNodeBinaryTree()
BTNodeBinaryTree with
a single leaf as the root.| Method Detail |
public jdsl.core.ref.BTHeadNode head()
public void expandExternal(Position mustBeExternal)
throws InvalidPositionException,
InvalidContainerException
mustBeExternal - A position which must be an external
position in the BinaryTreeBTNodeBinaryTree
has been invalidated.checkTree
public void removeAboveExternal(Position mustBeExternal)
throws InvalidPositionException,
BoundaryViolationException,
InvalidContainerException
mustBeExternal - A position which must be an external
position in the BinaryTreeBTNodeBinaryTree
has been invalidated.checkTree
public BinaryTree cut(Position subtreeRoot)
throws InvalidPositionException,
InvalidContainerException
subtreeRoot - The position above which to make the cutBTNodeBinaryTree
has been invalidated.checkTree
public void link(Position mustBeExternal,
BinaryTree newSubtree)
throws InvalidPositionException,
InvalidContainerException,
InvalidArgumentException
mustBeExternal - The external node to replace with the new
subtreenewSubtree - The subtree to link in. It will be invalidated by
link.BTNodeBinaryTree
has been invalidated.checkTree
public BinaryTree replaceSubtree(Position subtreeRoot,
BinaryTree newSubtree)
throws InvalidPositionException,
InvalidContainerException,
InvalidArgumentException
subtreeRoot - Any position in the BinaryTree on which
the method is callednewSubtree - The tree that will replace the tree rooted at
subtreeRootBTNodeBinaryTree
has been invalidated.checkTree
public Position leftChild(Position p)
throws InvalidPositionException,
BoundaryViolationException,
InvalidContainerException
Positionp - Any node of the treeBTNodeBinaryTree
has been invalidated.checkTree
public Position rightChild(Position p)
throws InvalidPositionException,
BoundaryViolationException,
InvalidContainerException
Positionp - Any node of the treeBTNodeBinaryTree
has been invalidated.checkTree
public Position sibling(Position p)
throws InvalidPositionException,
BoundaryViolationException,
InvalidContainerException
PositionotherChild - Any node of the treeBTNodeBinaryTree
has been invalidated.checkTree
public boolean isRoot(Position p)
throws InvalidPositionException,
InvalidContainerException
p - Any node of the treeBTNodeBinaryTree
has been invalidated.checkTree
public boolean isInternal(Position p)
throws InvalidPositionException,
InvalidContainerException
Position if an internal node in this tree.p - Any node of the treeBTNodeBinaryTree
has been invalidated.checkTree
public boolean isExternal(Position p)
throws InvalidPositionException,
InvalidContainerException
Position is an external node in this tree.p - Any node of the treeBTNodeBinaryTree
has been invalidated.checkTree
public Position root()
throws InvalidContainerException
BTNodeBinaryTree
has been invalidated.checkTree
public Position parent(Position p)
throws InvalidPositionException,
BoundaryViolationException,
InvalidContainerException
Position in the tree.p - Any node of the treeBTNodeBinaryTree
has been invalidated.checkTree
public java.util.Enumeration children(Position p)
throws InvalidPositionException,
InvalidContainerException
p - Any node of the treeBTNodeBinaryTree
has been invalidated.checkTree
public java.util.Enumeration siblings(Position p)
throws InvalidPositionException,
InvalidContainerException
p - Any node of the treeBTNodeBinaryTree
has been invalidated.checkTreepublic java.util.Enumeration positions()
Positions of this BinaryTree in
preorder order.BTNodeBinaryTree
has been invalidated.checkTree
public java.lang.Object replace(Position p,
java.lang.Object newElement)
throws InvalidPositionException
Position. Guaranteed to be a
constant-time operation.p - Position at which replacement is to occurnewElement - Element now to be stored at Position pPosition pBTNodeBinaryTree
has been invalidated.checkTree
public void swap(Position a,
Position b)
throws InvalidPositionException
Positions,
leaving the Positions themselves "where" they were. One of
the Positions can be from another container, and the swap
will be across containers.a - A Position.b - A Position.BTNodeBinaryTree
has been invalidated.checkTreepublic java.util.Enumeration elements()
container. Duplicated
elements are represented in the enumeration as many times as they are held
in the container. For some containers, the order of elements in the
enumeration is arbitrary, but for some it is defined.java.util.Enumeration of all elements in the
containerBTNodeBinaryTree
has been invalidated.checkTree,
Enumerationpublic Container newContainer()
BTNodeBinaryTree
has been invalidated.checkTreepublic int size()
BTNodeBinaryTree
has been invalidated.checkTree
public boolean isEmpty()
throws InvalidContainerException
size, runs in
constant time. Since a container always has at least one external node,
it can never be empty, so this method always returns true.false since a BinaryTree
can never be empty.BTNodeBinaryTree
has been invalidated.checkTree,
size
|
|||||||||
| PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
| SUMMARY: INNER | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD | ||||||||