關於獲取二叉樹中節點數的問題

我已經寫了兩個函數（僞代碼），用於計算樹的根節點數和二叉樹的樹高度。最重要的是，二叉樹被表示爲第一個chiled/next兄弟格式。關於獲取二叉樹中節點數的問題

所以

struct TreeNode 
{ 
    Object element; 
    TreeNode *firstChild; 
    TreeNode *nextSibling; 
}

計算節點＃：

public int countNode(TreeNode root) 
{ 
    int count=0; 
    while(root!=null) 
    { 
     root= root.firstChild; 
     count++; 
    } 

     return count; 
} 

public int countHeight(TreeNode root) 
{ 
    int height=0; 
    while(root!=null) 
    { 
     root= root.nextSibling; 
     height++; 
    } 

    return height;

}

這是我的一個算法書看到了問題的一個，和我上面的解決方案似乎有有些問題，我也沒有完全理解使用Binary Tree的First Child/Right兄弟表示的問題，請問您能給我一些想法和反饋嗎？乾杯！

來源

2010-05-07 Kevin

使用下一個同級和第一個孩子可以大概可視化這樣的：

A1 -- A2 -- A3 
|  |  
|  B1 -- B2 -- B3 
|   | 
D1 -- D2 C1

圖中的水平線表示nextSibling和垂直線對應於firstChild鏈路。對於某些問題，這可能是自然可視化（但對於其他一些問題，您可能更喜歡具有兩個子節點的普通樹 - 它們是相同的）。

你的僞代碼似乎缺少一些東西，因爲你並不是真的在計算任何東西。我想你想在while循環中分別有count++，height++。

無論如何，要計算節點數量，您需要添加子節點的數量以及同一級別（同級）上的節點數量。對於合理的小樹林，這是可以完成遞歸：

public int countNode(TreeNode root) { 
    if (root == null) return 0; 
    return 1 + countNodes(root.firstChild) 
      + countNodes(root.nextSibling); 
}

對於較大的數據結構，你需要「被處理」的節點存儲在內存中的堆棧，以避免堆棧溢出（原文如此！）

要計算高度，首先需要確定高度如何定義。當您按照firstChild鏈接（即A1 -> D1）或者您是否想要樹中最長的路徑（任何位置）時（這將是A1 -> A2 -> B1 -> B2 -> C1），是否爲路徑？在第一種情況下，您的實施將是正確的。在第二種情況下，你需要一個類似於計數節點的遞歸函數（而不是添加，你會選擇更大的子樹）。

來源

2010-05-07 22:25:30

謝謝，托馬斯，我真的意識到我的錯誤在哪裏。我只是挑了兩個分支之一，忽略了另一個，這是可怕的！ – Kevin 2010-05-07 22:34:14

雖然字面上是正確的，但'第一個孩子'和'右兄弟姐妹'可能有點混亂。如果你用「左邊的孩子」和「右邊的孩子」取代那些，我認爲你可以更好地理解它。

來源

2010-05-07 22:16:35 Zr40

要理解遞歸，首先必須瞭解遞歸。

public int countNode(TreeNode root) 
{ 
    if (root==null) { 
     return 0; 
    } else { 
     return countNode(root.firstChild) + countNode(root.nextSibling) + 1; 
    } 
} 

public int countHeight(TreeNode root) 
{ 
    if (root==null) { 
     return 0; 
    } else { 
     return max(countHeight(root.firstChild), 
        countHeight(root.nextSibling)) + 1; 
    } 
}

如果樹爲空，它不包含節點並且沒有高度。

如果樹不爲空，則它比其較高的子樹高一個節點，並且它包含兩個子樹的所有節點以及包含這兩個子樹的節點。

閱讀Dave Touretzky關於LISP的書。戴夫教授使用龍的故事遞歸，龍實際上是一位很好的老師。

來源

2010-05-07 22:41:16

關於獲取二叉樹中節點數的問題

回答

相關問題