Итак, прежде чем читать некоторые основные концепции информатики.
- Бинарное дерево - это динамически размещаемая структура (обычно используется для упорядоченного хранения).
- Из-за своей природы обход бинарных деревьев обычно рекурсивен;
Это потому, что линейный обход (через цикл) не является естественным, когда есть два пути цикла.- Рекурсивный: это означает функцию, которая вызывает себя.
- В старомодных языках управление памятью требует ручного управления памятью.
- Руководство: означает, что вы должны сделать это самостоятельно.
- Когда вы выполняете ручное управление памятью, вам нужно попросить базовую систему освободить каждого члена дерева.
- Свободно: восстановить память в глобальных poos, чтобы ее можно было использовать повторно, и вам не хватит памяти.
- Освобождение: это делается путем вызова функции
free()
и передачи ей указателя, который вы хотите восстановить. - Указатель: это как виртуальная палка. В конце это память. Когда вы запрашиваете память, вам дается указатель (виртуальная флешка), который имеет память. Когда вы закончите, вы вернете указатель (виртуальная флешка).
Рекурсивное решение:
freeTree(Node* node)
{
freeTree(node->left);
freeTree(node->right);
free(node);
}
Проблема в том, что рекурсия означает, что вы неоднократно вызываете одну и ту же функцию. Это увеличивает стек. Растущий стек использует больше памяти. Причина, по которой вы освобождаете дерево, заключается в том, что вы хотите вернуть память, используя больше памяти, контрпродуктивно (даже если вы вернете оба бита памяти назад).
Напоследок вопрос:
Так что проблема заключается в преобразовании приведенной выше рекурсивной версии в линейное решение (чтобы вам не приходилось использовать память).
Дайте тип узла
typedef struct Node Node;
struct Node
{
Node* left;
Node* right;
};
Напишите функцию, чтобы освободить дерево этих узлов.
Ограничения:
- Не может использовать рекурсию (даже косвенно)
Невозможно выделить динамическое пространство для отслеживания.
Обратите внимание, что есть решение O (n)
Победитель:
- Лучшая сложность.
- Tie Break 1: Первая отправка
- Tie Break 2: Наименьшее количество персонажей.
источник
C99, 94, O (n)
Изменить: все, кажется, относятся к
struct Node
так же,Node
как если быtypedef
он это сделал, так что я тоже.это на самом деле мой первый C гольф. много сегфо.
в любом случае, это требует C99, потому что он использует объявление внутри первого оператора цикла for.
даже не используя
#define
!этот алгоритм работает, преобразовывая дерево так, чтобы у верхнего узла не было левого потомка, а затем удаляя его и переходя к правому потомку.
например, если мы начнем с дерева
алгоритм изменяет указатели так, что дерево будет
Теперь мы можем легко удалить самый верхний узел.
источник
C / C ++ / Objective-C 126 символов (включая обязательный завершающий перевод строки)
Не запускается за O (n) время. Но OP не требует этого, так что вот мое решение O (n 2 ).
Алгоритм: спуститься к листу от корня. Отпусти это. Повторяйте, пока нет листьев. Выпустить рут.
Ungolfed:
источник
с ++ 99 O (n)
Циклы здесь отлично подходят для цепочки по списку, но не для иерархии вверх и вниз. user300 справился с этим (я впечатлен), но код трудно читать.
Решение состоит в том, чтобы преобразовать дерево в список.
Хитрость заключается в том, чтобы сделать это одновременно с удалением узлов.
Версия для гольфа
Гольф Расширенный
источник
C, 150 байтов
Попробуйте это на JDoodle
источник