Data Structures Program #12

CS 153 Data Structures I

Assignment #12

Due: 11/8/01

Purpose: to learn about removing a node from a binary search trees (BST)

Testing: You will be asked to show removals of all the different cases (0, 1 and 2 children) maybe involving the Root.

Interface: The Visual interface should have the following components

Insert button
Remove button
Find button - the result may be displayed in either a
- MessageBox
- Special EditBox
EditBox for specifing data
ListBox for showing the content of the tree
- Update this display after each Insert or Remove
- List the information IN-ORDER

BST member functions:

The same ones as Assignment #11
void Remove(int);
private void RemoveHelper(int, Node *);

Optional

If you do this portion successfully your team will be awarded an extra late free pass

Build the BST class with iterator capability. An iterator capability involves having functions

void BST::Reset()
int BST::GetNext();
bool BST::EOT(); //End of Tree

If you have this capabilty, then Display() should be a 'user function' coded in the ...Dlg class and you should remove BST::Display function.

In class we will discuss how to build the iterator functions. This capability will involve the use of a stack that holds data of type Node *. For this stack you may use choose from:

The stack that you built earlier in the semester
The stack type provided by Microsoft's MSDN library
The stack type provided by the STL (Standard Template Library)