Problem with pointers - remove element in a binary search tree

1

You are having some problem in passing the root pointer per parameter to the remove_node

This function is iterative, it has only one recursive call in the latter case. So you have to use two pointers. As we walk through the binary search tree until we find the element to be removed, let's keep the memory addresses of the current node ( current ) and the previous one ( previous ). But it is giving the root memory allocation error to the current pointer.

Thank you!

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

typedef struct Node{
 int data;
 struct Node* left;
 struct Node* right;    
}Node;    


Node* get_new_node(int data)
{
 Node* new_node = (Node *) malloc(sizeof(Node));
 new_node->data = data;
 new_node->left = new_node->right = NULL;
 return new_node;
}    


Node* insert(Node *root, int data)
{
 if(root == NULL){
     root = get_new_node(data);
 }else if(data <= root->data){
     root->left = insert(root->left, data);
 }else if(data > root->data){
     root->right = insert(root->right, data);
 }
 return root;
}

int get_min_value(Node *root)
{
 while(root->left != NULL)
    root = root->left;
 return root->data;
}

void remove_node(Node *root, int value)
{
 int is_remove_node_a_left_child;
 int value_min_tmp;
 Node* previous, current;
 Node* root_min_tmp;

 previous = NULL;
 current = root;

//finding the node to be removed
 while(value != current->data)
 {
    previous = current;
    if(value < current->data)
    {
        current = current->left;
        is_remove_node_a_left_child = 1;
    }else
    {
        current = current->right;
        is_remove_node_a_left_child = 0;
    }
 }
//current is now pointing to the node to be removed, and previous, to its parent

//cases:
 if((current->left == NULL) && (current->right == NULL))
 {//the remove node has no child
    if(is_remove_node_a_left_child == 1)
        previous->left = NULL;
    else
        previous->right = NULL;
    free(current);
 }else if((current->left == NULL) && (current->right != NULL))
 {//the remove node has only a right child
    if(is_remove_node_a_left_child == 1)
        previous->left = current->right;
    else
        previous->right = current->right;
    free(current);
 }else if((current->left != NULL) && (current->right == NULL))
 {//the remove node has only a left child
    if(is_remove_node_a_left_child == 1)
        previous->left = current->left;
    else
        previous->right = current->left;
    free(current);
 }else
 {//the remove node has a left and a right child
    value_min_tmp = get_min_value(current->right);
    remove_node(current->right, value_min_tmp);
    current->data = value_min_tmp;
 }

}


void show_bst_in_order(Node* root)
{
 if(root == NULL)
    return;
 show_bst_in_order(root->left);
 printf("%d ", root->data);
 show_bst_in_order(root->right);
}


int main(){
 int return_value;
 Node *root = NULL;

 root = insert(root, 10);
 root = insert(root, 3);
 root = insert(root, 1);
 root = insert(root, 7);
 root = insert(root, 19);
 root = insert(root, 25);
 root = insert(root, 30);
 root = insert(root, 6);
 root = insert(root, 4);

 printf("Binary search tree in order:\n");
 show_bst_in_order(root);
 printf("\n");

}
    
asked by anonymous 07.04.2018 / 23:35

1 answer

0

You have just declared the previous variable as a pointer. The current variable is of type struct Node. To declare the two variables as pointers do as follows.

void remove_node(Node* root, int value){
    ....

    Node* previous, *current; // <---------- Modifique aqui
    Node* root_min_tmp;
    previous = NULL;
    current =root;
    .....
}
    
08.04.2018 / 03:17