广度优先遍历 [英] Breadth-first traversal
问题描述
我试图解决一个面试问题,但为此我必须逐级遍历二叉树。我设计的BinaryNode具有以下变量
I was trying to solve one interview question, but for that I have to travel the binary tree level by level. I have designed BinaryNode with having below variable
private object data;
private BinaryNode left;
private BinaryNode right;
有人可以帮我在BinarySearchTree类中编写BreadthFirstSearch方法吗?
Could someone please help to write the BreadthFirstSearch method inside my BinarySearchTree class?
更新:谢谢大家的投入。这就是面试的问题。
给出一个二叉搜索树,设计一种算法,该算法创建每个深度的所有节点的链表(即,如果您的树的深度为D,则将有D个链表)。
Update: Thanks everyone for your inputs. So this was the interview question. "Given a binary search tree, design an algorithm which creates a linked list of all the nodes at each depth (i.e., if you have a tree with depth D, you’ll have D linked lists)".
这是我的方法,请告诉我您的专家意见。
Here is my Method, let me know your expert comment.
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;
}
推荐答案
通常是广度优先搜索
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 $的替代方法c $ c>出队后,您可以在添加到队列之前进行检查。我没有编译代码,所以它可能包含一些小错误。
As an alternative to checking for null
after dequeuing you can check before adding to the Queue. I didn't compile the code, so it might contain some small mistakes.
一个更好(但速度较慢)的版本与LINQ很好地集成:
A fancier (but slower) version that integrates well with 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);
}
}
可以与<$ c $一起使用c> 节点
上的儿童属性:
Which can be used together with a Children
property on Node
:
IEnumerable<Node> Children { get { return new []{ Left, Right }.Where(x => x != null); } }
...
foreach(var node in BreadthFirstTopDownTraversal(root, node => node.Children))
{
...
}
这篇关于广度优先遍历的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!