scranton.tree
Class RecursiveBinaryTreeViaLinear1

java.lang.Object
  scranton.Linear1
      scranton.tree.RecursiveBinaryTreeViaLinear1

All Implemented Interfaces:

RecursiveBinaryTree

Direct Known Subclasses:

BinarySearchTree

public class RecursiveBinaryTreeViaLinear1

extends Linear1

implements RecursiveBinaryTree

This interface describes one interpretation of an object oriented versions of the recursive binary tree found in McCarthey's LISP. Specification: a binary tree, T, is (1) empty, T = (), or (2) T = (r,(L,R)) where r is the root of the tree and L and R are (possibly empty) binary trees.

Field Summary

Fields inherited from class scranton.Linear1

data, link

Constructor Summary

RecursiveBinaryTreeViaLinear1()
Construct an empty tree, T=();

RecursiveBinaryTreeViaLinear1(java.lang.Object obj, RecursiveBinaryTreeViaLinear1 lst, RecursiveBinaryTreeViaLinear1 rst)
Construct a tree, T=(obj, ((),())); NOTE: May be used by extensions of this class to construct

Method Summary

Linear1	factory() Returns an empty tree
java.lang.Object	getRoot() Returns a reference to the root of the current tree.
void	graft(RecursiveBinaryTree T) Replace the current tree by T.
boolean	isEmpty() Returns true if and only if the current tree is empty.
RecursiveBinaryTree	leftSubtree() Returns a reference to the left subtree of the current tree.
RecursiveBinaryTree	prune() Return reference to the current tree, then make current tree empty.
RecursiveBinaryTree	rightSubtree() Returns a reference to the right subtree of the current tree.
void	setRoot(java.lang.Object obj) Modify the root of the current tree.
java.lang.String	sideways(java.lang.String Str, char Ch, int Level) Constructs a stylized string representation of a binary tree structure that appears sideways when displayed.
java.lang.String	toString() Returns a string representation of the tree.

Methods inherited from class scranton.Linear1

getData, getLink, setData, setLink

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

RecursiveBinaryTreeViaLinear1

public RecursiveBinaryTreeViaLinear1()

Construct an empty tree, T=();

RecursiveBinaryTreeViaLinear1

public RecursiveBinaryTreeViaLinear1(java.lang.Object obj,
                                     RecursiveBinaryTreeViaLinear1 lst,
                                     RecursiveBinaryTreeViaLinear1 rst)

Construct a tree, T=(obj, ((),())); NOTE: May be used by extensions of this class to construct

Method Detail

isEmpty

public boolean isEmpty()

Description copied from interface: RecursiveBinaryTree

Returns true if and only if the current tree is empty.

Specified by:

isEmpty in interface RecursiveBinaryTree

Returns:

true iff this==()

See Also:

isEmpty()

rightSubtree

public RecursiveBinaryTree rightSubtree()

Description copied from interface: RecursiveBinaryTree

Returns a reference to the right subtree of the current tree. Pre: T/=(), T=(r,(L,R))

Specified by:

rightSubtree in interface RecursiveBinaryTree

Returns:

Reference to the rightSubtree of the current tree

See Also:

rightSubtree()

leftSubtree

public RecursiveBinaryTree leftSubtree()

Description copied from interface: RecursiveBinaryTree

Returns a reference to the left subtree of the current tree. Pre: T/=(), T=(r,(L,R))

Specified by:

leftSubtree in interface RecursiveBinaryTree

Returns:

Reference to the leftSubtree of the current tree

See Also:

leftSubtree()

getRoot

public java.lang.Object getRoot()

Description copied from interface: RecursiveBinaryTree

Returns a reference to the root of the current tree. Pre: T/=(), T=(r,(L,R)) h

Specified by:

getRoot in interface RecursiveBinaryTree

Returns:

Reference to the root of the tree

See Also:

getRoot()

setRoot

public void setRoot(java.lang.Object obj)

Description copied from interface: RecursiveBinaryTree

Modify the root of the current tree. Pre: T/=(), T=(r,(L,R)) Post: T'=(obj,(L,R))

Specified by:

setRoot in interface RecursiveBinaryTree

Parameters:

obj - The new root of the current tree

See Also:

setRoot(java.lang.Object)

graft

public void graft(RecursiveBinaryTree T)

Description copied from interface: RecursiveBinaryTree

Replace the current tree by T. Pre: this = () Post: this'=T, T'=()

Specified by:

graft in interface RecursiveBinaryTree

Parameters:

T - becomes the current tree

See Also:

graft(scranton.tree.RecursiveBinaryTree)

prune

public RecursiveBinaryTree prune()

Description copied from interface: RecursiveBinaryTree

Return reference to the current tree, then make current tree empty. Post: T'=()

Specified by:

prune in interface RecursiveBinaryTree

Returns:

The current tree

See Also:

prune()

factory

public Linear1 factory()

Returns an empty tree

Overrides:

factory in class Linear1

Returns:

Returns an empty Linear1 object with the object signature for a RecursiveBinaryTreeViaLinear1

toString

public java.lang.String toString()

Description copied from interface: RecursiveBinaryTree

Returns a string representation of the tree. The string representation is "[]" for an empty tree, otherwise "[leftsubtree \t root \t rightsubtree]"

Specified by:

toString in interface RecursiveBinaryTree

Overrides:

toString in class Linear1

Returns:

String Returns a tab delimited string of the objects in the recursive Linear1 structure.

See Also:

Object.toString()

sideways

public java.lang.String sideways(java.lang.String Str,
                                 char Ch,
                                 int Level)

Constructs a stylized string representation of a binary tree structure that appears sideways when displayed.