在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'关键字和委托来创建类似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);
}

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

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