廣度優先遍歷

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

}