广度优先遍历使用C＃ [英] Breadth-first traversal using C#
问题描述
我是想解决了一个面试问题，但我必须乘坐级二叉树水平。我设计BinaryNode具有以下变量
私有对象的数据;
私人BinaryNode离开;
私人BinaryNode权利;
可能有人请帮忙写BreadthFirstSearch方法在我BinarySearchTree类？
更新：谢谢大家对你的投入。因此，这是面试的问题。 给定一个二叉搜索树，设计一种算法，在每个深度创建的所有节点的链表（也就是说，如果你有一个深度D一棵树，你就会有d链表）。
下面是我的方法，让我知道你的专家意见。
公开名单＆LT; LinkedList的＆LT; B节点＆GT;＆GT; FindLevelLinkList（B节点根）
{
队列＆LT; B节点＆GT; Q =新的队列和LT; B节点＆GT;（）;
//从根开始的所有节点的列表。
名单＆LT; B节点＆GT;名单=新的名单，其中，B节点＆GT;（）;
q.Enqueue（根）;
而（q.Count大于0）
{
B节点电流= q.Dequeue（）;
如果（当前== NULL）
继续;
q.Enqueue（current.Left）;
q.Enqueue（current.Right）;
list.Add（电流）;
}
//添加相同深度的树节点成单独的链表。然后加入全部的LinkedList到列表
链表＆LT; B节点＆GT; LL =新的LinkedList＆LT; B节点＆GT;（）;
名单＆LT; LinkedList的＆LT; B节点＆GT;＆GT;结果=新名单，其中，LinkedList的＆LT; B节点＆GT;＆GT;（）;
LL.AddLast（根）;
INT currentDepth = 0;
的foreach（在列表B节点的节点）
{
如果（节点！=根）
{
如果（node.Depth == currentDepth）
{
LL.AddLast（节点）;
}
其他
{
result.Add（LL）;
LL =新的LinkedList＆LT; B节点＆GT;（）;
LL.AddLast（节点）;
currentDepth ++;
}
}
}
//添加最后一个链表
result.Add（LL）;
返回结果;
}
使用的堆栈的
一个广度优先搜索通常用的队列的，深度优先搜索来实现。
问答LT;节点＆GT; Q =新的队列和LT;节点＆GT;（）;
q.Enqueue（根）;
而（q.Count大于0）
{
节点电流= q.Dequeue（）;
如果（当前== NULL）
继续;
q.Enqueue（current.Left）;
q.Enqueue（current.Right）;
DoSomething的（目前的）;
}
作为一种替代你出队后，检查空可以添加到队列前检查。我没有编译code，所以它可能包含一些小的失误。
一个票友（但速度较慢）版本使用LINQ很好地结合：
公共静态的IEnumerable＆LT; T＆GT; BreadthFirstTopDownTraversal＆LT; T＆GT;（T根，Func键＆LT; T，IEnumerable的＆LT; T＆GT;＆GT;儿童）
{
变种Q =新的队列＆LT; T＆GT;（）;
q.Enqueue（根）;
而（q.Count大于0）
{
T电流= q.Dequeue（）;
产量回流;
的foreach（VAR孩子在儿童（电流））
q.Enqueue（子）;
}
}
这可以一起使用了孩子财产节点：
的IEnumerable＆LT; T＆GT;儿童{{返回新的[] {node.Left，node.Right}。凡（X =＆GT;！x = NULL）; }};
...
在BreadthFirstTopDownTraversal（根，节点=＆GT的foreach（VAR元素; node.Children）
{
...
}
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;
Could someone please help to write the BreadthFirstSearch method inside my BinarySearchTree class?
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;
}
A breadth first search is usually implemented with a queue, a depth first search using a stack.
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);
}
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.
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);
}
}
Which can be used together with a Children property on Node:
IEnumerable<T> Children { get { return new []{node.Left, node.Right}.Where(x => x != null); } };
...
foreach(var element in BreadthFirstTopDownTraversal(root, node => node.Children)
{
...
}
这篇关于广度优先遍历使用C＃的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
