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)

code

#include #include #include

using namespace std;

class MyTree;

class BinaryNode { // each Node include myString myInt public: BinaryNode(int m, string s):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; int getInt() 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; };

#include "MyTree.h"

MyTree::MyTree() { root = NULL; }

MyTree::~MyTree() { }

void MyTree::insert (int x ,string s) { BinaryNode *newElem; newElem = new BinaryNode(x,s); BinaryNode *lchild; if(root == NULL){ lchild = newElem; } }

void MyTree::preorder() const {}

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

void MyTree::makeBST() {}

int MyTree::getInt() const{ cout << this->BinaryNode->myInt << endl; return 0; }