广度优先遍历

Question

广度优先遍历

50

我试图解决一道面试题，但需要逐层遍历二叉树。我已经设计了带有以下变量的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;
    }

- Pritam Karmakar

2

你目前尝试了什么？你能用简单易懂的英语解释一下算法应该做什么吗（例如给出伪代码）？ - David Weiser

5

好的，我会尽力进行翻译。以下是您需要翻译的内容：How 'bout due diligence on Wikipedia? http://en.wikipedia.org/wiki/Breadth-first_search - Kirk Woll

3个回答

13

var queue = new Queue<BinaryNode>();
queue.Enqueue(rootNode);

while(queue.Any())
{
  var currentNode = queue.Dequeue();
  if(currentNode.data == searchedData)
  {
    break;
  }

  if(currentNode.Left != null)
    queue.Enqueue(currentNode.Left);

  if(currentNode.Right != null)
    queue.Enqueue(currentNode.Right);
}

- Viacheslav Smityukh

这可能是一个愚蠢的建议，但你可以用一个检查searchedData匹配前是否为null的单一条件来替换两个if条件；即使只少了一行xD - Lorenzo

-2

使用深度优先搜索方法：树的遍历时间复杂度为O(n)。

public class NodeLevel
{
    public TreeNode Node { get; set;}
    public int Level { get; set;}
}

public class NodeLevelList
{
    private Dictionary<int,List<TreeNode>> finalLists = new Dictionary<int,List<TreeNode>>();

    public void AddToDictionary(NodeLevel ndlvl)
    {
        if(finalLists.ContainsKey(ndlvl.Level))
        {
            finalLists[ndlvl.Level].Add(ndlvl.Node);
        }
        else
        {
            finalLists.Add(ndlvl.Level,new List<TreeNode>(){ndlvl.Node});
        }
    }

    public Dictionary<int,List<TreeNode>> GetFinalList()
    {
        return finalLists;
    }
}

进行遍历的方法：

public static void DFSLevel(TreeNode root, int level, NodeLevelList nodeLevelList)
{
    if(root == null)
        return;

    nodeLevelList.AddToDictionary(new NodeLevel{Node = root, Level = level});

    level++;

    DFSLevel(root.Left,level,nodeLevelList);
    DFSLevel(root.Right,level,nodeLevelList);

}

- Saravanan

1

如果您可以在进行反对投票时添加一条评论，那将会很有帮助。 - Saravanan

13

一个很好的猜测是OP要求广度优先，而你的开头句子说你的答案是深度优先。 - ProfK

此外，如果您只是搜索特定值，则基本上通过创建字典和许多列表来分配比所需更多的内存，这并不是真正需要的。 - Lorenzo

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- CodesInChaos · Accepted Answer

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

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

这可以与Node上的Children属性一起使用：

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

...

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