Free структуры дерева с не рекурсивной функцией

Question

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

struct tree_suspects { 
    char **description; 
    struct tree_suspects *right_description; 
    struct tree_suspects *wrong_description; 
} 

.. и я хочу free каждый узел после выделения каждого из них с malloc.

Дерево должно выдерживать сотни узлов без проблем. Таким образом, использование рекурсивных функций было бы очень неэффективным для стека кадров, так есть ли какая-либо форма цикла или что-то, что позволило бы мне группировать все узлы в массиве? Рекурсия - единственный способ сделать это?

Answer 1

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

Вы уверены, что рекурсия - это проблема в любом случае? Несколько 100 узлов звучат совершенно нормально для меня с обычной рекурсией. В какой архитектуре вы работаете?

Если вы беспокоитесь о доступе к памяти, вы должны просто позаботиться о том, чтобы эти узлы и их данные были расположены в аналогичной памяти. Поскольку вы используете двоичное дерево, вы можете по крайней мере поместить дерево в массив (у этого есть накладные расходы не более n-1, учитывая n узлов в дереве). Я думаю, что оптимизация строк не требуется, но если вы тоже хотите это сделать, используйте, например, субиндексированные массивы символов.

Что касается расположения хранилища для древовидной структуры, сбалансированные деревья очень легко хранить (https://en.wikipedia.org/wiki/Binary_tree#Arrays). В этом случае следует избегать несбалансированных деревьев, я предлагаю нечто вроде красных черных деревьев, которые не так сложно реализовать.

Answer 2

с помощью рекурсивных функций будет очень неэффективно стек

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

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