Exercise 1

Use provided C++ skeleton files to insert your code. A.

Implement a binary tree class MyTree using pointers (define struct BinaryNode to store internal nodes), where each node has a pointer to its children and to its parent, and each node holds two variable, a string myString and an integer myInt.

Write functions in MyTree class to do the following:

Insert (int,string): Insert new node into first available position (to keep the tree almost complete). E.g.,

To get full points your Insert functions should be faster than O(n), where n is # nodes in tree.

Hint: you may use an additional private variable in MyTree class.

Preorder (): Output all strings in pre-order.

FindMax (): returns a pointer to the node with maximum myInt.

MakeBST (): converts the binary tree into a binary search tree (BST) with respect to myInt. That

is, move around node values (myString and myInt) to satisfy the BST property. Do not change the structure of the tree (i.e. the pointers) but only swap myString and myInt values. (Hint: if you need to sort an array, you can use STLs sort() method)

e.g.,

B. What is the big-Oh complexity of your functions above?

Also, what is the space complexity of your functions? Are they all in-place? If not, how much extra space do they need?

C.

Test and measure the performance of your functions.

Create sequences of 100, 1000, 10000, 100000 random (int, string) pairs and insert them into MyTree (using Insert(.,.) function). Measure the times to (a) build the tree, (b) execute Preorder(), (c) execute FindMax(), (d) execute MakeBST().

Report the times for each tree size in a table.

Here is the skeleton code:

#include

#include

#include

using namespace std;

class MyTree;

class BinaryNode {

public:

BinaryNode(string s, int m) :myString(s), myInt(m) {};

~BinaryNode() {};

int getInt() const { return myInt; };

string getString() const { return myString; };

private:

string myString;

int myInt;

BinaryNode *lchild;

BinaryNode *rchild;

friend class MyTree;

};

class MyTree {

public:

MyTree();

~MyTree();

// Insert new node into first available position (to keep the tree almost complete).

void insert(int x, string s);

//Output all strings in pre-order

//all the strings will be print in one line separated by spaces

void preorder() const;

//Returns a pointer to the node with maximum myInt

BinaryNode *findMax() const;

// Converts the binary tree into a binary search tree (BST) with respect to myInt.

// That is, move around node values (myString and myInt) to satisfy the BST property.

void makeBST();

private:

MyTree *root;

};

MyTree::MyTree() {

}

MyTree::~MyTree() {

}

void MyTree::insert(int x, string s) {

}

void MyTree::preorder() const {}

BinaryNode* MyTree::findMax() const { return NULL; }

void MyTree::makeBST() {}

//Testing (you must implement yours for the perfomance studies)

int main() {

MyTree t;

//....

}