Вычислить индекс для листьев в древовидной структуре

Данная древовидная структура с глубиной N. Возможно ли вычислить некоторый индекс поиска для отображения листовых узлов.Вычислить индекс для листьев в древовидной структуре

Каждый узел знает свой родительский элемент и его дочерние элементы (слева и справа), если это не лист.

Моя идея была чем-то вроде того, что rootnode является индексом 0, а затем слева: 1, слева: слева: 2, слева: слева: слева: 3, слева: влево: вправо: 4, влево: вправо: влево: 5, слева: справа: справа: 6, справа: 7, справа: слева: 8

Так что, учитывая листовой узел, как я могу вычислить индекс наиболее умный.

Другие решения также принимаются, если его умнее давать индексы листьев от 0,1 ... L, где L - количество листьев.

источник

2012-03-10 Poul K. Sørensen

Если вы хотите представить дерево в массиве, самым простым является получение слоев дерева по одному.

 0 
    /\ 
    / \ 
    1  2  [0, 1, 2, 3, 4, 5, 6] 
/\ /\ 
3 4 5 6

Таким образом, поиск родителя - это просто: (index-1)/2. И найти двух детей - всего лишь 2*index и 2*index + 1.

источник

2012-03-10 18:33:05

Мое дерево создано в extern lib. Он делает это рекурсивно, вычисляя левый, а затем правый. Затем я хочу вычислить карту для быстрого поиска листового узла. Поэтому, когда передается листовой узел, мне нужно найти его индекс, спросив, что его родители. Я хочу сделать это, потому что он быстрее выполняет итерацию N шагов над родителями узлов, чем перебирает все узлы в дереве, чтобы найти узел. Причина в том, что мне нужно сохранить дополнительную информацию, связанную с листовыми узлами, и я не могу расширить классы. –

Спасибо, я нуждался в такой идее –

В моей структуре дерева (Quadtree и Octree) Я использую двоичное представление индексов каждого узла. например 32 бит (для максимального уровня 32) для каждого измерения. Итак, я могу вычислить полный индекс (или путь) листа по формуле

path.x = (unsigned int) (leaf.position.x * pow (2,32));

leaf.position.x musst находиться в диапазоне от 0 ... 1

Единственное ограничение (я думаю) для этого метода является то, что данные, которые вы храните musst быть в определенном диапазоне, так что вы можете разделить его по размеру вашего района. Если это возможно для вашего использования, читайте больше на Simple and Efﬁcient Traversal Methods for Quadtrees and Octrees

источник

2012-03-10 19:23:12 Smittii

Я действительно думал использовать биты для пути, но мои деревья несколько глубже 32 бит. На данный момент я просто вычислил индекс от итерации слева сначала, а затем направо, и указав им индекс ++, когда достигнут новый лист. –

Вычислить индекс для листьев в древовидной структуре

ответ

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