广度优先遍历

Question

我试图解决一个面试问题，但为此我必须逐级访问二叉树。我已经设计BinaryNode用具有下述可变

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

可能有人请帮忙给我写BinarySearchTree类里面的广度优先搜索方法？

更新：谢谢大家的投入。所以这是面试问题。 “给定一个二叉搜索树，设计一个算法，该算法创建每个深度的所有节点的链表（即，如果您有一棵深度为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; 
    } 

Answer 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很好地结合：

​​

里面可以连同Children财产上Node使用：

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

...

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

Answer 2

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

Answer 3

使用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); 

}