binTree.cpp

#include

using namespace std;

struct treeNode {

int val;

treeNode *left;

treeNode *right;

};

void initialize(treeNode *t, int n) {

t->val = n;

t->left = t->right = 0;

}

void insert(treeNode *t, int n) {

cout << "insert t " << t->val << " n " << n << endl;

treeNode **child;

if (n <= t->val) child = &(t->left);

else child = &(t->right);

if (0 == *child) { // create new node and store value

*child = new treeNode;

initialize(*child, n);

} else { // recurse on the correct branch

insert(*child, n);

}

}

void remove(treeNode *t) {

cout << "remove t " << t->val << endl;

if (t->left) remove(t->left); // get rid of left subtree

if (t->right) remove(t->right); // get rid of right subtree

delete t;

}

void preorderPrint( treeNode *t ) {

// Print all the items in the tree to which t points.

// The item in the root is printed first, followed by the

// items in the left subtree and then the items in the

// right subtree.

if (t != NULL) { // (Otherwise, there's nothing to print.)

cout << t->val << " "; // Print the root item.

preorderPrint(t->left); // Print items in left subtree.

preorderPrint(t->right); // Print items in right subtree.

}

}

void postorderPrint( treeNode *t ) {

// Print all the items in the tree to which t points.

// The items in the left subtree are printed first, followed

// by the items in the right subtree and then the item in the

// root node.

if (t != NULL) { // (Otherwise, there's nothing to print.)

postorderPrint(t->left); // Print items in left subtree.

postorderPrint(t->right); // Print items in right subtree.

cout << t->val << " "; // Print the root item.

}

}

void inorderPrint( treeNode *t ) {

// Print all the items in the tree to which t points.

// The items in the left subtree are printed first, followed

// by the item in the root node, followed by the items in

// the right subtree.

if (t != NULL ) { // (Otherwise, there's nothing to print.)

inorderPrint(t->left); // Print items in left subtree.

cout << t->val << " "; // Print the root item.

inorderPrint(t->right); // Print items in right subtree.

}

}

int main() {

treeNode *root = new treeNode;

initialize(root, 5);

insert(root, 3);

insert(root, 4);

preorderPrint(root);

cout << endl;

inorderPrint(root);

cout << endl;

postorderPrint(root);

cout << endl;

insert(root, 0);

insert(root, 8);

insert(root, 10);

insert(root, 100);

insert(root, 9);

insert(root, 5);

preorderPrint(root);

cout << endl;

inorderPrint(root);

cout << endl;

postorderPrint(root);

cout << endl;

remove(root);

}

Add the function treeContains(treeNode *t, int item) to your binTree.cpp file, according to the following spec. This will be easiest (and run the fastest) if implemented recursively.

treeContains

2 Arguments:

t a treeNode pointer

item the int you are looking for in the tree

Return: A bool value, true if item is included in the tree, false otherwise.

Create 5 new trees in your main() that contain 15, 31, 63, 127, and 255 random values between 0 and 1000. Each tree should be built with the same numbers, up to the required size of the tree (so all 5 will have 15 values in common, all but the size 15 tree will have another 31 values in common, the larger 3 will have 63 values in common, and the largest 2 will have 127 values in common). Call your tree objects t15, t31, t63, t127, and t255 (with the number in the name corresponding to the size of the tree).

Take a look at the code in quicksort.cpp from Monday, and note how there is a global variable that is used to track how many times the function is called. Set up and use a similar global variable in your code in order to count how many times the treeContains function is called when searching a tree.

Print out a statement such as the following (it will differ by the values in red) in your main() after calling treeContains on each tree (be sure to reset your counter to 0 between calls, or it will keep accumulating):

treeContains was called 5 times for an item that was NOT FOUND in a BST with 15 nodes.

Be sure to test your function on values that are in the trees and values that are not (you should use a method similar to the search assignment to pull 5 values from the size 15 tree, and then generate 5 new random values that probably wont be in the tree), to be sure the function is working as described.

What do you notice about how many times treeContains is called when a value is not found in the tree?

What do you notice about how many times treeContains is called when looking for a value that is in all 5 trees? What is this telling you about the location of that value in the tree?

Add the function isBST(treeNode *t, int min, int max) to your binTree.cpp file, according to the following spec. Use the min and max parameters to bound what value a particular node may have, updating as you recursively call your function.

isBST

3 Arguments:

t a treeNode pointer

min an int representing the min value seen so far

max an int representing the max value seen so far

Return: A bool value, true if the tree is a valid Binary Search Tree, false otherwise.

The trick here is that you start with a very large range between min and max, and slowly narrow it as you move deeper in the tree (from a parent node, when you make the recursive call using the left child, max will be set to the value in parent, leaving min unchanged, while when you make the recursive call using the right child, min will be set to the value in parent, leaving max unchanged).

Your initial call the the function in main() will look like the following, changing only the red text for the different trees that you are testing on (note that youll either want to print out the result, or assign it to a variable that you later print out), because INT_MIN and INT_MAX are built in constant variables provided in C++:

sBST(t15, INT_MIN, INT_MAX);

Be sure to test your function on trees that are valid Binary Search Trees (like the ones from the previous problem) and on trees that are not. To make a tree that is not a valid BST, start by making a tree in the same way you did previously, then go in and change at least one nodes value to make it not a valid BST for testing purposes--it might be useful to make several copies of the same tree, and in each one, change a different nodes value to see if that impacts your function. I suggest starting with very small trees to confirm it works quickly, then try running the function on larger trees.