时间戳

首页 > 解决方案 > 无法删除二叉搜索树

c - 无法删除二叉搜索树

问题描述

我有一个创建 AVL 树的 C 代码。我已经编写了所有函数来创建一棵树，但我停留在最后一步，即移除树。该功能根本不起作用。这是我的tree_free功能；

void tree_free(TREE tree){
 
     if (tree != NULL){
        tree_free(tree->root->right);
        free(tree->root->data); 
        tree_free(tree->root->left);
        free(tree);
     }

}

因此，对于那些想要查看插入函数和结构的人，我将在下面分享这些函数的代码。

这是我在树中插入数字的方法；

void avl_insert(TREE tree, unsigned long long data){


    tree->root = avl_insert_recursive(tree->root, data);

}

这是avl_insert_recursive功能；

NODE avl_insert_recursive(NODE node, unsigned long long data){

    int balance = 0;


    if( node == NULL){
    
        return(node_init(data));
    }
    
    if( data < node->data ){
    
    
        node->left = avl_insert_recursive(node->left, data);
        return node;
    
    
    }else if( data > node->data){
    
        
        node->right = avl_insert_recursive(node->right, data);
        return node;

    
    }else{
    
        return node;
    }

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

    return node;

}

最后，我想与您分享我为TREE和NODE数据类型创建的结构。

typedef struct NODE_s *NODE;
typedef struct NODE_s
{
    NODE right;
    NODE left;
    unsigned long long data;
    int height;
} NODE_t[1];

typedef struct TREE_s *TREE;
typedef struct TREE_s
{
    NODE root;
} TREE_t[1];

那么你能诊断出问题吗？谢谢您的帮助。

标签： csortingdata-structuresbinary-search-tree

解决方案

在你的tree_free()函数中，你有这个：free(tree->root->data);. 但tree->root->data不是指向您先前分配的内存的指针。你的编译器应该已经警告你了。

此外，您的avl_insert_recursive()功能似乎是错误的。有一条永远无法到达的代码路径：height由于 if else 块，永远不会更新。此外，node->data永远不会被设置。

我还建议更改avl_insert_recursive()签名。它不应接受指向已为节点分配的内存的指针，而应接受指向根节点的指针，并分配和插入节点本身。这样，您可以free(tree->root->data);从tree_free().

推荐阅读