Answer to Question #230748 in C++ for Skye Jordan

Question

1. Write a C++ program to show the implementation of the Binary Search Tree using a linked list. The program must include all the operations in Binary Search Tree with explanation including:

• creating BST
• inserting an item into BST
• display item in BST

Answer 1

#include <iostream>


using namespace std;
   
struct b_node 
{ 
    int data; 
    struct b_node *left, *right; 
    };  
    struct b_node *newNode(int k) 
    { 
    struct b_node *temp =  new struct b_node(); 
    temp->data = k; 
    temp->left = temp->right = NULL; 
    return temp; 
} 
   


void inorder(struct b_node *root) 
{ 
    if (root != NULL) 
        { 
    inorder(root->left); 
    cout<<root->data<<" "; 
    inorder(root->right); 
        } 
} 
   


struct b_node* insert(struct b_node* node, int k) 
{ 
   
if (node == NULL) return newNode(k); 
   
if (k < node->data) 
node->left  = insert(node->left, k); 
else
node->right = insert(node->right, k); 
   
return node; 
} 
struct b_node * minValueNode(struct b_node* node) 
{ 
struct b_node* current = node; 
   
while (current && current->left != NULL) 
current = current->left; 
   
return current; 
} 
  
struct b_node* deleteNode(struct b_node* root, int k) 
{ 
     
if (root == NULL) return root; 
   
if (k < root->data) 
root->left = deleteNode(root->left, k); 
    
else if (k > root->data) 
root->right = deleteNode(root->right, k); 
   
else
    { 
if (root->left == NULL) 
        { 
struct b_node *temp = root->right; 
free(root); 
return temp; 
        } 
else if (root->right == NULL) 
        { 
struct b_node *temp = root->left; 
free(root); 
return temp; 
        } 
   
struct b_node* temp = minValueNode(root->right); 
   
root->data = temp->data; 
         
root->right = deleteNode(root->right, temp->data); 
    } 
    return root; 
}   
int main() 
{ 


    struct b_node *root = NULL; 
    root = insert(root, 10); 
    root = insert(root, 20); 
    root = insert(root, 70); 
    root = insert(root, 50); 
    root = insert(root, 80); 
     
    cout<<"Binary Search Tree created "<<endl; 
    inorder(root); 
    cout<<"\nDelete node 70\n"; 
    root = deleteNode(root, 70); 
    cout<<"Inorder traversal for the modified Binary Search Tree:"<<endl; 
    inorder(root); 
       
return 0; 
}