Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <stdlib.h>
- struct tree{
- int data;
- struct tree *left,*right;
- }*root = NULL;
- void insert(int val){
- struct tree *newNode = (struct tree*) malloc(sizeof(struct tree));
- newNode->data = val; newNode->right = newNode->left = NULL;
- if(!root) root = newNode;
- else{
- struct tree *help = root,*previous = NULL;
- while(help){
- previous = help;
- if(val < help->data) help = help ->left;
- else if(val > help->data) help = help->right;
- else{
- printf("\nDublicate values not allowed.\n");
- return;
- }
- }
- if(val > previous->data) previous->right = newNode;
- else previous->left = newNode;
- }
- }
- void eliminate(int value){
- struct tree *help = root, *previous = help;
- while (help){ //start from root, traverse until help becomes null or node's value matches
- if(help->data==value) break;
- previous = help;
- if (value > help-> data) help = help->right;
- else help = help->left;
- }
- if(!help) printf("Element not found!\n");
- else{
- struct tree *target = help;
- if (!target->left && !target->right) { //if node is a leaf node
- if(target == root)
- root = NULL;
- else if(previous->left == target) previous->left = NULL;
- else previous->right = NULL;
- }
- else if (!target->left || !target->right) { //if node has one child
- if(target == root){
- if(target->left) root = root->left;
- else root = root->right;
- }
- if(previous->left == target){
- if(target->left) previous->left = target->left;
- else previous->left = target->right;
- }
- else{
- if(target->left) previous->right = target->left;
- else previous->right = target->right;
- }
- }
- else { //if node has 2 children
- struct tree* t = target; //t will point to leftmost leaf node of target's right subtree
- t = t->right;
- while(t->left){
- previous = t;
- t = t->left;
- }
- if(t->right){
- previous = t;
- t = t->right;
- }
- target->data = t->data;
- if(previous->right) previous->right = NULL;
- else previous->left = NULL;
- free(t);
- }
- free(target);
- }
- }
- void display(struct tree* help){
- if(help){
- display(help->left);
- printf(" |%d| ", help->data);
- display(help->right);
- }
- if(!root) printf("The tree is empty.\n");
- }
- int main(){
- int n, choice;
- while(1){
- display(root);
- printf("\n\n1. Insert 2. Delete 3. Exit.\nInput: ");
- scanf("%d", &choice);
- switch(choice){
- case 1: printf("\nInsert: ");
- scanf("%d",&n);
- insert(n);
- break;
- case 2: if(root){
- printf("\nDelete: ");
- scanf("%d",&n);
- eliminate(n);
- }
- break;
- case 3: return 0;
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement