C program to delete a node, where the data value of the node to be deleted is known | DS Deleting Node Link List | Link List Program for node deletion
#include#include struct tnode { int data; struct tnode *lchild, *rchild; }; /* A function to get a pointer to the node whose data value is given as well as the pointer to its root */ struct tnode *getptr(struct tnode *p, int key, struct tnode **y) { struct tnode *temp; if( p == NULL) return(NULL); temp = p; *y = NULL; while( temp != NULL) { if(temp->data == key) return(temp); else { *y = temp; /*store this pointer as root */ if(temp->data > key) temp = temp->lchild; else temp = temp->rchild; } } return(NULL); } /* A function to delete the node whose data value is given */ struct tnode *delete(struct tnode *p,int val) { struct tnode *x, *y, *temp; x = getptr(p,val,&y); if( x == NULL) { printf("The node does not exists\n"); return(p); } else { /* this code is for deleting root node*/ if( x == p) { temp = x->lchild; y = x->rchild; p = temp; while(temp->rchild != NULL) temp = temp->rchild; temp->rchild=y; free(x); return(p); } /* this code is for deleting node having both children */ if( x->lchild != NULL && x->rchild != NULL) { if(y->lchild == x) { temp = x->lchild; y->lchild = x->lchild; while(temp->rchild != NULL) temp = temp->rchild; temp->rchild=x->rchild; x->lchild=NULL; x->rchild=NULL; } else { temp = x->rchild; y->rchild = x->rchild; while(temp->lchild != NULL) temp = temp->lchild; temp->lchild=x->lchild; x->lchild=NULL; x->rchild=NULL; } free(x); return(p); } /* this code is for deleting a node with on child*/ if(x->lchild == NULL && x->rchild !== NULL) { if(y->lchild == x) y->lchild = x->rchild; else y->rchild = x->rchild; x->rchild; = NULL; free(x); return(p); } if( x->lchild != NULL && x->rchild == NULL) { if(y->lchild == x) y->lchild = x->lchild ; else y->rchild = x->lchild; x->lchild = NULL; free(x); return(p); } /* this code is for deleting a node with no child*/ if(x->lchild == NULL && x->rchild == NULL) { if(y->lchild == x) y->lchild = NULL ; else y->rchild = NULL; free(x); return(p); } } } /*an iterative function to print the binary tree in inorder*/ void inorder1(struct tnode *p) { struct tnode *stack[100]; int top; top = −1; if(p != NULL) { top++; stack[top] = p; p = p->lchild; while(top >= 0) { while ( p!= NULL)/* push the left child onto stack*/ { top++; stack[top] =p; p = p->lchild; } p = stack[top]; top-; printf("%d\t",p->data); p = p->rchild; if ( p != NULL) /* push right child*/ { top++; stack[top] = p; p = p->lchild; } } } } /* A function to insert a new node in binary search tree to get a tree created*/ struct tnode *insert(struct tnode *p,int val) { struct tnode *temp1,*temp2; if(p == NULL) { p = (struct tnode *) malloc(sizeof(struct tnode)); /* insert the new node as root node*/ if(p == NULL) { printf("Cannot allocate\n"); exit(0); } p->data = val; p->lchild=p->rchild=NULL; } else { temp1 = p; /* traverse the tree to get a pointer to that node whose child will be the newly created node*/ while(temp1 != NULL) { temp2 = temp1; if( temp1 ->data > val) temp1 = temp1->lchild; else temp1 = temp1->rchild; } if( temp2->data > val) { temp2->lchild = (struct tnode*)malloc(sizeof(struct tnode));/ *inserts the newly created node as left child*/ temp2 = temp2->lchild; if(temp2 == NULL) { printf("Cannot allocate\n"); exit(0); } temp2->data = val; temp2->lchild=temp2->rchild = NULL; } else { temp2->rchild = (struct tnode*)malloc(sizeof(struct tnode));/ *inserts the newly created node as left child*/ temp2 = temp2->rchild; if(temp2 == NULL) { printf("Cannot allocate\n"); exit(0); } temp2->data = val; temp2->lchild=temp2->rchild = NULL; } } return(p); } void main() { struct tnode *root = NULL; int n,x; printf("Enter the number of nodes in the tree\n"); scanf("%d",&n); while( n - > 0) { printf("Enter the data value\n"); scanf("%d",&x); root = insert(root,x); } printf("The created tree is :\n"); inorder1(root); printf("\n Enter the value of the node to be deleted\n"); scanf("%d",&n); root=delete(root,n); printf("The tree after deletion is \n"); inorder1(root); }
Explanation
This program first creates a binary tree with a specified
number of nodes with their respective data values. It then takes the data value
of the node to be deleted, obtains a pointer to the node containing that data
value, and obtains another pointer to the root of the node to be deleted.
Depending on whether the node to be deleted is a root node, a node with two
children a node with only one child, or a node with no children, it carries out
the manipulations as discussed in the section on deleting a node. After deleting
the specified node, it returns the pointer to the root of the tree.
-
Input: 1. The number of nodes that the tree to be created should have
2. The data values of each node in the tree to be created
3. The data value in the node to be deleted -
Output: 1. The data values of the nodes in the tree in inorder before deletion
2. The data values of the nodes in the tree in inorder after deletion
No comments:
Post a Comment