trees

Class BinarySearchTree<K extends java.lang.Comparable<K>,V>

java.lang.Object

trees.BinarySearchTree<K,V>

public class BinarySearchTree<K extends java.lang.Comparable<K>,V>
extends java.lang.Object

Constructor Summary

Constructors

Constructor and Description
BinarySearchTree()

Method Summary

Methods

Modifier and Type	Method and Description
boolean	add(K key, V data)
static BinarySearchTree<java.lang.Integer,java.lang.String>	createBalancedTree()
int	getInteriorNodesCount() This method computes the number of interior nodes in the tree.
int	getLeavesCount() This method computes the number of leave nodes in the tree.
int	getMaximum() This method computes the maximum key value in the tree.
static void	main(java.lang.String[] args)
boolean	same(BinarySearchTree tree) This method determines whether the parameter and the current object tree have the same keys (ignore the values the key are mapped to).
boolean	sameShape(BinarySearchTree tree) This method determines whether the parameter and the current object tree have the same shape (we don't care about keys/values).
int	size() This method computes the tree size.
java.lang.String	toString()

Methods inherited from class java.lang.Object

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

Constructor Detail

BinarySearchTree

public BinarySearchTree()

Method Detail

main

public static void main(java.lang.String[] args)

add

public boolean add(K key,
          V data)

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object

createBalancedTree

public static BinarySearchTree<java.lang.Integer,java.lang.String> createBalancedTree()

getMaximum

public int getMaximum()

This method computes the maximum key value in the tree. Implement this method using recursion. You may only add one auxiliary function and you may not add any auxiliary instance/static variables.

Returns:

maximum key value

size

public int size()

This method computes the tree size. Implement this method using recursion. You may only add one auxiliary function and you may not add any auxiliary instance/static variables.

Returns:

tree size

getLeavesCount

public int getLeavesCount()

This method computes the number of leave nodes in the tree. Implement this method using recursion. You may only add one auxiliary function and you may not add any auxiliary instance/static variables.

Returns:

leave count

getInteriorNodesCount

public int getInteriorNodesCount()

This method computes the number of interior nodes in the tree. You may not implement this method by calling size() and getLeavesCount(). Implement this method using recursion. You may only add one auxiliary function and you may not add any auxiliary instance/static variables.

Returns:

number of interior nodes

same

public boolean same(BinarySearchTree tree)

This method determines whether the parameter and the current object tree have the same keys (ignore the values the key are mapped to).

Returns:

true if same keys present; false otherwise

sameShape

public boolean sameShape(BinarySearchTree tree)

This method determines whether the parameter and the current object tree have the same shape (we don't care about keys/values).

Returns:

true if same shape; false otherwise