Свести Дерево в массив

Question

Я ищу лучший способ поместить дерево в массив

Идея заключается в том, чтобы следовать этому принципу: Array Implementation of Trees но I'am застрял на том, чтобы знать, какие узлы являются дети и то, что узлы находятся на одном уровне, потому что я не использую двоичное дерево.

Возможно, мне придется хранить ASCII, но я не могу просто разрешить массивы из 256 указателей!

Любая идея приветствуется.

Целью этого является отправка массива (дерева) на мой графический процессор, а не использование структур.

Answer 1

Хорошо, вот моя идея converting tree into an array.

Возьмите массив размером MAX_VAL, который является общим числом узлов в дереве. Тип массива должен быть таким же, как у узла, но с одним дополнительным полем. Его значение индекса для его родителя. Таким образом вы храните каждый узел. Храните корневой узел в первой позиции. Скажите 1. Теперь дочерние узлы этого узла впоследствии сохраняются с дополнительным полем, хранящим 1 (так как это было там, где был сохранен корень).

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

Надеюсь, это поможет. :) :)

Answer 2

Списки Ahnentafel очень большие, если не близки к идеально сбалансированным. Я предполагаю, что ваше дерево не будет сбалансировано, поэтому преимущество неявных указателей родителя/ребенка перевешивает стоимость. Я никогда не видел ни двоичный список Ahnentafel, но я предполагаю, что это возможно (вы просили неявные уравнения?).

Не могли бы вы сохранить отсортированный список дочерних указателей для каждого узла (символ ASCII + указатель/индекс)? В этом случае было бы лучше, по мнению других, построить дерево с помощью указателей и позволить детям расти. Затем упакуйте все узлы в список: выполните заказ для размещения узлов, используйте префиксные суммы для их смещений в массиве, сохраните индексы позиции на каждом узле и, наконец, скопируйте дочерние списки в массив (заменив дочерние указатели на индексы списка можно сделать, следуя указателям и запросив индекс с предыдущего шага).

Перемещение к ребенку в CUDA не будет постоянным временем, но, поскольку заказ известен, вы можете использовать бинарный поиск, чтобы ускорить процесс.