c# - 如何在遍历树结构时匹配路径

Question

我有一个包含父项和子项的树状结构。 parent 可以拥有的 child 数量没有限制。树中的每个节点都有一些特定的属性集。

我有一个表示路径的类似结构的列表。路径中的每个节点都具有相同的属性集和一些特定的值。路径中的第一个节点始终与上述树的根节点相同。

我想从根开始遍历树，通过比较树上节点的属性和路径上节点的属性来检查路径是否存在于树中。同时记录满足匹配条件的TreeNodes。请注意，TreeNode 和 PathNode 是完全不同的类型，它们只是具有一些共同的属性，例如姓名、身份证、位置等

我能想到的最简单的方法是进行递归调用以遍历树的子级，并且对于树的每一层我比较路径中的下一个节点，但我不确定是否有任何简单的方法它。我将不得不在 C# 中实现它，因此是否有任何特定的结构或库可用于执行此操作。任何特定于语言的解决方案都会非常有用，否则我可以将它翻译成 C#，只需要了解它应该如何设计。

Answer 1

让我们抽象地解决这个问题。

路径是:

• 一个空路径，或者
• 路径片段(路径的头部)后跟路径(路径的尾部)

一棵树是:

• 一个节点后跟零个或多个树(子树)的列表。

请注意，在此定义中没有空树。你说总有根。

我们现在定义一个谓词“匹配”如下。

• 一个路径片段可以匹配一个树节点。如何匹配取决于您。
• 空路径匹配所有树。
• 假设我们有一个头后面跟着一个尾部，一个节点后面跟着 child 。当且仅当 (1) 头部与节点匹配，并且 (2) 尾部为空，或者存在至少一个与尾部匹配的子节点时，路径才与树匹配。

此草图应该足够详细，足以用您选择的语言编写实现。