查找两个树结构 C# 之间的差异

Question

我需要一个函数来比较两个不同文件结构之间的差异以及 return 文件结构的差异。

我有一个 class，"Element" 具有属性 ID 和 Children，其中 ID 是一个字符串，而 Children 是元素的集合。

public class Element
{
  string ID { get; }
  IEnumerable<Element> Children { get; }
}

现在，假设我有以下元素结构：

Structure A                Structure B
  - Category 1              - Category 1
      - Child X                - Child X
      - Child Y                - Child Z
  - Category 2

我想要 return 一个结构，它告诉我哪些元素存在于结构 A 中，但在结构 B 中缺失，如下所示：

Structure Diff
  - Category 1
       - Child Y
  - Category 2

是否有使用 LINQ 或直接算法（假设树可以有很多级别）来执行此操作的简单方法。

Answer 1

是的，是的。您可以只比较两个包含文件路径的字符串枚举：

Category 1\
Category 1\Child X
Category 1\Child Y
Category 2\

Category 1\
Category 1\Child X
Category 1\Child Z

有了这两个可枚举项，您可以调用 Enumerable.Except 方法来保留第一个可枚举项中缺少第二个可枚举项的项目。

Answer 2

帮助您入门的实施示例（仅在一种情况下测试）：

internal class Program {
    private static void Main(string[] args) {
        var c1 = new Element[] {
            new Element() {ID = "Category 1", Children = new Element[] {
                new Element() {ID = "Child X" },
                new Element() {ID = "Child Y" }
            }},
            new Element() {ID = "Category 2",}
        };
        var c2 = new Element[] {
            new Element() {ID = "Category 1", Children = new Element[] {
                new Element() {ID = "Child X" },
                new Element() {ID = "Child Z" }
            }},                
        };

        var keys = new HashSet<string>(GetFlatKeys(c2));
        var result = FindDiff(c1, keys).ToArray();
        Console.WriteLine(result);            
    }

    private static IEnumerable<Element> FindDiff(Element[] source, HashSet<string> keys, string key = null) {
        if (source == null)
            yield break;
        foreach (var parent in source) {
            key += "|" + parent.ID;
            parent.Children = FindDiff(parent.Children, keys, key).ToArray();
            if (!keys.Contains(key) || (parent.Children != null && parent.Children.Length > 0)) {                   
                yield return parent;
            }
        }
    }

    private static IEnumerable<string> GetFlatKeys(IEnumerable<Element> source, string key = null) {
        if (source == null)
            yield break;
        foreach (var parent in source) {
            key += "|" + parent.ID;
            yield return key;
            foreach (var c in GetFlatKeys(parent.Children, key))
                yield return c;
        }
    }
}

如另一个答案所述，首先获取第二棵树中每个元素的简单键列表，然后根据该列表过滤掉第一棵树中的元素会更容易。

查找两个树结构 C# 之间的差异

Finding difference between two tree structures C#

c#

linq

tree