Не удается удалить двоичное дерево поиска - PullRequest
Новая
       6

Не удается удалить двоичное дерево поиска

0 голосов
/ 02 декабря 2018

У меня есть код C, который создает дерево AVL.Я создал все функции для создания дерева, но застрял на последнем шаге - удалении дерева.Функция просто не работает.Вот моя 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];

Итак, вы можете диагностировать проблему?Спасибо за помощь.

1 Ответ

0 голосов
/ 02 декабря 2018

В вашей функции 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().

...