php - Tree Traversal - Find between two leaves

Question

I have a network node map, and I need to build a list of nodes between two points. It sounded simple enough to me at first, but the answer is eluding me :(

Given the (simplified) data structure of:

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

How do I build an algorithm (or can you suggest an algorithm) to build a traverse the nodes and build a list of all the nodes between two points? The tree is mostly linear, except in the few spots where its not.

They would like to be able to identify the nodes starting from either the branch or leaf end.

Answer 1

如果它是从一个节点到另一个节点的路径，我建议您在子树上使用 preorder 以及您希望路径记录的起始节点的根节点。更新：事实上，人工智能算法（和图中的搜索路径）也可能有用。例如，非常简单的 BFS 可能有用。