查找多路樹的高度

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