освобождение памяти двоичного дерева C - PullRequest
Новая
       2

освобождение памяти двоичного дерева C

4 голосов
/ 07 февраля 2012

Я хотел бы освободить память из моего выделенного двоичного дерева, какой обход лучше для этого сделать? 

typedef struct Node{
struct Node * right;
struct Node * left;
void * data;
}Node;


typedef int (*cmp) (void*,void *);


Node* init(void * element){
    Node * newNode=(Node*)malloc(sizeof(Node));
    newNode->data=element;
    newNode->left=NULL;
    newNode->right=NULL;
    return newNode; 
}

void  insert(void * element, Node** root,cmp compareTo){
    if(*root==NULL){
        *root=init(element);
        return;
    }
    if(compareTo(element,(*root)->data)==1)
        insert(element,&((*root)->left),compareTo);
    else
        insert(element,&((*root)->right),compareTo);
}

Ответы [ 5 ]

10 голосов
/ 07 февраля 2012

Поскольку это дерево, вы должны использовать рекурсивный подход. 

deallocate (node):
    //do nothing if passed a non-existent node
    if node is null
        return

    //now onto the recursion
    deallocate(left node)
    deallocate(right node)

    free node
9 голосов
/ 07 февраля 2012

Подумайте о том, что делают различные типы обхода, и имейте в виду, что после того, как вы освободите память, вам больше не разрешат доступ к ней:

  • Предзаказ: операция, выполняемая перед посещением детей
  • По порядку: операция, выполняемая после посещения левого поддерева, перед правым поддеревом
  • Postorder: операция выполняется после посещения всех поддеревьев

Учитывая вышеприведенные утверждения, ответ должен быть ясным.

4 голосов
/ 27 апреля 2016 
void free_tree(Node * node){
   //post-order like FatalError hinted at
       if (node != NULL) {
        free_tree(node->right);
        free(node->data); //if data was heap allocated, need to free it
        free_tree(node->left);
        free(node);
     }}

Отличный способ проверки ошибок сегментов и утечек памяти - использовать

valgrind --leak-check=full ./yourProgram

2 голосов
/ 07 февраля 2012

Первый поиск по глубине лучше всего подходит для этого

1 голос
/ 07 февраля 2012

Когда вы говорите «лучший», вы имеете в виду «правильный» (т. Е. Не вызовет ли хаос доступ к освобожденной памяти) или «самый эффективный» или что?

Что касается правильности: все, что выНапример, если вы позаботитесь о том, чтобы не получить доступ к данным после их освобожденияОчевидный простейший подход (о котором я не буду говорить явно, потому что это похоже на домашнюю работу :-), но это то, что вы бы сделали, если бы хотели написать как можно меньше кода [РЕДАКТИРОВАТЬ, чтобы добавить: это то, что опубликовал «cnicutar»;Я надеюсь, что это не домашняя работа, в конце концов!]) Просто отлично работает.

Вы можете получить более эффективные результаты (в пространстве или времени), если сопоставите порядок освобождения с порядком распределения, нодетали зависят от вашего распределителя памяти, и вам, вероятно, это не важно.

...