jdsl.core.api
Interface BinaryTree
- All Superinterfaces:
- Container, InspectableBinaryTree, InspectableContainer, InspectablePositionalContainer, InspectableTree, PositionalContainer
- All Known Implementing Classes:
- NodeBinaryTree
- public interface BinaryTree
- extends InspectableBinaryTree, PositionalContainer
A modifiable tree in which each node has
either zero or two children.
Binary trees are conceived as starting with a single external node
(a/k/a leaf) at the root. (The node's initial element is null.)
Thus, a BinaryTree is never empty (isEmpty() is always false).
Furthermore, since size() returns the number of internal and
external leaves, size() is always at least 1.
The splicing methods, link(.) and replaceSubtree(.), leave the
spliced-in container with a single external node storing null.
The iterator() of a BinaryTree gives nodes in preorder.
Note that a (modifiable) BinaryTree cannot be used where a (modifiable)
Tree is needed (it would violate the Liskov Substitution
Principle, because a tree has the ability to insert arbitrary numbers of children).
Hence this interface does not extend the
Tree
interface. For the inspectable counterparts the
substitution principle holds, so InspectableBinaryTree is a
subinterface of InspectableTree.
- Version:
- $Id: BinaryTree.java,v 1.13 2000/01/12 03:21:26 mdh Exp $
- Author:
- Mark Handy (mdh), Mike Boilen (mgb), Andrew Schwerin (schwerin)
- See Also:
InspectableBinaryTree
Method Summary |
BinaryTree |
cut(Position node)
Position node and all its children are removed from
this binary tree and replaced with a new external node with a
null element. |
void |
expandExternal(Position node)
The external position specified is transformed into an internal,
and it gains two external children. |
void |
graftOnLeft(Position subtreeRoot,
java.lang.Object eltOfParent,
BinaryTree newSubtree)
Position subtreeRoot of this binary tree is demoted
one level, with all the positions and elements unchanged, and
becomes the right child of a new node storing the given element. |
void |
graftOnRight(Position subtreeRoot,
java.lang.Object eltOfParent,
BinaryTree newSubtree)
Position subtreeRoot of this binary tree is demoted
one level, with all the positions and elements unchanged, and
becomes the left child of a new node, storing the given element. |
java.lang.Object |
link(Position node,
BinaryTree newSubtree)
Links binary tree newSubtree at external node
node by replacing node with the root of
newSubtree . |
void |
removeAboveExternal(Position node)
The parent of node is deleted, and the sibling of
node , with all its children, is installed in its
place; node is also deleted. |
BinaryTree |
replaceSubtree(Position subtreeRoot,
BinaryTree newSubtree)
Swaps a subtree of this binary tree with a binary tree passed in. |
Methods inherited from interface jdsl.core.api.InspectableTree |
childAtRank, children, firstChild, isExternal, isInternal, isRoot, lastChild, numChildren, parent, rankOfChild, root, siblingAfter, siblingBefore, siblings |
expandExternal
public void expandExternal(Position node)
throws InvalidAccessorException
- The external position specified is transformed into an internal,
and it gains two external children. The position reference
itself doesn't change. The elements of its two new, external
children are both null.
- Parameters:
node
- any external position in this binary tree- Throws:
InvalidAccessorException
- if node
is not
external, is null, or does not belong to this binary tree.
removeAboveExternal
public void removeAboveExternal(Position node)
throws BoundaryViolationException,
InvalidAccessorException
- The parent of
node
is deleted, and the sibling of
node
, with all its children, is installed in its
place; node
is also deleted.
- Parameters:
node
- any external position in this binary tree- Throws:
BoundaryViolationException
- if node
is
an external position, as required, but also the root of this binary
tree.InvalidAccessorException
- if node
is not
external, is null, or does not belong to this binary tree.
cut
public BinaryTree cut(Position node)
throws InvalidAccessorException
- Position node and all its children are removed from
this binary tree and replaced with a new external node with a
null element. They are packaged in a new binary tree and
returned; all positions elements are still valid, although some
of them have a different container after the operation.
node can be the root, or an external node.
- Parameters:
node
- the position above which to make the cut- Returns:
- the subtree removed, packaged as a new BinaryTree, with
node
as its root - Throws:
InvalidAccessorException
- if node
is null
or does not belong to this binary tree.
link
public java.lang.Object link(Position node,
BinaryTree newSubtree)
throws InvalidAccessorException,
InvalidContainerException
- Links binary tree
newSubtree
at external node
node
by replacing node
with the root of
newSubtree
. As a result of this method, the
positions of newSubtree
become positions of this
binary tree and newSubtree
becomes a binary tree
with a single node storing null.
- Parameters:
node
- the external node to replace with the new subtreenewSubtree
- the subtree to link in- Returns:
- the element of the external position that was removed
- Throws:
InvalidAccessorException
- if node
is not
external, is null, or does not belong to this binary tree.InvalidContainerException
- if newSubtree
is null, incompatible with, or equal to this binary tree.
replaceSubtree
public BinaryTree replaceSubtree(Position subtreeRoot,
BinaryTree newSubtree)
throws InvalidAccessorException,
InvalidContainerException
- Swaps a subtree of this binary tree with a binary tree passed in.
In the extremes, the subtree of this binary tree might be the
entire tree, or might be just a leaf.
subtreeRoot
specifies a subtree of this binary tree. That subtree is removed
from this binary tree, and newSubtree
is linked in in
its place. A new binary tree, whose root is the position
subtreeRoot
, is returned to the user (this binary
tree has all the positions of the removed subtree).
Note that this binary tree is one of three binary trees involved
in the method. The other two are the newSubtree passed in, which
becomes an empty tree when the method finishes; and the tree
returned, which is a brand new BinaryTree holding the
subtreeRoot, and all its children, which were removed from this
binary tree.
Note that link(.)
and cut(.)
can both
be implemented in terms of this method.
newSubtree
must be of the same class as this binary
tree, or perhaps otherwise node-compatible with this binary tree.
- Parameters:
subtreeRoot
- any position in this binary treenewSubtree
- the binary tree that will replace the binary
tree rooted at subtreeRoot
- Returns:
- a new binary tree, with
subtreeRoot
as its
root - Throws:
InvalidAccessorException
- if subtreeRoot
is null or does not belong to this binary tree.InvalidContainerException
- if newSubtree
is null, incompatible with, or equal to this binary tree.
graftOnLeft
public void graftOnLeft(Position subtreeRoot,
java.lang.Object eltOfParent,
BinaryTree newSubtree)
throws InvalidAccessorException,
InvalidContainerException
- Position
subtreeRoot
of this binary tree is demoted
one level, with all the positions and elements unchanged, and
becomes the right child of a new node storing the given element.
The root of newSubtree
, with all its children, is
linked in as the left child of the new node, with all the
positions and elements unchanged. newSubtree becomes empty.
- Parameters:
newSubtree
- the binary tree whose root will be linked in as
the left child of the new nodeeltOfParent
- the object to be stored in the new nodesubtreeRoot
- any position in this binary tree- Throws:
InvalidAccessorException
- if subtreeRoot
is null or does not belong to this binary tree.InvalidContainerException
- if newSubtree
is null, incompatible with, or equal to this binary tree.
graftOnRight
public void graftOnRight(Position subtreeRoot,
java.lang.Object eltOfParent,
BinaryTree newSubtree)
throws InvalidAccessorException,
InvalidContainerException
- Position
subtreeRoot
of this binary tree is demoted
one level, with all the positions and elements unchanged, and
becomes the left child of a new node, storing the given element.
The root of newSubtree
, with all its children, is
linked in as the right child of the new node, with all the
positions and elements unchanged. newSubtree becomes empty.
- Parameters:
subtreeRoot
- any position in this binary treeeltOfParent
- the object to be stored in the new nodenewSubtree
- the binary tree whose root will be linked in as
the right child of the new node- Throws:
InvalidAccessorException
- if subtreeRoot
is null or does not belong to this binary tree.InvalidContainerException
- if newSubtree
is null, incompatible with, or equal to this binary tree.