Не удалять узел с двумя дочерними элементами

Question

При удалении узла с двумя дочерними элементами из моего двоичного дерева из «продуктов» вместо замены корня, который нужно удалить с помощью самого правого предка левого ребенка, а затем удаления этого потомка, он просто просто заменяет значение этого корня в значении предков. Я назвал «free()» для этого предка, но это, похоже, не работает. Так что я остался с двумя узлами того же значения.

Мой код:

#include <stdio.h> 
#include <stdlib.h> 
//Structures 
typedef struct Node{ 
    void *dataPtr; 
    struct Node *left; 
    struct Node *right; 
}node; 

typedef struct Product 
{ 
    int ProductCode; 
    char ProductName[30]; 
    int QuantityOnHand; 
    double ProductCost; 
    double ProductRetail; 
    char ProductLocationCode[7]; 
}product; 

//functions 

int compareID(void *ptr1, void *ptr2) 
{ 
    int temp; 

    if (((product *)ptr1)->ProductCode > ((product *)ptr2)->ProductCode) 
     temp = 1; 
    else 
     if (((product *)ptr1)->ProductCode < ((product *)ptr2)->ProductCode) 
      temp = -1; 
     else 
      temp = 0; 
    return temp; 
} 

void insert(node ** root, node** val, int(*f)(void*,void*)){ 
    if (!(*root)) { 

     //initalize a temporary node 
     node *temp = NULL; 
     temp = (node *)malloc(sizeof(node)); 

     //make both right and left nodes for temp to be NULL 
     temp->left = NULL; 
     temp->right = NULL; 


     temp->dataPtr = (*val)->dataPtr;//store value you were looking for in temp 
     *root = temp;// root is now the temporary node 
     return;//end of function. 
    } 
    int result = f((*root)->dataPtr, (*val)->dataPtr); 

    if (result == 1) {//if the value is less than the current root node, go to the left connecting node 
     insert(&(*root)->left, &(*val), f); 
    } 
    else if (result == -1) {//if the value is more than the current root node, go to the right connecting node 
     insert(&(*root)->right, &(*val), f); 
    } 
} 

struct Node* deleteNode(struct Node *root, void *ptr, int(*cptr)(void*, void*)) 
{ 
    struct Node *temp; 

    if (cptr(ptr, root->dataPtr) == 0) 
    { 
     if (root->left == NULL && root->right == NULL)//no children 
     { 
      free(root); 
      return NULL; 
     } 
     if (root->left != NULL && root->right == NULL)//left child 
     { 
      temp = root->left; 
      free(root); 
      return temp; 
     } 
     if (root->left == NULL && root->right != NULL)//right child 
     { 
      temp = root->right; 
      free(root); 
      return temp; 
     } 
     else //two children 
     { 
      struct Node* pred = root->left;//go left one of the node you're trying to delete 
      while (pred->right != NULL){//now get further right ancestor of that node 
       pred = pred->right; 
      } 

      root->dataPtr = pred->dataPtr; //make the original node the value of that right ancestor 
      return pred;//return that ancestor to delete it 

     } 
    } 
    else 
    { 
     int val = cptr(ptr, root->dataPtr); 
     if (val < 0) 
     { 
      root->left = deleteNode(root->left, ptr, cptr); 
      return root; 
     } 
     else 
     { 
      root->right = deleteNode(root->right, ptr, cptr); 
      return root; 
     } 
    } 

} 

void readData(struct Node** vptr, FILE *fp){ 
    product* ptr = (product *)malloc(sizeof(product)); 
    if (fp == stdin){ 
     printf("Enter Product Code: "); 
     fscanf(fp, "%d", &(ptr->ProductCode)); 
     fflush(stdin); 

     printf("Enter Name: "); 
     fscanf(fp, "%30[^\n]", ptr->ProductName); 
     fflush(stdin); 

     printf("Enter Quantity: "); 
     fscanf(fp, "%d", &(ptr->QuantityOnHand)); 

     printf("Enter Cost: "); 
     fscanf(fp, "%lf", &(ptr->ProductCost)); 
     fflush(stdin); 

     ptr->ProductRetail = (ptr->ProductCost/0.7); 

     printf("Enter Location: "); 
     fscanf(fp, "%6[^\n]", &(ptr->ProductLocationCode)); 
     fflush(stdin); 
    } 
    else{ 

     fscanf(fp, "%d %29[^\n] %d %lf %6[^\n]", &(ptr->ProductCode), ptr->ProductName, &ptr->QuantityOnHand, &ptr->ProductCost, &ptr->ProductLocationCode); 
     ptr->ProductRetail = (ptr->ProductCost/0.7); 
    } 
    (*vptr)->dataPtr = ptr; 
} 


int main() 
{ 
    int i = 0; 
    struct Node *newNode, *temp; 
    struct Node *root = NULL; 
    int(*compPtr)(void *, void *) = compareID; 
    for(i; i < 3; i++){ 
     newNode = (struct Node *)malloc(sizeof(struct Node)); 
     newNode->left = newNode->right = NULL;// missing this operation. 
     readData(&newNode, stdin); // this function call was missing. 
     insert(&root, &newNode, compPtr); 
    } 

    temp = (struct Node *)malloc(sizeof(struct Node)); 
    temp->dataPtr = malloc(sizeof(struct Product)); 

    printf("enter the product ID to delete : "); 
    fflush(stdin); 
    scanf("%d", &((struct Product *)temp->dataPtr)->ProductCode); 

    deleteNode(root, temp->dataPtr, compPtr); 
    free(temp->dataPtr); 
    free(temp); 
    return 0; 
} 

Почему этот узел-предок не удалялся из памяти? Что я должен изменить, чтобы убедиться, что он удален?

Answer 1

Ваш вопрос и код сбивают с толку сначала, потому что вы используете слово «предок», когда имеете в виду «потомок». Ребенок-узлы являются потомками. Предки - это те, которые предшествуют.

Проблема заключается в том, что вы являетесь , возвращая потомком, а не удаляя его. Во всех остальных случаях вы удаляете корневой каталог и возвращаете новый узел. В случае возникновения проблем вы не удаляете какой-либо узел. Вместо этого вы возвращаете самого правого потомка левого ребенка. Код, который вызывает deleteNode, заменяет узел, который должен быть удален, с возвращаемым узлом.

В этом случае вам необходимо вернуть корень после удаления узла, значение которого заменило значение корня. Но прежде чем удалять этот узел-потомк, вам нужно удалить ссылку с родителя этого узла.

Я думаю, что код вы хотите:

//go left one of the node you're trying to delete 
struct Node* parent = root; 
struct Node* pred = root->left; 

//now get further right descendant of that node 
while (pred->right != NULL){ 
    parent = pred; 
    pred = pred->right; 
} 

//make the original node the value of that right descendant 
root->dataPtr = pred->dataPtr; 

// unlink that node from its parent 
if (parent == root) 
    parent->left = NULL; 
else 
    parent->right = NULL; 

free(pred); 
return root; //return the root node