Есть ли способ получить доступ к неконцевым узлам в C++ Boost rtree?
Извините заранее, это очень специфический вопрос, и я не могу предоставить какой-либо фрагмент кода, так как это для моей работы, поэтому конфиденциально.
Я использую Boost R-деревья, и алгоритм, который мне нужно реализовать, требует доступа к неконцевым узлам дерева. С помощью библиотеки Boost rtree я могу легко получить доступ к конечным узлам. Я заметил, что есть функция для печати всех узлов, включая неконечные узлы (что означает, что они существуют, они вычисляются), с их положением, уровнем в дереве и т. Д., Но я не могу получить к ним доступ таким же образом, как лист узлы.
На данный момент лучшее решение, которое у меня есть, - реализовать посетитель для дерева и перегрузить оператор () для сбора узлов (это то, что метод print делает для доступа к узлам).
Мой вопрос: кто-нибудь знает более простой способ доступа к неконцевым узлам? Потому что этот не кажется эффективным, и я теряю время каждый раз, когда хочу получить доступ к неконечному узлу. Более того, мне нужно скопировать структуру дерева без точек, и я не могу этого сделать, если не могу получить доступ к неконцевым узлам.
Заранее спасибо!
0 ответов
Я не знаю, что бы вы хотели сделать, так что это будет общий ответ.
Для того, чтобы получить доступ к узлам дерева в первый раз, вы должны пройти через древовидную структуру. В Boost.Geometry для этого используется шаблон посетителей rtree. Вы можете сделать это вручную, но внутренне Boost.Variant используется для представления узлов, так что вместо этого вы получите вариант посетителя. На данный момент у вас есть несколько вариантов в зависимости от того, что вы собираетесь делать с узлами. Собираетесь ли вы изменить R-дерево? Будет ли дерево перенесено в память? Будут ли изменены адреса узлов? Сколько узлов вы собираетесь получить доступ? Вы хотите сохранить какую-то ссылку на узел и пересечь древовидную структуру с этой точки? Вы хотите пересечь структуру вниз или вверх?
Как вы заметили, один вариант - каждый раз обходить древовидную структуру. Это хороший подход, если древовидная структура может измениться. Очевидным недостатком является то, что вы должны проверять все дочерние узлы на каждом узле, используя некоторое условие (что бы вы ни делали, чтобы выбрать интересующий узел).
Если древовидная структура не изменяется, но дерево копируется в другое место в памяти, вы можете представить узел в виде пути от корня до интересующего узла в виде списка индексов дочерних узлов. Например, список {1, 2, 3} означает: пройдитесь по дереву, используя дочерний узел 1 корневого узла, затем на следующем уровне выберите дочерний узел 2, тогда ваш узел будет дочерним узлом 3 на следующем уровне. В этом случае вам все равно придется пройти по дереву, но не нужно снова проверять условия.
Если дерево не изменяется и узлы остаются в памяти в одном месте, вы можете просто использовать указатели или ссылки.