如何压平树形结构

Question

我有一个嵌套列表，其中包含

public class Person
{
    public Person(string name)
    {
        this.Name = name;
    }

    public string Name { get; set; }

    public List<Person> Childs { get; set; }
}

列表可以像这样使用：

var Persons = new List<Person>();
Persons.Add(new Person("Eric"));
Persons[0].Childs = new List<Person>();
Persons[0].Childs.Add(new Person("Tom"));
Persons[0].Childs.Add(new Person("John"));
Persons[0].Childs[0].Childs = new List<Person>();
Persons[0].Childs[0].Childs.Add(new Person("Bill"));
Persons.Add(new Person("John");

如何将这个树形结构扁平化（将所有节点、子节点和子子节点放在一个列表中），例如，我想在同一级别上显示所有子节点和父节点，并带有级别参数。也就是说：

之前：

-Eric
    -Tom
    -John
        -Bill

What I want:

-Eric, Level1
-Tom, Level2
-John, Level2
-Bill, Level3

- Bob

---

为什么嵌套的for循环对你没起作用？你可能想尝试使用递归，但我认为现在保持简单，专注于一些for循环可能更好。请注意，不要改变原文意思。 - TheGeneral

Answer 1

递归方法的完美应用场景。

public static void DisplayPerson(List<Person> persons, int level = 0)
{
    if (persons != null)
    {
        level++;
        foreach (Person item in persons)
        {
            Console.WriteLine("-" + item.Name + ", Level" + level); 
            DisplayPerson(item.Childs, level);
        }
    }
}

https://dotnetfiddle.net/2J9F5K

- fubo

---

在这种情况下使用递归方法可能会导致溢出。对于这些情况，请改用Stack。 - Mikael Dúi Bolinder

Answer 2

Stack类是一个非常适合的使用场景。

public static void DisplayPerson(List<Person> persons)
{
    if (persons != null)
    {
        Stack<Person> personStack = new Stack<Person>();
        int level = 1;
        persons.ForEach(personStack.Push);
        while (personStack.Count > 0)
        {
            Person item = personStack.Pop();
            Console.WriteLine("-" + item.Name + ", Level:" + level); 
            if (item.Childs != null)
            {
                item.Childs.ForEach(personStack.Push);
                level++;
            }
        }
    }
}

https://dotnetfiddle.net/eD2GmY

---

在C#中，使用堆栈（Stack）比递归方法更快，占用的内存也更少，而且可以避免由于像@fubo答案中使用的递归C#方法导致的堆栈溢出问题。

递归方法只应该递归一两次。对于像这样可能有数千个项目的用例，应该使用Stack。

最初的回答：https://dev59.com/HXRB5IYBdhLWcg3w26x3#23349238

- Mikael Dúi Bolinder

Answer 3

非常简短的代码，可以将树形结构展平而不改变原始模型：

  static void Main(string[] args)
{
    var flattedTree=new List<Person>();
    var Persons = new List<Person>();
    Persons.Add(new Person("Eric"));
    Persons[0].Childs = new List<Person>();
    Persons[0].Childs.Add(new Person("Tom"));
    Persons[0].Childs.Add(new Person("John"));
    Persons[0].Childs[0].Childs = new List<Person>();
    Persons[0].Childs[0].Childs.Add(new Person("Bill"));
    Persons.Add(new Person("John"));
    Flatten(Persons, flattedTree);
    //flattedTree variable is the flatted model of tree.
}
 static void Flatten(List<Person> nodes, List<Person> flattedNodes)
        {
            foreach (var node in nodes)
            {
                flattedNodes.Add(node);
                if (node.Childs?.Count > 0)
                    Flatten(node.Childs, flattedNodes);
            }
        }

- Mohammad Niazmand