遞歸方法內的java循環

我有一個名爲TrieNode的類，它有一個char鍵和triNode的arrayList。我正在嘗試執行一個trie。遞歸方法內的java循環

結構：

something like this

例如根密鑰是'。孩子們是t，o，s和p。對於具有密鑰's'的節點，孩子是t和p。我想計算trie中的節點數。我用這個算法

public int size(TrieNode tmp, int n){ 

    if(tmp.children.isEmpty()){ 
     return 0; 
    } 

    for(int i=0;i<tmp.children.size();i++){ 
     return 1 + size(tmp.children.get(i), n); 
    } 


    return 1; 
}

問題是我對每個電話都不是唯一的。所以這個方法是在根上調用的，然後是孩子t然後是o直到p。當它再次返回時，它不會調用p上的方法。

如何解決這個問題？

來源

2017-05-14 Number 13

你爲什麼混合遞歸和循環？ –

，因爲我想遍歷ArrayList以便在所有節點上調用我的方法。 –

@Aominè爲什麼他不應該？如果你有一棵樹，並且你需要在每個節點上重複出現，我認爲可以循環遍歷給定節點的所有子節點，並在每個節點上重複出現。 – BackSlash

問題是您退出第一個元素的循環。如果你想總結所有的元素，那麼你需要在返回父項之前對遞歸結果進行求和。

public int size(TrieNode tmp, int n){ 

    int sum = 0; 
    for(int i=0;i<tmp.children.size();i++){ 
     sum += size(tmp.children.get(i), n); 
    } 

    if(/* node has char n */){ 
     return sum + 1; 
    } 
    return sum ; 
}

來源

2017-05-14 16:20:29 Beri

感謝您的幫助。 –

這就是堆棧的用途。遞歸函數在開始時可能會非常棘手，但它們很容易:) – Beri

使用DFS這個算法。您訪問的每個節點都是一個子節點。在您訪問該子節點之後總結計數。做這樣的事情..

//the root is the first node to be passed on.** 
void size(TrieNode node){ 
if(node is null) return; 
if(node is not null) result.add(node); 

while(there exist childNode in node){ 
    size(childNode); 
} 
}

結果是包含樹的所有節點的ArrayList。 result.size()爲您提供了樹中的節點數量。

來源

2017-05-14 16:27:48 neeranzan

遞歸方法內的java循環

回答

相關問題