Add methods to the Tree class of BST_Basic-004cpp.cpp to do the following:

1) find1, an iterative version of find that takes an int parameter and looks for it in the tree. Return NULL if not found, or a pointer to the Node containing the value if found.

2) find2, a recursive version of the method.

3) node_count, returns a count of the number of nodes in the tree.

4) depth, returns the depth of the deepest node in the tree. A null tree will have depth zero, a one node tree depth 1.

#include

using namespace std;

//=====================================================================

struct Node

{

int x;

Node * left;

Node * right;

Node(){left = NULL; right = NULL;}

Node(int d, Node* l = 0, Node* r = 0)

{

x = d;

left = l;

right = r;

}

};

//=====================================================================

class Tree

{

private:

Node * root;

public:

Tree()

{

root = NULL;

}

//-----------------------------------------------------------------

void insert(int x)

{

Node * ptr = new Node(x);

cout << " -------------------------------------" << endl;

cout << "Node Address: " << ptr << endl;

if (root == NULL)

root = ptr;

else

{

Node * temp = root;

while (true)

{

if (temp -> x > x)

{

if (temp -> left == NULL) {

cout << "Node Parent Address: " << temp << endl;

cout << "Node Parent Value: " << temp -> x << endl;

temp -> left = ptr;

break;

} else

temp = temp -> left;

} else

{

if (temp -> right == NULL)

{

cout << "Node Parent Address: " << temp << endl;

cout << "Node Parent Value: " << temp -> x << endl;

temp -> right = ptr;

break;

} else

temp = temp -> right;

}

}

}

cout << "Root: " << root << endl;

cout << "-------------------------------------" << endl;

}

//-----------------------------------------------------------------

public: void inOrder(){ inOrder(root); }

private: void inOrder(Node * temp) {

if (temp != NULL)

{

inOrder(temp -> left);

cout << temp -> x << " ";

inOrder(temp -> right);

}

}

//-----------------------------------------------------------------

public: void preOrder(){ inOrder(root); }

private: void preOrder(Node * temp)

{

if (temp != NULL) {

cout << temp -> x << " ";

preOrder(temp -> left);

preOrder(temp -> right);

}

}

//-----------------------------------------------------------------

public: void postOrder(){ inOrder(root); }

private: void postOrder(Node * temp)

{

if (temp != NULL) {

postOrder(temp -> left);

postOrder(temp -> right);

cout << temp -> x << " ";

}

}

//-----------------------------------------------------------------

public: void serial(){ serial(root); }

private: void serial(Node *n)

{

cout << '(';

if (n != 0)

{

cout << n->x << ' ';

serial(n->left); cout << ' ';

serial(n->right);

}

cout << ')';

}

//-----------------------------------------------------------------

public: Node * getRoot() {

return root;

}

//-----------------------------------------------------------------

public: void display(){ display(root); }

private: void display(Node * temp)

{

if (temp != NULL) {

cout << endl;

cout << "Parent: " << temp -> x << endl;

cout << " Left Child of " << temp -> x << ": ";

if (temp -> left == NULL)

cout << "NULL" << endl;

else

cout << temp -> left -> x << endl;

cout << " Right Child of " << temp -> x << ": ";

if (temp -> right == NULL)

cout << "NULL" << endl;

else

cout << temp -> right -> x << endl;

display(temp -> left);

display(temp -> right);

}

}

//-----------------------------------------------------------------

bool isEmpty()

{

if (root == NULL)

return true;

return false;

}

public:

//-----------------------------------------------------------------

void removeAll(int value)

{

while (true)

{

Node * temp = root, * ptemp = root;

while (temp != NULL && temp -> x != value)

{

ptemp = temp;

if (temp -> x < value)

temp = temp -> right;

else if (temp -> x > value)

temp = temp -> left;

}

if (temp == NULL)

{

cout << "All nodes cotaining " << value << " are deleted" << endl;

break;

} else

{

if (temp -> left == NULL && temp -> right == NULL)

{

if (temp == root)

root = NULL;

else if (ptemp -> left == temp)

ptemp -> left = NULL;

else if (ptemp -> right == temp)

ptemp -> right = NULL;

} else if (temp -> left == NULL && temp -> right != NULL)

{

if (temp == root)

root = temp -> right;

else if (ptemp -> left == temp)

ptemp -> left = temp -> right;

else if (ptemp -> right == temp)

ptemp -> right = temp -> left;

} else if (temp -> right == NULL && temp -> left != NULL)

{

if (temp == root)

root = temp -> left;

else if (ptemp -> left == temp)

ptemp -> left = temp -> left;

else if (ptemp -> right == temp)

ptemp -> right = temp -> right;

} else if (temp -> left != NULL && temp -> right != NULL)

{

Node * tempHolder = temp, * ptempHolder = temp;

while (tempHolder -> left != NULL)

{

ptempHolder = tempHolder;

tempHolder = tempHolder -> left;

}

temp -> x = tempHolder -> x;

ptempHolder -> left = tempHolder -> right;

temp = tempHolder;

}

delete temp;

cout << "Node Removed Successfully." << endl;

}

}

}

//-----------------------------------------------------------------

void remove(int value)

{

Node * temp = root, * ptemp = root;

while (temp != NULL && temp -> x != value)

{

ptemp = temp;

if (temp -> x < value)

temp = temp -> right;

else if (temp -> x > value)

temp = temp -> left;

}

if (temp == NULL) {

cout << "Value Not Found...." << endl;

} else

{

if (temp -> left == NULL && temp -> right == NULL)

{

if (temp == root)

root = NULL;

else if (ptemp -> left == temp)

ptemp -> left = NULL;

else if (ptemp -> right == temp)

ptemp -> right = NULL;

} else if (temp -> left == NULL && temp -> right != NULL)

{

if (temp == root)

root = temp -> right;

else if (ptemp -> left == temp)

ptemp -> left = temp -> right;

else if (ptemp -> right == temp)

ptemp -> right = temp -> left;

} else if (temp -> right == NULL && temp -> left != NULL)

{

if (temp == root)

root = temp -> left;

else if (ptemp -> left == temp)

ptemp -> left = temp -> left;

else if (ptemp -> right == temp)

ptemp -> right = temp -> right;

} else if (temp -> left != NULL && temp -> right != NULL)

{

Node * tempHolder = temp, * ptempHolder = temp;

while (tempHolder -> left != NULL)

{

ptempHolder = tempHolder;

tempHolder = tempHolder -> left;

}

temp -> x = tempHolder -> x;

ptempHolder -> left = tempHolder -> right;

temp = tempHolder;

}

delete temp;

cout << "Node Removed Successfully." << endl;

}

}

//-----------------------------------------------------------------

void deleteAllNodes(Node * temp) {

if (temp != NULL) {

deleteAllNodes(temp -> left);

deleteAllNodes(temp -> right);

cout << "Address: " << temp << endl;

cout << "Value: " << temp -> x << endl << endl;

delete temp;

}

}

//-----------------------------------------------------------------

~Tree() {

cout << "Below Nodes Deleted Successfully:" << endl;

deleteAllNodes(root);

}

};

//=====================================================================

int main(){

Tree T, S;

T.insert(50);

T.insert(20);

T.insert(80);

T.insert(60);

T.insert(90);

T.display();

T.serial(); cout << endl;

S = T;

S.serial(); cout << endl;

T.insert(100);

cout << "After insert 100 ";

T.serial(); cout << endl;

S.serial(); cout << endl;

system("pause");

return 0;

}

/*

(50 (20 () ()) (80 (60 () ()) (90 () ())))

(50 (20 () ()) (80 (60 () ()) (90 () ())))

-------------------------------------

Node Address: 0x941a40

Node Parent Address: 0x941a20

Node Parent Value: 90

Root: 0x941500

-------------------------------------

After insert 100

(50 (20 () ()) (80 (60 () ()) (90 () (100 () ()))))

(50 (20 () ()) (80 (60 () ()) (90 () (100 () ()))))

*/