Untitled

unknown
plain_text
2 years ago
2.5 kB
1
Indexable
Never
```/*
week 8
1> write a program to delete a node from a binary search tree.

leaf level
subtree level
root deletion
reconstruct the tree after deletion

Implement a heap using top down aproach to construct a min heap.

*/
#include <stdio.h>
#include <stdlib.h>

struct node {
int key;
struct node *left, *right;
};

struct node* newNode(int item)
{
struct node* temp
= (struct node*)malloc(sizeof(struct node));
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}

void inorder(struct node* root)
{
if (root != NULL) {
inorder(root->left);
printf("%d ", root->key);
inorder(root->right);
}
}

struct node* insert(struct node* node, int key)
{

if (node == NULL)
return newNode(key);

if (key < node->key)
node->left = insert(node->left, key);
else
node->right = insert(node->right, key);

return node;
}

struct node* minValueNode(struct node* node)
{
struct node* current = node;

while (current && current->left != NULL)
current = current->left;

return current;
}

struct node* deleteNode(struct node* root, int key)
{

if (root == NULL)
return root;

if (key < root->key)
root->left = deleteNode(root->left, key);

else if (key > root->key)
root->right = deleteNode(root->right, key);

else {

if (root->left == NULL) {
struct node* temp = root->right;
free(root);
return temp;
}
else if (root->right == NULL) {
struct node* temp = root->left;
free(root);
return temp;
}

struct node* temp = minValueNode(root->right);

root->key = temp->key;

root->right = deleteNode(root->right, temp->key);
}
return root;
}

int main()
{

struct node* root = NULL;
int c=1;
do{
printf("\nOperations:\n1. Insert node into tree\n2. Inorder traversal\n3. Delete a node\n4. Exit\nEnter your choice: ");
int ch;
scanf("%d",&ch);

int x;
switch(ch){
case 1:
printf("\nEnter value to insert: ");
scanf("%d",&x);
root=insert(root,x);
break;
case 2:
printf("\nInorder traversal of the tree:\n");
inorder(root);
break;
case 3:
printf("\nEnter value to delete: ");
scanf("%d",&x);
root=deleteNode(root,x);
break;
case 4:
c=0;
break;
}

}while(c==1);

return 0;
}```