Could somebody please show me how would this look on C++? Inserting a node in Bi
ID: 3571852 • Letter: C
Question
Could somebody please show me how would this look on C++? Inserting a node in Binary Search Tree?
// REQUIRES: item is not already contained in the tree rooted at 'node'
// MODIFIES: the tree rooted at 'node'
// EFFECTS : If 'node' represents an empty tree, allocates a new Node to
// represent a single element tree with 'item' as its only element.
// If the tree rooted at 'node' is not empty, inserts 'item' into
// the proper location as a leaf in the existing tree structure
// according to the sorting invariant and returns the original
// parameter 'node'.
// NOTE: This function must be linear recursive, but does not
// need to be tail recursive.
// HINT: Element ordering is defined according to the Compare functor
// associated with this instantiation of the BinarySearchTree
// template, NOT according to the < operator. Use the "less"
// parameter to compare elements.
static Node * insert_impl(Node *node, const T &item, Compare less) {
Explanation / Answer
# include <iostream>
# include <cstdlib>
//#define LESS < // will not workiing means not compare proper
using namespace std;
/* declare node */
struct Node
{
int info;
struct Node *left;
struct Node *right;
}*root;
class BST
{
public:
void insertNode(Node *, Node *);
void displayTree(Node *, int);
BST()
{
root = NULL;
}
};
void BST :: insertNode(Node *node, Node *newnode)
{
if (root == NULL)
{
root = new Node;
root->info = newnode->info;
root->left = NULL;
root->right = NULL;
cout<<"Root Node is Added"<<endl;
return;
}
if (node->info == newnode->info)
{
cout<<"Element already in the tree"<<endl;
return;
}
if (node->info < newnode->info)
{
if (node->right != NULL)
{
insertNode(node->right, newnode);
}
else
{
node->right = newnode;
(node->right)->left = NULL;
(node->right)->right = NULL;
cout<<"Node Added To Right"<<endl;
return;
}
}
else
{
if (node->left != NULL)
{
insertNode(node->left, newnode);
}
else
{
node->left = newnode;
(node->left)->left = NULL;
(node->left)->right = NULL;
cout<<"Node Added To Left"<<endl;
return;
}
}
}
void BST :: displayTree(Node *ptr, int level)
{
int i;
if (ptr != NULL)
{
displayTree(ptr->right, level+1);
cout<<endl;
if (ptr == root)
cout<<"Root->: ";
else
{
for (i = 0;i < level;i++)
cout<<" ";
}
cout<<ptr->info;
displayTree(ptr->left, level+1);
}
}
int main()
{
int num;
BST bst;
Node *temp;
int opt;
temp = new Node;
while(1){
cout<<" 1. insertion 2. display 3. exit Enter option : ";
cin>>opt;
switch(opt){
case 1: cout<<"Enter the number to be inserted : ";
cin>>temp->info;
bst.insertNode(root, temp);
break ;
case 2: cout<<"Display BST:"<<endl;
bst.displayTree(root,1);
cout<<" ";
break;
case 3: exit(1);
break;
default : cout<<"Invalid otption ";
break;
}
}
}