Answer to Question #281545 in C++ for Skye

Question

1. Write a C++ program to show the implementation of the Binary Search Tree (BST) using a linked list. Your program must include all the operations in Binary Search Tree (BST) including

− creating BST

− inserting an item into BST

− display item in BST

Answer 1

#include <stdio.h>

#include <stdlib.h>

struct BST

{

int data;

struct BST *left;

struct BST *right;

};

typedef struct BST NODE;

NODE *node;

NODE* createtree(NODE *node, int data)

{

if (node == NULL)

{

NODE *temp;

temp= (NODE*)malloc(sizeof(NODE));

temp->data = data;

temp->left = temp->right = NULL;

return temp;

}

if (data < (node->data))

{

node->left = createtree(node->left, data);

}

else if (data > node->data)

{

node -> right = createtree(node->right, data);

}

return node;

}

NODE* search(NODE *node, int data)

{

if(node == NULL)

printf("\nElement not found");

else if(data < node->data)

{

node->left=search(node->left, data);

}

else if(data > node->data)

{

node->right=search(node->right, data);

}

else

printf("\nElement found is: %d", node->data);

return node;

}

void inorder(NODE *node)

{

if(node != NULL)

{

inorder(node->left);

printf("%d\t", node->data);

inorder(node->right);

}

}

void preorder(NODE *node)

{

if(node != NULL)

{

printf("%d\t", node->data);

preorder(node->left);

preorder(node->right);

}

}

void postorder(NODE *node)

{

if(node != NULL)

{

postorder(node->left);

postorder(node->right);

printf("%d\t", node->data);

}

}

NODE* findMin(NODE *node)

{

if(node==NULL)

{

return NULL;

}

if(node->left)

return findMin(node->left);

else

return node;

}

NODE* del(NODE *node, int data)

{

NODE *temp;

if(node == NULL)

{

printf("\nElement not found");

}

else if(data < node->data)

{

node->left = del(node->left, data);

}

else if(data > node->data)

{

node->right = del(node->right, data);

}

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(node->right && node->left)

{ /* Here we will replace with minimum element in the right sub tree */

temp = findMin(node->right);

node -> data = temp->data;

/* As we replaced it with some other node, we have to delete that node */

node -> right = del(node->right,temp->data);

}

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 = node;

if(node->left == NULL)

node = node->right;

else if(node->right == NULL)

node = node->left;

free(temp); /* temp is longer required */

}

}

return node;

}

void main()

{

int data, ch, i, n;

NODE *root=NULL;

while (1)

{

printf("\n1.Insertion in Binary Search Tree");

printf("\n2.Search Element in Binary Search Tree");

printf("\n3.Delete Element in Binary Search Tree");

printf("\n4.Inorder\n5.Preorder\n6.Postorder\n7.Exit");

printf("\nEnter your choice: ");

scanf("%d", &ch);

switch (ch)

{

case 1: printf("\nEnter N value: " );

scanf("%d", &n);

printf("\nEnter the values to create BST like(6,9,5,2,8,15,24,14,7,8,5,2)\n");

for(i=0; i<n; i++)

{

scanf("%d", &data);

root=createtree(root, data);

}

break;

case 2: printf("\nEnter the element to search: ");

scanf("%d", &data);

root=search(root, data);

break;

case 3: printf("\nEnter the element to delete: ");

scanf("%d", &data);

root=del(root, data);

break;

case 4: printf("\nInorder Traversal: \n");

inorder(root);

break;

case 5: printf("\nPreorder Traversal: \n");

preorder(root);

break;

case 6: printf("\nPostorder Traversal: \n");

postorder(root);

break;

case 7: exit(0);

default:printf("\nWrong option");

break;

}

}

}