c# - 在不使用 C# 中的递归的情况下展平本身具有 N 深度列表的列表项

Question

我要

在 C# 中对单个列表中的 N 个深度项进行排序。每个项目本身都有一个 N 深度列表。该模型如下所示。

TestModel model = new TestModel
        {
            Name = "Model",
            Nested = new List<TestModel>
            {
                new TestModel {
                    Name = "T1"
                },
                new TestModel {
                    Name = "T2"
                },
                new TestModel {
                    Name = "T3"
                },
                new TestModel {
                    Name = "T4-Nested01",
                    Nested = new List<TestModel> {
                        new TestModel {
                            Name = "T4-Nested01-T1",
                        },
                        new TestModel {
                            Name = "T4-Nested01-T2-Nested02",
                            Nested = new List<TestModel> {
                                new TestModel {
                                    Name = "T4-Nested01-T2-Nested02-T1-Nested03",
                                    Nested = new List<TestModel> {
                                        new TestModel {
                                            Name = "T4-Nested01-T2-Nested02-T1-Nested03-T1"
                                        },
                                        new TestModel {
                                            Name = "T4-Nested01-T2-Nested02-T1-Nested03-T2"
                                        },
                                        new TestModel {
                                            Name = "T4-Nested01-T2-Nested02-T1-Nested03-T3"
                                        }
                                    }
                                },
                                new TestModel {
                                    Name = "T4-Nested01-T2-Nested02-T2"                                        
                                },
                                new TestModel {
                                    Name = "T4-Nested01-T2-Nested02-T3"                                        
                                }
                            }
                        },
                        new TestModel {
                            Name = "Nested01-T2",
                        },
                        new TestModel {
                            Name = "Nested01-T3"
                        }
                    }
                }
            }
        };

        // model looks like this.
        // ㄴ Name = "Model"
        // ㄴ Nested Count 4
            // ㄴ [0] TestModel T1
            // ㄴ [1] TestModel T2
            // ㄴ [2] TestModel T3
            // ㄴ [3] TestModel T4
                // ㄴ Name = "T4-Nested01"
                // ㄴ Nested Count 4
                    // ㄴ [0] TestModel T4-Nested01-T1
                    // ㄴ [1] TestModel T4-Nested01-T2
                        // ㄴ Name = "T4-Nested01-T2-Nested02"
                        // ㄴ Nested Count 3
                            // [0] TestModel T4-Nested01-T2-Nested02-T1
                                // ㄴ Name = "T4-Nested01-T2-Nested02-T1-Nested03"
                                // ㄴ Nested Count 3
                                    // [0] TestModel T4-Nested01-T2-Nested02-T1-Nested03-T1
                                    // [1] TestModel T4-Nested01-T2-Nested02-T1-Nested03-T2
                                    // [2] TestModel T4-Nested01-T2-Nested02-T1-Nested03-T3
                                // [1] TestModel T4-Nested01-T2-Nested02-T2
                                // [2] TestModel T4-Nested01-T2-Nested02-T3
                    // ㄴ [2] TestModel
                    // ㄴ [3] TestModel

我需要

单个列表可以更轻松地通过排序列表中的某些属性搜索特定元素。我已经有一个递归算法来实现这个目标。但我想使用非递归解决方案。

问题

1. 我应该使用哪种非递归算法以获得最佳性能？
2. 我应该使用哪种数据结构来编写最简单的代码？

给我一​​个想法就足够了，或者如果你能为我调整一个替代算法，那也将不胜感激。

Answer 1

当你使用递归来迭代一个图时，看起来你没有使用任何数据结构来执行遍历，但你实际上是在使用一个隐式/固有的数据结构:Stack。因此，如果不使用递归执行相同类型的遍历，就需要堆栈。

在 C# 中，您可以使用 Stack、“yield return”关键字和委托(delegate)来创建类似 linq 的扩展方法，该方法将以非常方便且可重用的方式执行此图形遍历。实现的粗略概述如下:

public static IEnumerable<T> Flatten<T>(this T root, Func<T, IEnumerable<T>> selector)
{
    var stack = new Stack<T>();
    stack.Push(root);
    while(stack.Count > 0)
    {
        var current = stack.Pop();
        yield return current;
        foreach(var child in selector(current))
        {
            stack.Push(child);
        }
    }
}

你可以这样使用它:

foreach(var item in model.Flatten(t=>t.Nested))
{
    Console.WriteLine(item.Name);
}

您需要添加一些空检查和可选的检查以防止无限循环(如果您的图中的子项包含祖先，则该算法将陷入无限循环，而递归算法将堆栈溢出)

这种类型的图遍历称为“深度优先”。您可以通过简单地将堆栈换成队列来实现“广度优先”版本。