*USING the BST class provided below follow the assignment. MUST use BST Class provided below* class IntBinaryTree

{

private:

// The TreeNode struct is used to build the tree.

struct TreeNode

{

int value;

TreeNode *left;

TreeNode *right;

TreeNode(int value1,

TreeNode *left1 = nullptr,

TreeNode *right1 = nullptr)

{

value = value1;

left = left1;

right = right1;

}

};

TreeNode *root; // Pointer to the root of the tree

//**************************************************

// This version of insert inserts a number into *

// a given subtree of the main binary search tree. *

//**************************************************

void insert(TreeNode * &tree, int num)

{

// If the tree is empty, make a new node and make it

// the root of the tree. We are passing the node pointer by

// reference so that if it is replaced like below, the

// change will also impact the incoming argument.

if (!tree)

{

tree = new TreeNode(num);

return; //Terminate the function

}

// If num is already in tree: return.

if (tree->value == num)

return;

// The tree is not empty: insert the new node into the

// left or right subtree.

if (num < tree->value)

insert(tree->left, num);

else

insert(tree->right, num);

}

//***************************************************

// destroySubTree is called by the destructor. It *

// deletes all nodes in the tree. *

//***************************************************

void destroySubtree(TreeNode *tree)

{

if (!tree) return;

destroySubtree(tree->left);

destroySubtree(tree->right);

// Delete the node at the root.

delete tree;

}

//********************************************

// remove deletes the node in the given tree *

// that has a value member the same as num. *

//********************************************

void remove(TreeNode *&tree, int num)

{

if (tree == nullptr) return;

if (num < tree->value)

remove(tree->left, num);

else if (num > tree->value)

remove(tree->right, num);

else

// We have found the node to delete.

makeDeletion(tree);

}

void makeDeletion(TreeNode *&tree)

{

// Used to hold node that will be deleted.

TreeNode *nodeToDelete = tree;

// Used to locate the point where the

// left subtree is attached.

TreeNode *attachPoint;

if (tree->right == nullptr)

{

// Replace tree with its left subtree.

tree = tree->left;

}

else if (tree->left == nullptr)

{

// Replace tree with its right subtree.

tree = tree->right;

}

else

//The node has two children

{

// Move to right subtree.

attachPoint = tree->right;

// Locate the smallest node in the right subtree

// by moving as far to the left as possible.

while (attachPoint->left != nullptr)

attachPoint = attachPoint->left;

// Attach the left subtree of the original tree

// as the left subtree of the smallest node

// in the right subtree.

attachPoint->left = tree->left;

// Replace the original tree with its right subtree.

tree = tree->right;

}

// Delete root of original tree

delete nodeToDelete;

}

//*********************************************************

// This function displays the values stored in a tree *

// in inorder. *

//*********************************************************

void displayInOrder(TreeNode *tree) const

{

if (tree)

{

displayInOrder(tree->left);

cout << tree->value << " ";

displayInOrder(tree->right);

}

}

//*********************************************************

// This function displays the values stored in a tree *

// in inorder. *

//*********************************************************

void displayPreOrder(TreeNode *tree) const

{

if (tree)

{

cout << tree->value << " ";

displayPreOrder(tree->left);

displayPreOrder(tree->right);

}

}

//*********************************************************

// This function displays the values stored in a tree *

// in postorder. *

//*********************************************************

void displayPostOrder(TreeNode *tree) const

{

if (tree)

{

displayPostOrder(tree->left);

displayPostOrder(tree->right);

cout << tree->value << " ";

}

}

public:

// These member functions are the public interface.

IntBinaryTree() // Constructor

{

root = nullptr;

}

~IntBinaryTree() // Destructor

{

destroySubtree(root);

}

void insert(int num)

{

insert(root, num);

}

void remove(int num)

{

remove(root, num);

}

void showInOrder(void) const

{

displayInOrder(root);

}

void showPreOrder() const

{

displayPreOrder(root);

}

void showPostOrder() const

{

displayPostOrder(root);

}

//***************************************************

// searchNode determines if a value is present in *

// the tree. If so, the function returns true. *

// Otherwise, it returns false. *

//***************************************************

bool search(int num) const

{

TreeNode *tree = root;

while (tree)

{

if (tree->value == num)

return true;

else if (num < tree->value)

tree = tree->left;

else

tree = tree->right;

}

return false;

}

};

*Assignment to follow* In this assignment, you will write a program that inputs values from a file to a Binary Search Tree. See an example program run below:

Example Program Run 1:

Enter input filename: HW07_Input1.txt

Opening HW07_Input1.txt...

Inserting values into binary tree...

Printing Values In-Order: 17 238 240 291 299 307 311 421 434 520 534 558 584 600 620 625 639 643 698 701 702 732 761 819 833 835 857 861 880 937 956 967 982

Printing Values Pre-Order: 311 291 238 17 240 299 307 625 600 421 558 534 520 434 584 620 880 701 643 639 698 835 761 702 732 819 833 861 857 967 937 956 982

Printing Values Post-Order: 17 240 238 307 299 291 434 520 534 584 558 421 620 600 639 698 643 732 702 833 819 761 857 861 835 701 956 937 982 967 880 625 311

Printing Leaf Nodes: 17 240 307 434 584 620 639 698 732 833 857 956 982

Example Program Run 2:

Enter input filename: HW07_Input2.txt

Opening HW07_Input2.txt...

Inserting values into binary tree...

Printing Values In-Order: 1 2 3 4 5 6 7 8 9 10

Printing Values Pre-Order: 5 3 2 1 4 8 7 6 10 9

Printing Values Post-Order: 1 2 4 3 6 7 9 10 8 5

Printing Leaf Nodes: 1 4 6 9

Assignment Requirements (all must be met to receive full credit):

Use the IntBinaryTree implementation from class.

After inputting all values from the input file into the binary tree, your program should print all nodes in-order, pre-order and post-order.

Finally, print the leaf nodes:

. You will add functions to the IntBinaryTree class in order to do this.

. You will write a private, recursive function to print the leaf nodes within a tree.

. You will also write a public function which will call the private function - just like the public showInOrder function calls the private displayInOrder function.

. Remember that a leaf node is defined as a node without a left or right child.