Нахождение высоты многолучевого дерева

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

Несмотря на то, что она стоит (почти ничего), эта проблема прекрасно отрисовывается в чисто функциональных языках, таких как SML:

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

Answer 3

Это зависит от того, как хранятся дочерние узлы. Предположим на секунду, что они хранятся в векторе. Затем вы можете использовать следующее для расчета их высоты.

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 4

если не ноль:

• найти рост каждого из детей
• взять максимум
• добавить 1

Answer 5

Разве это не '1 + максимальная высота поддерева, начиная с любого из дочерних узлов (текущего) корневого узла'?

Обратите внимание, что двоичное дерево - это особый случай многоходового дерева, в котором дочерние узлы известны как левый и правый дочерние узлы. Результат равен нулю, если указатель корневого узла равен нулю.