广度优先遍历
广度优先遍历
提问于 2011-02-25 07:01:49
我试图解决一个面试问题，但为了解决这个问题，我不得不逐级遍历二叉树。我用下面的变量设计了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;
}回答 3
Stack Overflow用户
回答已采纳
发布于 2011-02-25 07:07:53
广度优先搜索通常通过队列实现，深度优先搜索使用堆栈。
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))
{
...
}Stack Overflow用户
发布于 2011-02-25 07:10:55
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);
}Stack Overflow用户
发布于 2017-02-28 13:14:04
使用DFS方法:树的遍历是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);
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/5111645
复制相关文章
相似问题
腾讯云开发者
