查找多路树的高度

Question

如何查找多路树的高度？如果我想找到一个二叉树的高度，我可以做这样的事情：

int height(node *root) { 
    if (root == NULL) 
    return 0; 
    else 
    return max(height(root->left), height(root->right)) + 1; 
} 

但我不知道我是否可以申请一个类似的递归方法来进行多方位的树。

Answer 1

是不是'1 +从（当前）根节点'的任何子节点开始的子树的最大高度？

请注意，二叉树只是多路树的一个特殊情况，其中子节点已知是左侧子节点和右侧子节点。如果根节点指针为空，结果为零。

Answer 2

如果非空：

• 找到每个孩子
• 取最大值
• 的高度加1

Answer 3

一般情况是：

int height(node *root) 
{ 
    if (root == NULL) 
     return 0; 
    else { 
     // pseudo code 
     int max = 0; 
     for each child { 
      int height = height(child); 
      if (height > max) max = height; 
     } 
     return max + 1; 
    } 
} 

Answer 4

这取决于子节点是如何存储。让我们假设它们存储在一个向量中。然后你可以使用以下来计算它们的高度。

int height(node* root) { 
    if (!root) { 
    return 0; 
    } 
    int max = 0; 
    for (vector<node*>::const_iterator it = root->children.begin(); 
     it != root->children.end(); 
     it++) { 
    int cur = height(*it); 
    if (cur > max) { 
     max = cur; 
    } 
    } 
    return max+1; 
} 

Answer 5

对于它的价值（几乎没有），这个问题呈现精美的纯功能性语言，如SML：

fun height Node(children) = (foldl max -1 (map height children)) + 1