指针设置为NULL，但不在调试器中

Question

所以我正在AVL树上工作，但是我似乎无法使delete函数正常工作或释放树的权利。每次都会有delete功能段错误，但是在调试器中时free功能段错误。这是gdb的堆栈跟踪：

#0  0x00007fffd935a87a in msvcrt!_memicmp_l () from C:\WINDOWS\System32\msvcrt.dll
#1  0x0000000000402811 in isPresentRecurs (root=0xb756d0, searchedValue=0xb795b0 "aaa", found=0x61fcec) at ../.source/binTree.c:206
#2  0x00000000004027d6 in isPresent (root=0xb756d0, searchKey=0xb795b0 "aaa") at ../.source/binTree.c:200
#3  0x0000000000401c3d in main () at test.c:110

在我的测试中，我检查根目录是否已设置为NULL或将其密钥设置为null，通常运行if会完成if但在gdb中运行代码不会完成，而是进入else语句：

    if(tree->root->key==NULL||tree->root==NULL) printf("Tree has been freed successfully\n");
    else printf("Failed to free tree \n");

尝试访问失败的根将产生：

(gdb) print *(Node *)tree->root
$2 = {key = 0xfeeefeeefeeefeee <error: Cannot access memory at address 0xfeeefeeefeeefeee>, value = {data = 0xfeeefeeefeeefeee,
    type = (CHARACTER | unknown: 4277075692)}, height = -17891602, left = 0xfeeefeeefeeefeee, right = 0xfeeefeeefeeefeee}

这是我的结构定义：

typedef struct Node{
    char* key;
    Var value;

    int height;
    struct Node *left;
    struct Node *right;
}Node;

typedef struct binTree{
    Node *root;
    unsigned int nodeCount;
}binTree;

typedef enum TYPE {INTEGER, FLOAT, CHARACTER} TYPE;

typedef union {
    float fData;
    int iData;
    char cData;
} varData;

typedef struct Var{
    varData * data;
    TYPE type;
} Var;

//only used for flattening a tree into an array, as an intermediate representation
typedef struct VDContainer{
    Var var;
    char * varName;
} VDC ;

树初始化

binTree* createNewTree(){
    binTree *t = (binTree *) malloc(sizeof(binTree));
    t->root = NULL;
    return t;
}

这是我的删除功能：

void freeTree(Node* node){
    if (!node) return;
    freeTree(node->left);
    freeTree(node->right);
    freeNode(node);
}
void freeNode(Node *node){
    free(node->value.data);
    node->value.data = NULL;
    free(node->key);
    node->key = NULL;
    free(node);
    node = NULL;
}

插入：

Node* insert(Node *node, char *key,Var value){
    if (!node) return newNode(key,value);
    if ( strcasecmp(key ,node->key)<0) node->left = insert(node->left, key,value);
    else if (strcasecmp(key ,node->key)>0) node->right = insert(node->right, key,value);
    else if(strcasecmp(key,node->key)==0){
        if(memcmp(&value.data,&node->value,sizeof(Var))!=0){
            memcpy(&node->value,&value,sizeof(Var));
        }
        return node;
    };

    node->height = max(height(node->left),height(node->right))+1;

    int balance = getBalance(node);

    // Left Left Case
    if (balance > 1 && strcasecmp(key, node->left->key)<0)
        return rightRotate(node);

    // Right Right Case
    if (balance < -1 && strcasecmp(key, node->right->key)>0)
        return leftRotate(node);

    // Left Right Case
    if (balance > 1 && strcasecmp(key, node->left->key)>0){
        node->left =  leftRotate(node->left);
        return rightRotate(node);
    }

    // Right Left Case
    if (balance < -1 && strcasecmp(key,node->right->key)<0){
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }

    return node;
}

Node *rightRotate(Node *n){
    Node *leftNode = (Node*)n->left;
    if(!leftNode) return n;
    Node *rightOfLeft = (Node*)leftNode->right;

    leftNode->right = n;
    n->left = rightOfLeft;

    n->height = max(height(n->left), height(n->right)) + 1;
    leftNode->height = max(height(leftNode->left), height(leftNode->right)) + 1;

    return leftNode;
}

Node *leftRotate(Node *n){
     Node *rightNode =(Node*) n->right;
     if(!rightNode) return n;
     Node *leftOfright = (Node*)rightNode->left;

    rightNode->left = n;
    n->right = leftOfright;

    n->height = max(height(n->left), height(n->right)) + 1;
    rightNode->height = max(height(rightNode->left), height(rightNode->right)) + 1;

    return rightNode;
}

int height(Node *node){
    if (!node) return 0;
    return node->height;
}

int getBalance(Node *N){
    if (N == NULL) return 0;
    return height(N->left) - height(N->right);
}

删除节点：

Node* Delete(Node* root,char *key) {
    if (root==NULL) return root;
    else if (strcasecmp(key ,root->key)>0)      root->left = (Node*)Delete(root->left,key);
    else if (strcasecmp(key ,root->key)<0)      root->right = (Node*)Delete(root->right,key);
    else {
        if(root->right==NULL && root->left==NULL) {
            free(root);
            root = NULL;
        }
        else if(root->left!=NULL && root->right==NULL) {
            Node* temp = root->left;
            root = root->left;
            freeNode(temp);
        }
        else if(root->right!=NULL && root->left==NULL) {
            Node* temp = root->right;
            root = root->right;
            freeNode(temp);
        }
        else {
            Node* temp = minValueNode(root->right);
            root->key= temp->key;
            root->value = temp->value;
            root->right = Delete(root->right,temp->key);
        }
    }
    if(root==NULL) return root;

    root->height = 1 + max(height(root->left),height(root->right));
    int balance = getBalance(root);

    //Left Left Case
    if(balance > 1 && getBalance(root->left) >=0)   return rightRotate(root);

    // Right Right Case
    if(balance < -1 && getBalance(root->right) <=0) return leftRotate(root);

    // Left Right Case
    if(balance > 1 && getBalance(root->left) < 0)   {
        root->left = leftRotate(root->left);
        return rightRotate(root);
    }

    //Right Left Case
    if(balance < -1 && getBalance(root->right) > 0) {
        root->right = rightRotate(root->right);
        return leftRotate(root);
    }
    return root;
}

[link to complete source code and test code here导航至binTr / Tests并运行run.bat或gcc -g test.c ../.source/binTree.c

Answer 1

此行的测试方法错误：

if(tree->root->key==NULL||tree->root==NULL)

应该是：

if( tree->root==NULL || tree->root->key==NULL )

第一个错误，因为||是从左到右执行的，如果tree->root为NULL，则第一个将取消引用空指针，从而导致未定义的行为。它可以表现为优化器删除了无效代码（例如|| tree->root==NULL可以删除，因为它无法访问），这会使调试器感到困惑。

（也许还有其他问题，但是这个问题对我来说很突出；如果您仍然遇到问题，请尝试构建一个Minimal Reproducible Example）