递归算法树

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! 
}