广度优先遍历

广度优先遍历

广度优先搜索通常使用 队列 来实现，深度优先搜索使用 堆栈 。

Queue<Node> q = new Queue<Node>();q.Enqueue(root);while(q.Count > 0){    Node current = q.Dequeue();    if(current == null)        continue;    q.Enqueue(current.Left);    q.Enqueue(current.Right);    DoSomething(current);}

作为

null

出队后检查的替代方法，您可以在添加到队列之前进行检查。我没有编译代码，因此其中可能包含一些小错误。

---

与LINQ很好集成的更高级（但较慢）的版本：

public static IEnumerable<T> BreadthFirstTopDownTraversal<T>(T root, Func<T, IEnumerable<T>> children){    var q = new Queue<T>();    q.Enqueue(root);    while (q.Count > 0)    {        T current = q.Dequeue();        yield return current;        foreach (var child in children(current)) q.Enqueue(child);    }}

可以与以下

Children

属性一起使用

Node

：

IEnumerable<Node> Children { get { return new []{ Left, Right }.Where(x => x != null); } }

…

foreach(var node in BreadthFirstTopDownTraversal(root, node => node.Children)){   ...}