迭代遍歷樹找到大小

我需要使用迭代算法找到樹中元素的數量，但我發現代碼在概念上很難編寫。迭代遍歷樹找到大小

我的方法是從根節點開始，訪問子節點，然後訪問這些子節點的子節點，等等。

這是我寫的代碼，適用於一棵小樹，但並不是真正的解決辦法，因爲我需要添加一個額外的塊的每一個層次：

// Start the counter at 1 because the root node counts 
int size = 1; 

for(ITree child1 : root) { 
    size++; 
    for(ITree child2 : child1) { 
     size++; 
     for(ITree child3 : child2) { 
      size++; 
      for(ITree child4 : child3) { 
       size++; 
       for(ITree child5 : child4) { 
        size++; 
       } 
      } 
     } 
    } 
} 
return size;

來源

2011-11-21 Matt

我認爲這是你的一個類似的問題：http://stackoverflow.com/questions/547622/counting-nodes-in-a-tree-in-java你或許可以找到有些答案在那裏。 –

我之前讀過的文章很有幫助，但這棵樹不是二元的，我需要迭代地做。 – Matt

概念，保留一個堆棧（LinkedList等）。對於每個孩子（現在，你的孩子循環），添加到堆棧。繼續循環堆棧，直到最終爲空。

這沒有測試，但這應該做你正在尋找的。我只是用java.io.File，而不是你「ITree」，因爲這件事情我可以編譯反對：

int sizeOfTree(File root){ 
    // Start the counter at 1 because the root node counts 

    int size = 1; 

    LinkedList<File> stack = new LinkedList<File>(); 
    stack.add(root); 

    while(!stack.isEmpty()){ 
     File f = stack.remove(); 
     for(File child : f.listFiles()){ 
      size++; 
      stack.add(child); 
     } 
    } 

    return size; 
}

來源

2011-11-21 17:11:35 ziesemer

使用LinkedList將提供請求的「迭代」遍歷，而不是使用遞歸 - 這可能會導致堆棧溢出。 – ziesemer

仍然不明白髮生了什麼，但通過選票來判斷你是正確的，所以非常感謝:) – Matt

感謝接受 - 但我想幫助消除你有任何困惑。我可以詳細說明一下嗎？ – ziesemer

使用遞歸數據結構

它實際上不可能反覆地遍歷的遞歸數據結構，就像帶指針的樹 - 這是因爲對象「隱藏」了其基礎數據元素。

使用不同的數據結構

，所有的樹可以被存儲/爲線性，陣列的數據結構，其中索引可以用指數數學計算實現：

例如，一棵樹[0 ，1，2，3，null，4，null]將描述一棵在根上具有0的樹，其中0具有直接的孩子1和2.然後1離開孩子「3」，並且2離開孩子「4」。因此，如果以這種方式存儲樹，則元素的數量自然就是數組中非空元素的數量。

更簡單：將樹存儲在一個線性結構中，並且您可以在任何給定時間知道長度，而無需製作任何類型的花式算法。

來源

2011-11-21 17:14:44 jayunit100

您的任務的關鍵詞是遞歸。樹是一個經典的遞歸結構，因此您應該編寫接受根節點的遞歸方法，計算此節點的大小，然後爲所有子節點調用自身。下面是僞代碼：

public int getSize(ITree root) { 
    return getSize(root, 0); 
} 

private int getSize(ITree node, int size) { 
    size++; 
    for(ITree child : node.children()) { 
     size += getSize(child, size) 
    } 
    return size; 
}

來源

2011-11-21 17:15:07 AlexR

但這不僅是遞歸的，它也是迭代的。我可以使用遞歸嗎？或者只是迭代？（不是兩個） – Matt

請解釋當你說「互動」時你的意思是什麼 – AlexR

迭代遍歷樹找到大小

回答

相關問題