根据条件从二叉搜索树中删除元素

Question

我有一个存储文件名和上次访问日期的结构。

typedef struct sFile {
   int lastAccess;
   char name[50];
} File;

typedef struct sNode {
   File info;
   struct sNode* left;
   struct sNode* right;
} Node;

我编写了一个函数，该函数递归地删除访问日少于特定数量的文件。例如，调用此函数并传递10作为参数时，将删除所有访问天数小于10的文件。

但是，我在执行相同的过程时遇到问题并最终生成内存访问错误。

我相信我的插入和删除函数是正确的，但以防万一我将它们留在下面。

插入和删除函数：

void insert(Node **root, File value) {
   if(*root == NULL) {
      Node *celula = getNode();
      
      if(celula == NULL) {
         printf("\nERRO: Falha na alocacao de memoria. Encerrando programa.\n");
         exit(1);
      }

      celula->left = NULL;
      celula->right = NULL;
      celula->info = value;
      *root = celula ;
   } else {
      if(strcmp(value.name, (*root)->info.name) < 0) {
         insert(&(*root)->left, value);
      } else {
         insert(&(*root)->right, value);
      }
   }
};

Node* deleteNode(Node *root, char name[50]) {
    if (root == NULL)
        return root;
 
    if (strcmp(name, root->info.name) < 0)
        root->left = deleteNode(root->left, name);
 
    else if (strcmp(name, root->info.name) > 0)
        root->right = deleteNode(root->right, name);
 
    else {
        if (root->left == NULL) {
            Node *temp = root->right;
            free(root);
            return temp;
        }
        else if (root->right == NULL) {
            Node *temp = root->left;
            free(root);
            return temp;
        }
 
        Node *temp = minValueNode(root->right);
 
        root->info = temp->info;
 
        root->right = deleteNode(root->right, temp->info.name);
    }
    return root;
}

树木清洁功能：

Node* clear(Node *root, int date) {
   if(root == NULL) {
      return NULL;
   }

   if(root->info.lastAccess <= date) {
      root = deleteNode(root, (root)->info.name);
   }

   root = clear(root->left, date);
   root = clear(root->right, date);

   return root;
}

错误信息：

[1]    39970 segmentation fault (core dumped)  ./7.out

有谁知道可能导致此错误的原因以及我该如何解决？

Answer 1

我推荐运行 valgrind、gdb 等，尝试找出错误的确切位置，但如果没有这些信息，我可以在此处看到可能的 NULL 取消引用。

如果 root->left 和 root->right 均为 NULL，则 deleteNode 将 return NULL，然后通过对 [=14 的调用取消引用=].

看看插入 NULL 检查是否会使其不再出现段错误。

同样，这里无法判断这是否是导致它的原因，请同时提供其余代码以使其可运行，或调试它以找出导致段错误的行。

Answer 2

我找到了错误。感谢所有帮助过的人。

我将 NULL 返回到树的根，因此我丢失了所有树引用并因此执行了不正确的内存访问。我将清除功能更新为以下内容：

Node* clear(Node *root, int date) {
   if(root == NULL) {
      return NULL;
   }

   if(root->info.lastAccess <= date) {
      root = deleteNode(root, (root)->info.name);
   }

   root->left = clear(root->left, date);
   root->right = clear(root->right, date);

   return root;
}

根据条件从二叉搜索树中删除元素

Remove elements from a binary search tree based on a condition

c

recursion

data-structures

binary-search-tree

recursive-datastructures