多方向木の高さの検索

Question

多方向木の高さはどうやって分かりますか？私は、バイナリツリーの高さを見つけたい場合は、私はこのような何かができる：

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

しかし、私は多分木に似た再帰的な方法を適用することができるかどうかわかりません。

Answer 1

（現在の）ルートノードの子ノードのいずれかから始まるサブツリーの最大高さ+1ではありませんか？

バイナリツリーは、子ノードが左の子と右の子であることが分かっているマルチウェイツリーの特殊なケースに過ぎないことに注意してください。ルートノードポインタがnullの場合、結果はゼロになります。

Answer 2

null以外の場合：

• は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