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

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

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

depth(BinaryTreeNode)
 Compute the depth of a node.

elements()
 Generate an inorder traversal of subtree.

height(BinaryTreeNode)
 Returns height of node in tree.

inorderElements()
 Return an iterator to traverse the elements of subtree inorder.

isBalanced(BinaryTreeNode)
 Return true iff the tree is height balanced.

isComplete(BinaryTreeNode)
 Return whether tree is complete.

isFull(BinaryTreeNode)
 Returns true if tree is full.

isLeftChild()
 Determine if this node is a left child.

isRightChild()
 Determine if this node is a right child.

left()
 Get left subtree of current node.

levelorderElements()
 Method to return a levelorder iterator of subtree.

parent()
 Get reference to parent of this node.

postorderElements()
 Return an iterator to traverse the elements of subtree in postorder.

preorderElements()
 Return an iterator to traverse nodes of subtree inorder.

right()
 Get right subtree of current node.

root(BinaryTreeNode)
 Returns reference to root of tree containing n.

setLeft(BinaryTreeNode)
 Update the left subtree of this node.

setRight(BinaryTreeNode)
 Update the right subtree of this node.

setValue(Object)
 Set's value associated with this node.

size(BinaryTreeNode)
 Returns the number of descendants of node n.

toString()
 Returns a representation the subtree rooted at this node.

value()
 Returns value associated with this node.
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.
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.
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.
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.
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.
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
reparents newLeft if not null
 Parameters:
 newLeft  The root of the new left subtree.
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
reparents newRight if not null
 Parameters:
 newRight  A reference to the new right subtree of this node.
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.
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.
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.
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.
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.
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.
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.
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.
preorderElements
public Iterator preorderElements()
 Return an iterator to traverse nodes of subtree inorder.
 Postcondition:
 The elements of the binary tree rooted at node n are
traversed in preorder
 Returns:
 Iterator to traverse subtree.
inorderElements
public Iterator inorderElements()
 Return an iterator to traverse the elements of subtree inorder.
 Postcondition:
 The elements of the binary tree rooted at node n are
traversed in inorder
 Returns:
 An inorder iterator over descendants of node.
postorderElements
public Iterator postorderElements()
 Return an iterator to traverse the elements of subtree in postorder.
 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.
levelorderElements
public Iterator levelorderElements()
 Method to return a levelorder 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 levelorder
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
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
value
public Object value()
 Returns value associated with this node.
 Postcondition:
 Returns value associated with this node.
 Returns:
 The node's value
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.
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