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

Question

Учитывая древовидную (двоичную) структуру с глубиной N. Можно ли вычислить некоторый индекс поиска для отображения конечных узлов.

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

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

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

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

Answer 1

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

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

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

Answer 2

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

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

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

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