c# - GetAllNodes メソッドを実装して、すべてのノードのコレクションをレベル順で返すにはどうすればよいですか?

Question

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();
  }
}

Answer 1

この種のトラバーサルは、幅優先トラバーサルと呼ばれます。

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;
}

仕組み：次のツリーを検討してください

[角括弧] に含まれるキューと、結果に追加されるもの (括弧) を見てみましょう。

ループ前:

• root がキューに追加されます:[N0]

最初のループ:

• キューから削除された最初のアイテム:
• 結果に追加された最初のアイテム:(N0)
• のすべての子がN0キューに追加されます。[N1-1][N1-2]

2 番目のループ:

• N1-1キューから削除された最初のアイテム:[N1-2]
• 結果に追加された最初のアイテム:(N0)(N1-1)
• のすべての子がN1-1キューに追加されます。[N1-2][N2-1]

3 番目のループ:

• N1-2キューから削除された最初のアイテム:[N2-1]
• 結果に追加された最初のアイテム:(N0)(N1-1)(N1-2)
• のすべての子がN1-2キューに追加されます。[N2-1][N2-2][N2-3]

4 番目のループ:

• N2-1キューから削除された最初のアイテム:[N2-2][N2-3]
• 結果に追加された最初のアイテム:(N0)(N1-1)(N1-2)(N2-1)
• のすべての子がN2-1キューに追加されます。[N2-2][N2-3][N3-1]

これらのアイテムはすべて子を持たないため、さらにループするとキューから 1 つずつ削除され、結果に追加されるだけです。