如何在自引用 linq 中获取针对高度父级的极端叶节点

Question

我有数据结构

-Emp1 - Emp1_1 - Emp1_1_1
               - Emp1_1_2
      - Emp1_2 - Emp1_2_1
               - Emp1_2_2
-Emp2 - Emp2_1 - Emp2_1_1
               - Emp2_1_2
      - Emp2_2 - Emp2_2_1
               - Emp2_2_2

我想要一个字典，它将极端叶节点作为键，将其最高父节点作为值。操作：

（Emp1_1_1，Emp1）（Emp1_1_2，Emp1）（Emp1_2_1，emp1）（Emp1_2_2，Emp1）（Emp2_1_1，Emp2）（Emp2_1_2，Emp2）（Emp2_2_1，Emp2）（Emp2_2_2，Emp2）

(Emp1_1_1, Emp1)
(Emp1_1_2, Emp1) 
(Emp1_2_1, Emp1)
(Emp1_2_2, Emp1)
(Emp2_1_1, Emp2)
(Emp2_1_2, Emp2)
(Emp2_2_1, Emp2)
(Emp2_2_2, Emp2)

下面是 c# 代码

public class Program
    {
        public static void Main()
        {
            var program = new Program();
            var empList = program.GetData();
           //Some linq which return the expected dictionary.
            Console.WriteLine("Press any key to exit");
            Console.ReadKey();
        }
        public class Employee
        {
            public int Id { get; set; }
            public string Name { get; set; }
            public int parentEmployee { get; set; }
            public List<Employee> childList { get; set; }
        }
        List<Employee> GetData()
        {
            var empList = new List<Employee>();
            var emp1 = new Employee() { Id = 1, Name = "Emp1_Name", childList = new List<Employee>() };
            var emp1_1 = new Employee() { Id = 2, Name = "Emp1_1_Name", parentEmployee = emp1.Id, childList = new List<Employee>() };
            var emp1_2 = new Employee() { Id = 3, Name = "Emp1_2_Name", parentEmployee = emp1.Id, childList = new List<Employee>() };
            emp1.childList.Add(emp1_1);
            emp1.childList.Add(emp1_2);
            var emp1_1_1 = new Employee() { Id = 4, Name = "Emp1_1_1_Name", parentEmployee = emp1_1.Id };
            var emp1_1_2 = new Employee() { Id = 5, Name = "Emp1_1_2_Name", parentEmployee = emp1_1.Id };
            emp1_1.childList.Add(emp1_1_1);
            emp1_1.childList.Add(emp1_1_2);
            var emp1_2_1 = new Employee() { Id = 6, Name = "Emp1_2_1_Name", parentEmployee = emp1_2.Id };
            var emp1_2_2 = new Employee() { Id = 7, Name = "Emp1_2_2_Name", parentEmployee = emp1_2.Id };
            emp1_2.childList.Add(emp1_2_1);
            emp1_2.childList.Add(emp1_2_2);

            var emp2 = new Employee() { Id = 1, Name = "emp2_Name", childList = new List<Employee>() };
            var emp2_1 = new Employee() { Id = 2, Name = "emp2_1_Name", parentEmployee = emp2.Id, childList = new List<Employee>() };
            var emp2_2 = new Employee() { Id = 3, Name = "emp2_2_Name", parentEmployee = emp2.Id, childList = new List<Employee>() };
            emp2.childList.Add(emp2_1);
            emp2.childList.Add(emp2_2);
            var emp2_1_1 = new Employee() { Id = 4, Name = "emp2_1_1_Name", parentEmployee = emp2_1.Id };
            var emp2_1_2 = new Employee() { Id = 5, Name = "emp2_1_2_Name", parentEmployee = emp2_1.Id };
            emp2_1.childList.Add(emp2_1_1);
            emp2_1.childList.Add(emp2_1_2);
            var emp2_2_1 = new Employee() { Id = 6, Name = "emp2_2_1_Name", parentEmployee = emp2_2.Id };
            var emp2_2_2 = new Employee() { Id = 7, Name = "emp2_2_2_Name", parentEmployee = emp2_2.Id };
            emp2_2.childList.Add(emp2_2_1);
            emp2_2.childList.Add(emp2_2_2);
            empList.Add(emp1);
            empList.Add(emp2);
            return empList;
        }
    }

我尝试了一些解决方案，例如在linq中调用私有自引用函数，但它适用于单亲一子关系。

Answer 1

如果使用递归函数是可以接受的：

        Func<IEnumerable<Employee>, IEnumerable<Employee>> flatten = null;
        flatten = (IEnumerable<Employee> employees) => 
            employees.SelectMany(c => c.childList != null ? flatten(c.childList) : Enumerable.Empty<Employee>()).Concat(employees);
        var dict = (
            from topNode in empList
                    from node in flatten(topNode.childList)
                    where node.childList == null || node.childList.Count == 0
                    select new KeyValuePair<string, string>(node.Name, topNode.Name)
            ).ToDictionary(kv => kv.Key, kv => kv.Value);

        foreach(var keyValuePair in dict)
        {
            Console.WriteLine($"Key={keyValuePair.Key}, Value={keyValuePair.Value}");
        }

这输出：

Key=Emp1_1_1_Name, Value=Emp1_Name
Key=Emp1_1_2_Name, Value=Emp1_Name
Key=Emp1_2_1_Name, Value=Emp1_Name
Key=Emp1_2_2_Name, Value=Emp1_Name
Key=emp2_1_1_Name, Value=emp2_Name
Key=emp2_1_2_Name, Value=emp2_Name
Key=emp2_2_1_Name, Value=emp2_Name
Key=emp2_2_2_Name, Value=emp2_Name

Answer 2

试试这个

public static void Main()
{
    var program = new Program();
    var empList = program.GetData();
    Func<IEnumerable<Employee>, Employee, Dictionary<Employee, Employee>> TreeToDict = null;
    TreeToDict = (employees, topParent) => 
    employees.SelectMany(e => 
                         {
                             if(e.childList != null)
                             {
                                 return TreeToDict(e.childList, topParent == null ? e : topParent);
                             }
                             else
                             {
                                 Dictionary<Employee, Employee> dict = new Dictionary<Employee, Employee>();
                                 dict.Add(e, topParent == null ? e : topParent);
                                 return dict;
                             }
                         }).ToDictionary(x => x.Key, x => x.Value);
    foreach(var emp in TreeToDict (empList, null))
    {
        Console.WriteLine("key : {0}, value {1}", emp.Key.Name, emp.Value.Name);
    }
}

结果

key : Emp1_1_1_Name, value Emp1_Name
key : Emp1_1_2_Name, value Emp1_Name
key : Emp1_2_1_Name, value Emp1_Name
key : Emp1_2_2_Name, value Emp1_Name
key : emp2_1_1_Name, value emp2_Name
key : emp2_1_2_Name, value emp2_Name
key : emp2_2_1_Name, value emp2_Name
key : emp2_2_2_Name, value emp2_Name