CSCI 3333.3 Data Structures
Spring 2013
Suggested Solution to Homework #7
Exercises:
(1) [1 5 [[[[[] 9 [12 13 []]] 16 17] 18 []] 20 [22 37 [[] 47 90]]]]
(2)
After deleting 15: [[[7 10 [12 13 []]] 27 29] 30 [[] 60 90]]
After deleting 13:
[[[7 10 12] 27 29] 30 [[] 60 90]]
After deleting 60:
[[[7 10 12] 27 29] 30 90]
After deleting 29:
[[[7 10 12] 27 []] 30 90]
(3) For example:
Algorithm RangeSearch(p: BST, low, high: integer);
Input:
p: root of an integer binary search tree.
[low, high]: the range of node values to be included the result.
Output:
result: an integer array containing all integers in the BST
with values in the range [low, high] in order.
size: number of integers in the array result.
size <- 0;
result <- empty;
RangeSearchHelper(p, low, high, size, result);
Algorithm RangeSearchHelper(p: BST, low, high: integer, result: integer array, size: integer);
Input:
p: root of an integer binary search tree.
[low, high]: the range of key values to be included the result.
result: an integer array that has been built so far.
size: number of integers in the array result.
Output:
result: an integer array in which all integers in the BST p
with values in the range [low, high] are added in order.
size: number of integers in the array result.
if p == null then
return;
end if;
if p.value > low then
RangeSearchHelper(p.left, low, high, result, size);
end if;
if low <= p.value and p.value <= high then
result[size] <- p.value;
size++;
end if;
if p.value < high then
RangeSearchHelper(p.right, low, high, result, size);
end if;
Program:
(1) (10%) Copy the content of the immediate successor to the targeted node and delete the immediate successor (which has no left child).
(2) and (3):
In BinaryNode.java, add:
// Print tree rooted at current node using inorder traversal with indentation
public void printInOrder(int identLevel)
{ if( left != null )
left.printInOrder(identLevel+1); // Left
for (int i=0; i<identLevel; i++) System.out.print(" ");
System.out.println(element); // Node
if( right != null )
right.printInOrder(identLevel+1); // Right
}
// Print tree rooted at current node using inorder traversal
// with element value within the range of [low, high].
public static void printRange(BinaryNode t, Comparable low, Comparable high)
{ if (t != null)
{ if (low.compareTo(t.element) < 0)
printRange(t.left, low, high); // Left
if ((low.compareTo(t.element) <= 0) && (high.compareTo(t.element) >= 0))
System.out.println(t.element); // Node
if(high.compareTo(t.element) > 0)
printRange(t.right, low, high); // Right
}
}
/**
* Return the size of the binary tree rooted at t.
*/
public static int size( BinaryNode t )
{
if( t == null )
return 0;
else
return 1 + size( t.left ) + size( t.right );
}
In the BinarySearchTree class, add:
/**
* Print BST with level indentation.
*/
public void printBST()
{
if (root != null)
root.printInOrder(0);
}
public int size( )
{
return BinaryNode.size( root );
}
public void printRange(Comparable low, Comparable high)
{ if ( root != null )
BinaryNode.printRange(root, low, high);
}