树遍历 - 查找两片叶子

我有一个网络节点图，我需要建立两点之间的节点列表。这听起来很简单对我来说是第一次，但得到的答复是躲避我:(树遍历 - 查找两片叶子

鉴于（简化）数据结构：

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

如果是从一个节点到另一个节点的路径，我建议您在子树上使用预定义，并在要开始记录路径的起始节点的根节点上进行。更新：实际上，人工智能算法（以及图中的搜索路径）也可能有用。例如，非常简单的BFS就可以使用。

来源

2013-09-23 19:11:30 netchkin

树遍历 - 查找两片叶子

回答

相关问题