遞歸算法樹

Question

可能重複：
the # of internal nodes

我正在當然，這是在CS數據結構。我有這個問題，要求提供遞歸算法，通過給定樹的根節點來確定樹的高度。 我將解釋什麼是樹的根節點：

        root 
           /\ 
        internal node internal node 
         /\     \ 
      external node internal node  external node 
           /    
          external node 

什麼我目前做的是：

• 輸入：INT R（R =根節點）T是樹
• 輸出：整數H（H =樹的高）

• HIGHT（T，R）：

• 如果r爲T的根節點然後

• 回報1
• 其他
• ^h < --- 1
• 爲每個孩子w^T中的R做
• ^h < ---最大（H，HIGHT（T，W））

• 返回1 + H

，我到目前爲止....

Answer 1

由於這是作業，我不想放棄解決方案，但這裏有一個有希望的幫助提示。

專注於樹的最頂端，根節點和孩子正好在它下面。如果您知道子樹的高度，那麼如何幫助您計算父樹的高度？

在你給了，想象一下你知道的高度（標有[方括號]）子樹和例子想找到根樹的高度：

       root[?] 
          /\ 
       internal node[3] internal node[2] 
        /\     \ 
     external node internal node  external node 
          /    
         external node 

另一個提示是你的代碼將具有以下結構，這是recursive programs通用的結構。您將有一個基本案例，然後歸納步驟其中您用較小的子問題表示您的問題。

int height(Node root) { 
    // The base case is that the node has no children, so it is a tree of height 1. 
    if (root has no children) return 1; 

    // Otherwise, apply the hint from above. Remember, you can call this height() 
    // function on the children of the root! 
}