Untitled
unknown
plain_text
3 years ago
2.5 kB
4
Indexable
/* 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; }
Editor is loading...