c++ - 多元木の高さを見つける

Question

多面木の高さはどうやって求めるのですか? 二分木の高さを知りたい場合は、次のようにすることができます。

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

しかし、同様の再帰的方法を多元木に適用できるかどうかはわかりません。

Answer 1

一般的なケースは次のとおりです。

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 2

これは、子ノードの格納方法によって異なります。それらがベクトルに格納されていると仮定しましょう。次に、以下を使用して高さを計算できます。

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 3

それだけの価値はありますが (ほとんど何もありません)、この問題は SML のような純粋関数型言語で美しくレンダリングされます。

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

Answer 4

「1 + (現在の) ルート ノードのいずれかの子ノードから始まるサブツリーの最大高さ」ではないですか?

二分木は、子ノードが左の子と右の子であることがわかっている多元木の特殊なケースであることに注意してください。ルート ノード ポインタが null の場合、結果はゼロです。

Answer 5

null 以外の場合:

• それぞれの子供の身長を見つける
• 最大を取る
• 1を追加