广度优先遍历

一尘不染

广度优先遍历

algorithm

我试图解决一个面试问题，但为此，我必须逐级遍历二叉树。我设计了具有以下变量的BinaryNode

private object data;
private BinaryNode left;
private BinaryNode right;

有人可以帮我在BinarySearchTree类中编写BreadthFirstSearch方法吗？

更新：谢谢大家的投入。这就是面试的问题。“给定二叉搜索树，设计一种算法，该算法创建每个深度的所有节点的链表（即，如果您有深度为D的树，则将有D链表）”。

这是我的方法，请告诉我您的专家意见。

public List<LinkedList<BNode>> FindLevelLinkList(BNode root)
    {
        Queue<BNode> q = new Queue<BNode>();
        // List of all nodes starting from root.
        List<BNode> list = new List<BNode>();
        q.Enqueue(root);
        while (q.Count > 0)
        {
            BNode current = q.Dequeue();
            if (current == null)
                continue;
            q.Enqueue(current.Left);
            q.Enqueue(current.Right);
            list.Add(current);
        }

        // Add tree nodes of same depth into individual LinkedList. Then add all LinkedList into a List
        LinkedList<BNode> LL = new LinkedList<BNode>();
        List<LinkedList<BNode>> result = new List<LinkedList<BNode>>();
        LL.AddLast(root);
        int currentDepth = 0;
        foreach (BNode node in list)
        {
           if (node != root)
            {
                if (node.Depth == currentDepth)
                {
                    LL.AddLast(node);
                }
                else
                {
                    result.Add(LL);
                    LL = new LinkedList<BNode>();
                    LL.AddLast(node);
                    currentDepth++;
                }
            }
        }

        // Add the last linkedlist
        result.Add(LL);
        return result;
    }

阅读 185

2020-07-28

共1个答案

一尘不染

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

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))
{
   ...
}

2020-07-28