Освобождение памяти, выделенной для Дерева - C

Question

У меня есть дерево, определенное как,

struct tree {
    char label[MAX_LENGTH];
    char value[MAX_LENGTH];
    struct tree *child;
    struct tree *next;
};

Теперь мне нужно освободить память, выделенную этим деревом. Я написал следующий код.

unsigned int tree_free(struct tree *root)
{
    struct tree *current = NULL, *next = NULL, *child = NULL;
    unsigned int freecnt = 0;

    current = root;
    while(current != NULL)
    {
        next = current->next;
        child = current->child;      
        xfree(current);
        freecnt += tree_free(child) + 1;
        current = next;
    }
    return freecnt;
}

Этот метод возвращает количество освобожденных элементов, чтобы я мог проверить его по количеству выделенных ресурсов. Этот код работает. Но я не уверен, что это правильный способ ведения дел.

Это реализация дерева суффиксов. Для элементов s, stack, over, overflow, stackoverflow дерево будет выглядеть так:

root
-s
--stack
---stackoverflow
-over
--overflow

Любые предложения по улучшению кода приветствуются.

Answer 1

Если вам нужно освободить дерево, вам нужно пройтись по нему, поэтому я думаю, что код правильный.Я бы сделал это так же (рекурсивно пройтись по дереву, освободив объекты по пути).Единственное, что я хотел бы сделать по-другому, - запустить xfree после рекурсии (т. Е. Поменять местами xfree(current); и freecnt += tree_free(child) + 1;).Потому что теперь вы удаляете узел перед удалением его дочернего элемента, но я чувствую, что было бы лучше удалить дочерний элемент перед удалением родительского элемента.

Кроме того, вы можете избавиться от переменной child при использованииэто только один раз, с реальной потребностью.Сэкономит вам sizeof(pointer) стекового пространства на одну рекурсию; -)

Answer 2

Это довольно хорошее решение.Вы используете рекурсию для детей (которая не будет слишком глубокой), но итерацию для братьев и сестер (которая будет углубляться, если вы используете рекурсию).Ваш код, безусловно, может быть более элегантным в качестве рекурсивного решения (вызов tree_free для child и next), но риск переполнения стека будет значительно увеличен, поэтому я думаю, что вы сделали правильный выбор там.

Сказав это, вам вообще не понадобится child, если вы измените порядок своих операций:

unsigned int tree_free (struct tree *root) {
    struct tree *current = NULL, *next = NULL;
    unsigned int freecnt = 0;

    current = root;
    while(current != NULL)
    {
        freecnt += tree_free (current->child) + 1;
        next = current->next;
        xfree (current);
        current = next;
    }
    return freecnt;
}

Если вы считаете, что длина вашего списка братьев и сестер не будетнастолько большой, что вы могли бы попробовать элегантное решение:

unsigned int tree_free (struct tree *root) {
    unsigned int freecnt;

    if (root == NULL) return 0;
    freecnt = tree_free (root->child) + tree_free (root->next);
    xfree (root);
    return freecnt + 1;
}

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