components.binarytree

Class BinaryTreeUtility

java.lang.Object

components.binarytree.BinaryTreeUtility

public final class BinaryTreeUtility
extends java.lang.Object

A collection of useful methods for manipulating binary trees.

Author:

Matthew Shoemaker

Constructor Summary

Constructors

Constructor and Description
BinaryTreeUtility()

Method Summary

Modifier and Type	Method and Description
static <T> T	removeLeftMost(BinaryTree<T> t) Removes and returns the left-most node in t.
static <T> T	removeRightMost(BinaryTree<T> t) Removes and returns the right-most node in t.
static BinaryTree<java.lang.String>	treeFromString(java.lang.String str) Builds a binary tree from the given string.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

BinaryTreeUtility

public BinaryTreeUtility()

Method Detail

treeFromString

public static BinaryTree<java.lang.String> treeFromString(java.lang.String str)

Builds a binary tree from the given string. The string must be formatted such that: each subtree is denoted by its String label and 2 sets of parentheses, one for the right and one for the left. Empty subtrees must be explicitly denoted with empty parenthesis. For example, the simple binary tree with the root of "x" and a left child "y" and a right child "z" would be represented by: a(b()())(c()()) A tree with "x" as its root node and no children would be: x()() A tree with "x" as its root, an empty left subtree, and "z" as its right child would be denoted by: x()(z()()) A tree with "x" as its root, "y" as its left child, and an empty right subtree would be denoted by: x(y()())() Any tree can be expressed through the combination of the 4 examples.

Parameters:

str -

Returns:

a binary tree with the structure conveyed by the string parameter.

Requires:

[str defines a valid tree structure following the guidelines] and [str is not null]

Ensures:

treeFromString = {a binary tree with exactly the structure conveyed by the str argument]

removeLeftMost

public static <T> T removeLeftMost(BinaryTree<T> t)

Removes and returns the left-most node in t.

Type Parameters:

T - type of BinaryTree nodes

Parameters:

t - the BinaryTree from which to remove the node

Returns:

the left-most node in the given BinaryTree

Updates:

t

Requires:

t.size > 0

Ensures:

[the left-most node in t is removed from t and returned] and [if the left-most node has a right subtree, then its right subtree will be moved to the position in the tree where the left-most node was]

removeRightMost

public static <T> T removeRightMost(BinaryTree<T> t)

Removes and returns the right-most node in t.

Type Parameters:

T - type of BinaryTree nodes

Parameters:

t - the BinaryTree from which to remove the node

Returns:

the right-most node in the given BinaryTree

Updates:

t

Requires:

t.size > 0

Ensures:

[the right-most node in t is removed from t and returned] and [if the right-most node has a right subtree, then its right subtree will be moved to the position in the tree where the right-most node was]