c - AVL树删除导致程序崩溃

所以我有C语言中的二进制搜索树的代码，对我来说很好用。但是，当我为BST删除添加代码时，我的程序在该删除过程中将崩溃。

它给我一个错误，提示访问冲突读取位置0x00000000。

我认为这与传递NULL指针有关。也许我在某个地方读到了它，或者那完全是错误的，我很傻。

无论如何，这是我删除AVL的代码。如果您能帮助我使程序正常运行并帮助我了解我做错了什么，我将非常感谢。我还将包括寻找最小节点的功能，因为我觉得这可能是罪魁祸首。

AVL min_node(AVL self)
{
    /*  A AVL node to keep track of the current node. */
    AVL current = self;


    /*  This loop finds the minimum node, by traversing the tree until the leftmost node is discovered. */
    while (!empty_tree(current))
    {
        current = current->left;
    }

    /*  Returns the tree.   */
    return current;
}



AVL delete(AVL self, long id)
{

    if (self != NULL)
    {
        if (id == self->student_id)
        {
            if (self->left != NULL)
            {
                AVL successor = min_node(self->right);
                self->student_id = successor->student_id;
                self->right = delete(self->right, self->student_id);
            }
            else
            {
                AVL to_free = self;
                if (self->left)
                {
                    self = self->left;
                }
                else
                {
                    self = self->right;
                }
                free(to_free);
            }
        }
        else if (id < self->student_id)
        {
            self->left = delete(self->left, id);
        }
        else
        {
            self->right = delete(self->right, id);
        }
    }

    /*NEW SHIT*/
    int balance = getBalance(self);

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

    return self;
}

更新：因此，似乎在删除功能的两行之一上崩溃了：

self->student_id = successor->student_id;

要么

AVL successor = min_node(self->right);

编辑2：应要求，我包括了我的整个avl.c文件。

#include <stdlib.h>
#include <stdbool.h>
#include "avl.h"

bool names_match(char* name_one, char* name_two)
{
    if (strcmp(name_one, name_two) == 0)
    {
        return true;
    }
    else
    {
        return false;
    }
}

bool empty_tree(AVL self)
{
    if (self == NULL)
    {
        return true;
    }
    else
    {
        return false;
    }
}


AVL leftRotate(AVL self)
{
    AVL y = self->right;
    AVL T2 = y->left;

    y->left = self;
    self->right = T2;

    return y;
}

AVL rotateRight(AVL self)
{
    AVL x = self->left;
    AVL T2 = x->right;

    x->right = self;
    self->left = T2;

    return x;
}

int getBalance(AVL node)
{
    if (node == NULL)
    {
        return 0;
    }
    return height(node->left) - height(node->right);
}


AVL insert(AVL self, long id)
{
    if (self == NULL)
    {
        self = (AVL)malloc(sizeof(struct avlNode));
        self->student_id = id;
        self->left = self->right = NULL;
    }
    else if (id < self->student_id)
    {
        self->left = insert(self->left, id);
    }
    else if (id > self->student_id)
    {
        self->right = insert(self->right, id);
    }


    /*NEW SHIT*/
    int balance = getBalance(self);

    //Left Left Case
    if (balance > 1 && id < self->left->student_id)
    {
        return rotateRight(self);
    }
    //Right Right Case
    if (balance < -1 && id > self->right->student_id)
    {
        return leftRotate(self);
    }
    //Left Right Case
    if (balance > 1 && id > self->left->student_id)
    {
        self->left = leftRotate(self->left);
        return rotateRight(self);
    }
    //Right Left Case
    if (balance < -1 && id < self->right->student_id)
    {
        self->right = rotateRight(self->right);
        return leftRotate(self);
    }

    //Return unchanged pointer (i dunno why. could probably be void)
    return self;
}

/*  === AVL MINIMUM NODE ===
Finds the minimum node in a AVL.
*/
AVL min_node(AVL self)
{
    /*  A AVL node to keep track of the current node. */
    AVL current = self;

    /*  This loop finds the minimum node, by traversing the tree until the leftmost node is discovered. */
    while (!empty_tree(current->left))
    {
        current = current->left;
    }

    /*  Returns the tree.   */
    return current;
}



AVL delete(AVL self, long id)
{
    if (self != NULL)
    {
        if (id == self->student_id)
        {
            if (self->left != NULL)
            {
                AVL successor = min_node(self->right);
                self->student_id = successor->student_id;
                self->right = delete(self->right, self->student_id);
            }
            else
            {
                AVL to_free = self;
                if (self->left)
                {
                    self = self->left;
                }
                else
                {
                    self = self->right;
                }
                free(to_free);
            }
        }
        else if (id < self->student_id)
        {
            self->left = delete(self->left, id);
        }
        else
        {
            self->right = delete(self->right, id);
        }
    }

    /*NEW SHIT*/
    if (self == NULL)
    {
        return self; //ADDED TODAY
    }

    int balance = getBalance(self);

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

    return self;
}

/*  === AVL NODE COUNT ===
Counts the number of nodes in the AVL.
*/
int number_of_nodes(AVL self)
{
    /*  If the tree is empty, return a count of 0 nodes.    */
    if (empty_tree(self))
    {
        return(0);
    }
    /*  If the tree is not empty, but its left and right nodes are, return a count of 1 node.   */
    else if (empty_tree(self->left) && empty_tree(self->right))
    {
        return(1);
    }

    /*  If the tree is not empty, and its left and right nodes are also not empty, run this function recursively in the left and right nodes.   */
    else
    {
        return(1 + (number_of_nodes(self->left) + number_of_nodes(self->right)));
    }

}

/*  === AVL HEIGHT ===
Returns the total height of a AVL.
*/
int height(AVL self)
{
    /*  If the tree is empty, return a count of 0 nodes.    */
    if (empty_tree(self))
    {
        return 0;
    }
    /*  If the tree is not empty, run this fucntion recursively on the left and right branches, returning the max of the two.   */
    else
    {
        return 1 + max(height(self->left), height(self->right));
    }
}



/*  === PRINT AVL ===
Prints a AVL in pre-order.
*/
void print_pre_order(AVL self)
{

    /*  If the tree isn't empty, print the node's ID and then run this function recursively on the left and then the right nodes,
    to print pre order. */
    if (!empty_tree(self))
    {
        printf("%d", self->student_id);
        printf("\n");
        print_pre_order(self->left);
        print_pre_order(self->right);

    }
}

/*  === SEARCH AVL ===
Searches a AVL for a particular node.
*/
bool searchTree(AVL self, long id)
{
    if (!empty_tree(self))
    {
        /*  If the node's ID matches the input ID, return true. */
        if (self->student_id == id)
        {
            return true;
        }

        /*  If the node's ID doesn't match the input ID, run this function recurseively on the appropriate node.    */
        else
        {
            if (self->student_id > id)
            {
                return searchTree(self->left, id);
            }
            else if (self->student_id < id)
            {
                return searchTree(self->right, id);
            }
        }
    }
    return false;
}

void destroy_tree(AVL self)
{
    /*  If the tree is not empty, free each node in the tree  by running this function recursively on the left and right branches.  */
    if (!empty_tree(self))
    {
        destroy_tree(self->left);
        destroy_tree(self->right);
        free(self);
    }
}

编辑3：有趣的发展。实际上，所使用的AVL树位于链接列表中，每个节点都包含一个AVL树。现在，我已经（通过大量测试）意识到，如果AVL树上的第一个节点已被构建，则可以将其删除。非常有趣，甚至更烦人。

最佳答案

我认为问题出在传递给函数的“自我->正确”。如果我假设“自我”是一个指针，那么在我看来，您应该像“＆（self-> right）”那样传递“自我”的“地址”，并应将当前值赋给'＆self'就像'current = * self'。然后我认为它可以工作。
我想我可以纠正我所说的话，如果我提供了完整的代码，但我想你的主旨是

关于c - AVL树删除导致程序崩溃，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/36820016/