write c++ code to implement the class BinTree. Class BinTree { Node *Root Constr

ID: 3590960 • Letter: W

Question

write c++ code to implement the class BinTree.

Class BinTree

{

Node *Root

Constructor

Destructor

void InOrder()

void PreOrder()

void PostOrder()

int Height()

int insert(int )

void Delete(int )

}

node-> int val;

Node *Left;

Node *Right;

Node *Pointer;

Node *Root;

int Depth()

int Level()

int Height()

Constructor:

Node();

Node(int);

Destructor:

~Node;

Explanation / Answer

#include<iostream>
#include<stdlib.h>
#include<conio.h>
#include <string.h>
using namespace std;
//Structure definition
struct BinaryTreeNode
{
//Structure member
int value;
BinaryTreeNode *left;
BinaryTreeNode *right;
};//End of structure

//Returns the node having minimum value
BinaryTreeNode* FindMin(BinaryTreeNode *tnode)
{
//Checks if tree is empty
if(tnode == NULL)
{
//There is no element in the tree
return NULL;
}
//Go to the left sub tree to find the min element
if(tnode -> left)
return FindMin(tnode -> left);
else
return tnode;
}//End of function

//Insert a node
BinaryTreeNode *Insert(BinaryTreeNode *tnode,int value)
{
//Checks if tree is empty
if(tnode == NULL)
{
//Creates a temporary pointer
BinaryTreeNode *temp;
temp = new BinaryTreeNode;
temp -> value = value;
//Initializes left and right node to null
temp -> left = temp -> right = NULL;
return temp;
}//End of if
//Checks if the entered value is greater than the current node value
if(value >(tnode -> value))
{
//Insert the node at right
tnode -> right = Insert(tnode -> right, value);
}//End of if
//Checks if the entered value is less than the current node value
else if(value < (tnode -> value))
{
//Insert the node at left
tnode -> left = Insert(tnode -> left, value);
}//End of else if
//Else there is nothing to do as the data is already in the tree.
return tnode;
}//End of function

//Function to delete a node from tree
BinaryTreeNode * Delete(BinaryTreeNode *tnode, int value)
{
//Creates a temporary pointer
BinaryTreeNode *temp;
//Checks if tree is empty
if(tnode == NULL)
{
cout<<"Element Not Found";
}//End of if
//Checks if the entered value is less than the current node value
else if(value < tnode -> value)
{
tnode -> left = Delete(tnode -> left, value);
}
//Checks if the entered value is greater than the current node value
else if(value > tnode -> value)
{
tnode -> right = Delete(tnode -> right, value);
}
else
{
//Now We can delete this node and replace with either minimum element in the right sub tree or maximum element in the left subtree
if(tnode -> right && tnode -> left)
{
//Here we will replace with minimum element in the right sub tree
temp = FindMin(tnode -> right);
tnode -> value = temp -> value;

//As we replaced it with some other node, we have to delete that node
tnode -> right = Delete(tnode -> right, temp -> value);
}
else
{
//If there is only one or zero children then we can directly remove it from the tree and connect its parent to its child
temp = tnode;
if(tnode -> left == NULL)
tnode = tnode -> right;
else if(tnode -> right == NULL)
tnode = tnode -> left;
//Delete temp
free(temp);
}//End of inner else
}//End of outer else
return tnode;
}//End of function

//Inorder traversal
void Inorder(BinaryTreeNode *tnode)
{
//Checks if tree is empty
if(tnode == NULL)
{
return;
}
//Recursively calls the left child node
Inorder(tnode -> left);
//Displays data
cout<<tnode -> value<<" ";
//Recursively calls the right child node
Inorder(tnode -> right);
}//End of function

//Pre order traversal
void Preorder(BinaryTreeNode *tnode)
{
//Checks if tree is empty
if(tnode == NULL)
{
return;
}
//Displays data
cout<<tnode -> value<<" ";
//Recursively calls the left child node
Preorder(tnode -> left);
//Recursively calls the right child node
Preorder(tnode -> right);
}//End of function

//Post order traversal
void Postorder(BinaryTreeNode *tnode)
{
//Checks if tree is empty
if(tnode == NULL)
{
return;
}
//Recursively calls the left child node
Postorder(tnode -> left);
//Recursively calls the right child node
Postorder(tnode -> right);
//Displays data
cout<<tnode -> value<<" ";
}//End of function

//Returns depth of the tree
int depth(BinaryTreeNode *tnode)
{
//Checks if tree is empty
if (tnode == NULL)
return 0;
//Recursively calls the function to calculate depth
return max( depth(tnode->left), depth(tnode->right) ) + 1;
}
//Main function
int main()
{
//Creates root and temporary node
BinaryTreeNode *root = NULL,*temp;
int val, x, y;
int ch;
//Loops till user choice is 7
while(1)
{
//Displays the menu
cout<<" 1 Insert 2 Delete 3 Inorder 4 Preorder 5 Postorder 6 Depth 7 Quit ";
//Accepts user choice
cout<<"Enter your choice: ";
cin>>ch;
//Checks the choice
switch(ch)
{
case 1:
cout<<" Enter the value to insert: ";
cin>>val;
root = Insert(root, val);
break;
case 2:
cout<<" Enter the value to delete: ";
cin>>val;
root = Delete(root,val);
break;
case 3:
cout<<" Inorder Traversal: ";
Inorder(root);
break;
case 4:
cout<<" Preorder Traversal:: ";
Preorder(root);
break;
case 5:
cout<<" Postorder Traversal:: ";
Postorder(root);
break;
case 6:
cout<<" Depth of the tree: "<<depth(root);
break;
case 7:
exit(0);
default:
cout<<" Invalid choice:";
}//End of switch
}//End of while
return 0;
}//End of main

Sample Run: