All Packages  Class Hierarchy  This Package  Previous  Next  Index

Class structure.BinaryTreeNode 

java.lang.Object
    |
    +----structure.BinaryTreeNode
public class BinaryTreeNode
extends Object
This class implements a single node of a binary tree. It is a recursive structure. Relationships between nodes are doubly linked, with parent and child references. Many characteristics of trees may be detected with static methods.

See Also:
BinaryTree, BinarySearchTree

Constructor Index

o BinaryTreeNode(Object)
Constructs a tree node with no children.
o BinaryTreeNode(Object, BinaryTreeNode, BinaryTreeNode)
Constructs a tree node with no children.

Method Index

o depth(BinaryTreeNode)
Compute the depth of a node.
o elements()
Generate an inorder traversal of subtree.
o height(BinaryTreeNode)
Returns height of node in tree.
o inorderElements()
Return an iterator to traverse the elements of subtree in-order.
o isBalanced(BinaryTreeNode)
Return true iff the tree is height balanced.
o isComplete(BinaryTreeNode)
Return whether tree is complete.
o isFull(BinaryTreeNode)
Returns true if tree is full.
o isLeftChild()
Determine if this node is a left child.
o isRightChild()
Determine if this node is a right child.
o left()
Get left subtree of current node.
o levelorderElements()
Method to return a level-order iterator of subtree.
o parent()
Get reference to parent of this node.
o postorderElements()
Return an iterator to traverse the elements of subtree in post-order.
o preorderElements()
Return an iterator to traverse nodes of subtree in-order.
o right()
Get right subtree of current node.
o root(BinaryTreeNode)
Returns reference to root of tree containing n.
o setLeft(BinaryTreeNode)
Update the left subtree of this node.
o setRight(BinaryTreeNode)
Update the right subtree of this node.
o setValue(Object)
Set's value associated with this node.
o size(BinaryTreeNode)
Returns the number of descendants of node n.
o toString()
Returns a representation the subtree rooted at this node.
o value()
Returns value associated with this node.

Constructors

o BinaryTreeNode 
public BinaryTreeNode(Object value)
Constructs a tree node with no children. Value of the node is provided by the user.

Postcondition:
Returns a tree referencing value with two null subtrees

Parameters:
value - A (possibly null) value to be referenced by node.
o BinaryTreeNode 
public BinaryTreeNode(Object value,
                      BinaryTreeNode left,
                      BinaryTreeNode right)
Constructs a tree node with no children. Value of the node and subtrees are provided by the user.

Postcondition:
Returns a tree referencing value & subtrees.

Parameters:
value - A (possibly null) value to be referenced by node.
left - The subtree to be left subtree of node.
right - The subtree to be right subtree of node.

Methods

o left 
public BinaryTreeNode left()
Get left subtree of current node.

Postcondition:
Returns reference to left subtree, or null

Returns:
The left subtree of this node.
o right 
public BinaryTreeNode right()
Get right subtree of current node.

Postcondition:
Returns reference to right subtree, or null

Returns:
The right subtree of this node.
o parent 
public BinaryTreeNode parent()
Get reference to parent of this node.

Postcondition:
Returns reference to parent node, or null

Returns:
Reference to parent of this node.
o setLeft 
public void setLeft(BinaryTreeNode newLeft)
Update the left subtree of this node. Parent of the left subtree is updated consistently. Existing subtree is detached.

Postcondition:
Sets left subtree to newLeft re-parents newLeft if not null

Parameters:
newLeft - The root of the new left subtree.
o setRight 
public void setRight(BinaryTreeNode newRight)
Update the right subtree of this node. Parent of the right subtree is updated consistently. Existing subtree is detached.

Postcondition:
Sets left subtree to newRight re-parents newRight if not null

Parameters:
newRight - A reference to the new right subtree of this node.
o size 
public static int size(BinaryTreeNode n)
Returns the number of descendants of node n.

Postcondition:
Returns the size of the subtree rooted at n

Parameters:
n - Root of subtree.
Returns:
Size of subtree.
o root 
public static BinaryTreeNode root(BinaryTreeNode n)
Returns reference to root of tree containing n.

Postcondition:
Returns the root of the tree node n

Parameters:
n - Node of tree.
Returns:
Root of tree.
o height 
public static int height(BinaryTreeNode n)
Returns height of node in tree. Height is maximum path length to descendant.

Postcondition:
Returns the height of a node n in its tree

Parameters:
n - Node in tree.
Returns:
The height of the node in the tree.
o depth 
public static int depth(BinaryTreeNode n)
Compute the depth of a node. The depth is the path length from node to root.

Postcondition:
Returns the depth of a node in the tree

Parameters:
n - A node in a tree.
Returns:
The path length to root of tree.
o isFull 
public static boolean isFull(BinaryTreeNode n)
Returns true if tree is full. A tree is full if adding a node to tree would necessarily increase its height.

Postcondition:
Returns true iff the tree rooted at n is full.

Parameters:
n - Root of tree to be considered.
Returns:
True iff tree is full.
o isComplete 
public static boolean isComplete(BinaryTreeNode n)
Return whether tree is complete. A complete tree has minimal height and any holes in tree would appear in last level to right.

Postcondition:
Returns true iff the tree rooted at n is complete

Parameters:
n - Root of subtree considered.
Returns:
True iff the subtree is complete.
o isBalanced 
public static boolean isBalanced(BinaryTreeNode n)
Return true iff the tree is height balanced. A tree is height balanced iff at every node the difference in heights of subtrees is no greater than one.

Postcondition:
Returns true iff the tree rooted at n is balanced

Parameters:
n - Root of subtree to be considered.
Returns:
True if tree is height balanced.
o elements 
public Iterator elements()
Generate an inorder traversal of subtree.

Postcondition:
Returns an inorder traversal of the elements.

Returns:
Inorder iterator on subtree rooted at this.
o preorderElements 
public Iterator preorderElements()
Return an iterator to traverse nodes of subtree in-order.

Postcondition:
The elements of the binary tree rooted at node n are traversed in preorder

Returns:
Iterator to traverse subtree.
o inorderElements 
public Iterator inorderElements()
Return an iterator to traverse the elements of subtree in-order.

Postcondition:
The elements of the binary tree rooted at node n are traversed in inorder

Returns:
An in-order iterator over descendants of node.
o postorderElements 
public Iterator postorderElements()
Return an iterator to traverse the elements of subtree in post-order.

Precondition:
None
Postcondition:
The elements of the binary tree rooted at node n are traversed in postorder

Returns:
An iterator that traverses descendants of node in postorder.
o levelorderElements 
public Iterator levelorderElements()
Method to return a level-order iterator of subtree.

Precondition:
None
Postcondition:
The elements of the binary tree rooted at node n are traversed in levelorder

Returns:
An iterator to traverse subtree in level-order
o isLeftChild 
public boolean isLeftChild()
Determine if this node is a left child.

Postcondition:
Returns true if this is a left child of parent.

Returns:
True iff this node is a left child of parent
o isRightChild 
public boolean isRightChild()
Determine if this node is a right child.

Postcondition:
Returns true if this is a right child of parent.

Returns:
True iff this node is a right child of parent
o value 
public Object value()
Returns value associated with this node.

Postcondition:
Returns value associated with this node.

Returns:
The node's value
o setValue 
public void setValue(Object value)
Set's value associated with this node.

Postcondition:
Sets the value associated with this node

Parameters:
value - The new value of this node.
o toString 
public String toString()
Returns a representation the subtree rooted at this node.

Postcondition:
Returns string representation

Returns:
String representing this subtree.
Overrides:
toString in class Object
All Packages  Class Hierarchy  This Package  Previous  Next  Index