LinkBack URL
About LinkBacks
I have this program where in want to delete a node in a BST. But before i delete that node i must find its parent. Now what is happening currently is that i reach the parent but as i am in a recursive loop i am unable to figure out why the program does not terminate when i have found a parent.
[insert]Code:#include <stdio.h> #include <stdlib.h> struct node { struct node *left; int data; struct node *right; }; void insert(struct node **root, int data); void search(struct node** root, int data); struct node * searchloc(struct node **root, int data); void delete(struct node **root, int data); struct node * searchparent(struct node **root, struct node *temp); struct node * inorder(struct node *root, struct node *temp); int main(void) { //printf("\n %d", SIZE); struct node *root = NULL; int data; char ch; do { printf("\n Enter the data\n"); scanf("%d", &data); insert(&root, data); printf("\n Do you want to add more elements\n"); scanf("\n%c", &ch); }while(ch == 'y' || ch == 'Y'); printf("\n Do you want to search data"); scanf("\n %c", &ch); while(ch == 'y' || ch == 'Y') { printf("\n Enter the data to search in the BST"); scanf("\n %d", &data); search(&root, data); printf("\n Do you want to search data"); scanf("\n %c", &ch); } delete(&root, 8); return 0; } void delete(struct node **root, int data) { struct node *temp = NULL; struct node ** r; struct node *parent; struct node *insuc; r = root; // find where is the data that is get the address temp = searchloc(r, data); if(temp != NULL) printf("\n Location at which element was found is %p", temp); else { printf("\n The data that you tried to delete doesnt exist in the list"); return; } r = root; // get the parents address as well parent = searchparent(*r, temp); if(parent != NULL) printf("\n Location at which parent was found is %p", parent); // the location where the element has been found has no children // simply delete the element and move ahead if(temp->left == NULL && temp->right == NULL) { // set the pointer in the parent to null if(parent->left == temp) parent->left = NULL; else if (parent->right == temp) parent->right = NULL; free(temp); } // the location where the element has been found has one children // set the pointer in the parent to point to the child if(temp->left == NULL && temp->right != NULL) { if(parent->left == temp) parent->left = temp->right; else if(parent->right == temp) parent->right = temp->right; free(temp); return; } else if(temp->left != NULL && temp->right == NULL) { if(parent->left == temp) parent->left = temp->left; else if(parent->right == temp) parent->right = temp->left; free(temp); return; } // the location where the element has been found has two children // 1. Find the inorder successor // 2. Copy its data to the node being deleted // 3. The inorder successor will always have one or no child // which reduces the problem to deletion of a node with one or zero child if(temp->left != NULL && temp->right != NULL) { // find the location of the inorder successor insuc = inorder(root, temp); printf("\n Location of inorder successor is %p and its value is %d", insuc, insuc->data); } } struct node * inorder(struct node **root, struct node *temp) { int i = 0; if((*root) != NULL) { inorder((*root)->left, temp); if(temp->data == (*root)->data) { printf("\n %d", (*root)->data); ++ i; } // next time i come here with value of i being 1 i would have got the inorder successor else { if(i == 1) { return (*root); } else printf("\n Still searching"); } inorder((*root)->right, temp); } } struct node * searchparent(struct node *root, struct node *temp) { if(root->left != NULL && root->left == temp) { return root; } else if(root->left != NULL) { searchparent(root->left, temp); if(root->right != NULL) searchparent(root->right, temp); } if(root->right != NULL && root->right == temp) { return root; } else if(root->left != NULL) { searchparent(root->left, temp); if(root->right != NULL) searchparent(root->right, temp); } } struct node * searchloc(struct node **root, int data) { if((*root)->data == data) { printf("\n Data Found in the tree"); return (*root); } // search in the left of the root else if((*root)->data < data) { if((*root)->right != NULL) { searchloc(&(*root)->right, data); } else { printf("\n Data not in the tree"); return NULL; } } // search in the right of the root else if((*root)->data > data) { if((*root)->left != NULL) { searchloc(&(*root)->left, data); } else { printf("\n Data not in the tree"); return NULL; } } else { printf("\n Data does not exist in the tree"); return NULL; } } void search(struct node** root, int data) { if((*root)->data == data) { printf("\n Data Found in the tree"); return; } // search in the left of the root else if((*root)->data < data) { if((*root)->right != NULL) { search(&(*root)->right, data); } else { printf("\n Data not in the tree"); return; } } // search in the right of the root else if((*root)->data > data) { if((*root)->left != NULL) { search(&(*root)->left, data); } else { printf("\n Data not in the tree"); return; } } else { printf("\n Data does not exist in the tree"); return; } } void insert(struct node **root, int data) { struct node *temp; // check if its the first element that i am going to add if(*root == NULL) { *root = (struct node *) malloc(sizeof(struct node)); (*root)->left = NULL; (*root)->right = NULL; (*root)->data = data; return; } // this is not the first element // find its correct place in the tree // data is larger than root so put in the right else { if((*root)->data < data) { insert(&((*root)->right), data); } else if((*root)->data > data) { insert(&((*root)->left), data); } } }
Originally Posted by roaan 
