非遞歸地計算樹中的節點。

在最近的一次採訪中，我被要求在給定這個節點類的樹中統計所有節點。非遞歸地計算樹中的節點。

class Node 
{ 
    public List<Node> Children; 
}

雖然我在面試過程中有腦屁我在做它遞歸幾分鐘今天早上寫了這一點。

int CountNodes(Node node, int count) 
{ 
    count++; 

    if(node.Children == null) 
     return count; 

    foreach(Node n in node.Children) 
    { 
     count = CountNodes(n, count); 
    } 

    return count; 
}

但是在會話期間，我們討論了遞歸方法的問題。一個是堆棧溢出。

什麼是非遞歸方法來解決這個問題。我似乎正在努力。

來源

2016-11-18 CathalMF

所以，你實現[深度優先搜索]（https://en.wikipedia.org/wiki/Depth-first_search） - 另一種選擇是[廣度優先搜索]（https://en.wikipedia.org/wiki/Breadth-first_search ），這基本上是[尾遞歸]（https://en.wikipedia.org/wiki/Tail_call）。最後，如果你控制Node的實現，當子節點被添加時（根節點），你也可以在Node節點上增加一個子節點。 –

通常的方法是使用隊列。該算法非常簡單：首先添加根節點。然後，當隊列不爲空時：出列隊列，對其執行任何操作，然後將其所有子隊列添加到隊列中，重複。 –

您可以從包含所有根節點的List<Node> nodes開始。該方法將循環，直到沒有節點留在「當前」的水平，並在每次迭代更換nodes列表與水平的孩子：

List<Node> nodes = GetRootNodes(); 
int total = 0; 
while (nodes.Count > 0) 
{ 
    total += nodes.Count; 
    List<Node> children = new List<Node>(); 
    foreach (Node node in nodes) 
    { 
     children.AddRange(node.Children); 
    } 

    nodes = children; 
}

來源

2016-11-18 10:30:07

[廣度優先搜索]（https://en.wikipedia.org/wiki/Breadth-first_search）是技術*術語* :) –

Breadth-first search

int CountNodes(Node node) 
{ 
    int count = 0; 
    List<Node> nodesToSearch = new List<Node>(); 
    nodesToSearch.Add(node); 

    while(nodesToSearch.Count > 0){ 
     count += nodesToSearch.Count; 

     List<Node> newNodes = new List<Node>(); 
     foreach(Node nodeToSearch in nodesToSearch){ 
      if(nodeToSearch.Children != null) 
       newNodes.AddRange(nodeToSearch.Children); 
     } 
     nodesToSearch = newNodes; 
    } 

    return count; 
}

來源

2016-11-18 10:33:44 GregaMohorko

不錯，您需要返回計數並檢查nodeToSearch.Children爲空。但它的工作。 – CathalMF

Tnx，固定它.. – GregaMohorko

非遞歸地計算樹中的節點。

回答

相關問題