c# - 如何实现GetAllNodes方法以按级别顺序返回所有节点的集合？

public class TreeNode<T>
{
  private List<TreeNode<T>> _children = new List<TreeNode<T>>();
  public T Data { get; set; }
  public TreeNode<T> Parent { get; private set; }
  public ReadOnlyCollection<TreeNode<T>> Children {
    get {
      return new ReadOnlyCollection<TreeNode<T>>(_children);
    }
  }
  public void AddChild(TreeNode<T> child)
  {
    _children.Add(child);
  }
  public ICollection<TreeNode<T>> GetAllNodes()
  {
    throw new NotImplementedException();
  }
}

最佳答案

这种遍历称为Breadth-First Traversal：

public ICollection<TreeNode<T>> GetAllNodes()
{
    var allNodes = new List<TreeNode<T>>();
    var queue = new Queue<TreeNode<T>>();
    queue.Enqueue(this); // will include root node

    while (queue.Any())
    {
        var current = queue.Dequeue();
        allNodes.Add(current);
        foreach (var child in current._children)
            queue.Enqueue(child);
    }

    return allNodes;
}

工作原理：考虑以下树
让我们看看队列[方括号]将包含什么以及将添加到结果中的内容（括号）：
循环前：
根目录已添加到队列：[N0]
第一个循环：
从队列中删除的第一个项：
添加到结果的第一项：(N0)
N0的所有子项都添加到队列中：[N1-1][N1-2]
第二个循环：
从队列中移除的第一个项目：N1-1
添加到结果的第一项：[N1-2]
(N0)(N1-1)的所有子项都将添加到队列：N1-1
第三个循环：
从队列中移除的第一个项目：[N1-2][N2-1]
添加到结果的第一项：N1-2
[N2-1]的所有子项都将添加到队列：(N0)(N1-1)(N1-2)
第四个循环：
从队列中移除的第一个项目：N1-2
添加到结果的第一项：[N2-1][N2-2][N2-3]
N2-1的所有子项都将添加到队列：[N2-2][N2-3]
所有这些项都没有子项，因此进一步的循环将只从队列中逐个删除它们并添加到结果中。

关于c# - 如何实现GetAllNodes方法以按级别顺序返回所有节点的集合？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/18845756/