Есть ли алгоритм обхода дерева с фиксированной памятью?

У меня есть первый узел дерева. Что-то вроде этого:Есть ли алгоритм обхода дерева с фиксированной памятью?

class TreeNode { 
    int uniqueValue; 
    List<TreeNode> children; 
}

Я хочу найти наиболее эффективный способ памяти для печати всех узлов дерева. Дерево может быть большим или ОЧЕНЬ БОЛЬШИМ. Он может быть глубоким или широким. Я знаю алгоритмы с рекурсией и со стеклом. Я хочу найти алгоритм, который использует память фиксированного объема независимо от размера графика.

Дерево не является бинарным!

источник

2013-12-07 dart

Каковы ограничения на временную сложность? Кроме того, можно добавить дополнительный указатель в класс TreeNode? –

Имеет ли значение вопрос? Можете ли вы добавить логический флаг на каждый узел, чтобы вы могли пометить его как напечатанный? Вам небезразлично, требуется ли время O (n^2)? Действительно ли дерево настолько глубокое, что обычная рекурсивная перемотка по глубине приведет к удалению стека? –

Если вы можете пересечь дерево на самый глубокий уровень, распечатайте узел и удалите его (!), А затем снова начните с вершины, у вас есть ужасно неэффективный алгоритм, но он не использует лишнюю память. Это интеллектуальное упражнение, или вы ищете полезный ответ? Если дерево вписывается в память, оно должно быть доступно для использования (стек не глубже, чем самый глубокий уровень дерева). – Floris

Нет такого алгоритма O (1). Использование памяти в худшем случае всегда O (N). Вы можете «обмануть», добавив поля для поддержки обхода непосредственно на узел графика. Таким образом, если вы можете загрузить график в память, вы можете пересечь его (с помощью BFS или DFS).

источник

2013-12-07 16:20:35 bobah

@MooingDuck, как? дерево не двоично, а не сбалансировано. – ile

@ile: вы наполовину правы, я сделал предположение. Любое N-арное дерево можно повторить с использованием O (max_depth) дополнительной памяти. –

@MooingDuck, однако, если дерево не сбалансировано, то O (n). – ile

Если дерево хранится в плоском кучеобразном потоке, таком как длинный список в скобках, для его перемещения требуется достаточно памяти для записи вашей позиции в потоке, которая принимает биты O (log (N)) ,

Конечно, как говорит Лиор, вы можете просто пройти сначала по нему, используя стек в битах O (log (N)).

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

источник

2013-12-07 22:01:00

Есть ли алгоритм обхода дерева с фиксированной памятью?

ответ

Смежные вопросы