Bag ADT is same as before. Will call the new class IntTreeBag to distinguish it.

Here is the list of IntTreeBag instance variables (private) and methods (public):

Goal: implement IntTreeBag methods using IntBTNode methods when feasible.

For reference, IntBTNode documentation is stored in Lab 8 folder.

Consider implementation of IntLinkedBag methods: countOccurrences, add, remove.

Starting a root, descend through tree until dead-end (null node). At each node, compare target value to node's data. If target is less, continue descent down left subtree. If target is greater, continue descent down right subtree. If target is equal, increment counter and continue descent down left (using textbook definition of BST) subtree.

Consider recursive vs. iterative method. Develop iterative method.

new node will always be added as leaf. Descend tree until spot is found, then link it in. The solution shown here (and described in textbook) is iterative, not recursive. Compare to lab 8.

// Used by driver program but not used to implement remove method.
// Note this is an iterative method. 
public void add(int element)
{
	IntBTNode cursor = root;
	boolean placed = false;
	IntBTNode newNode = new IntBTNode(element, null, null);
	if (root == null)
		root = newNode;
	else
		while (!placed)
			if (element <= cursor.getData())
				if (cursor.getLeft()==null)
				{
					cursor.setLeft(newNode);
					placed = true;
				}
				else
					cursor = cursor.getLeft();
			else
				if (cursor.getRight()==null)
				{
					cursor.setRight(newNode);
					placed = true;
				}
				else
					cursor = cursor.getRight();
}

Need to first search for the target, then consider four possible removal situations (see pages 469-470).

1. The target is not found. This is discovered when descending the binary search tree leads to a dead-end (null node) without matching the target value. In this case, return false.
2. The target is found at the root and the root has no left child. In this case, the right child becomes the new root.
3. The target is found below the root, but the target node has no left child. In this case, the target node's parent will "adopt" the target node's right child upon removal of the target node. If the target node was a left child, its right child will become its parent's left child. If the target node was a right child, its right child will become its parent's right child.
4. The target is found and the target node does have a left child. In this case, we want to replace the target node with the node containing the next smaller value -- the rightmost node of the target node's left subtree. This potentially requires changing several links, but there is an easier way. Simply copy the data value from the "rightmost in left subtree" node into the data field of the target node, then remove the "rightmost in left subtree" node. The IntBTNode class provides methods to support both of these operations (getRightmostData, removeRightmost).

[ Lectures | CSC 132 | Peter Sanderson | Computer Science | SMSU ]

Peter Sanderson ( PeteSanderson@smsu.edu )