Tree Traversal - Найти между двумя листами

У меня есть карта сетевого узла, и мне нужно построить список узлов между двумя точками. Это звучало достаточно просто мне в первый, но ответ ускользает меня :(Tree Traversal - Найти между двумя листами

Учитывая (упрощенно) структура данных:

Id Name  LeftId RightId 
1  Skagway  3 
2  Klukwan  3 
3  Haines  2  4 
4  Juneau  3  5 
5  Petersburg 4  6 
6  Wrangell 5  7 
7  Kasaan  6  4 
8  Portage  4  6

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

Они хотели бы иметь возможность идентифицировать узлы, начиная с либо ветвь или листовой конец.

источник

2013-09-23 Dan Morphis

Это не дерево, это направленный (двоичный) граф. Дерево характеризуется как имеющий уникальный путь между любыми двумя узлами (или, альтернативно, без циклов), но есть два пути от 8 до 5: 8-4-5 и 8-6-5. Независимо от того, какой алгоритм вам нужен, это ** Первый поиск **. – amnn

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

источник

2013-09-23 19:11:30 netchkin

Tree Traversal - Найти между двумя листами

ответ

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