Как рекурсивно найти высоту Trie Tree

Question

У меня есть небольшая проблема, когда выясняется, как найти высоту структуры данных trie tree. Я знаю, что для дерева AVL простая рекурсивная функция высоты будет:

height(nodeType *node) const 
{ 
    if(node == NULL) 
    return 0; 

    // if tree is not empty height is 1 + max of either path 
    return 1 + std::max(height(node->left), height(node->right)); 
} 

, но теперь мое Trie дерево имеет детей с 26 различными индексами, должна быть простой способ найти максимальную высоту без печатала все 26 различные возможные индексы. Как я могу это сделать?

int height(trieNodeType *node) const 
{ 
    if(node == NULL) 
    return 0; 

    for(int i = 0; i < 26; i ++) { 
    //has to be something to do with a for loop, 
    //i know that much 
    } 
} 

Answer 1

Looping - это путь.

C++ 11:

if (node == nullptr) return 0; 

auto i = std::begin(node->children); 
auto end = std::end(node->children); 

auto max_height = height(i++); 

while (i != end) { 
    max_height = std::max(max_height, height(i++)); 
} 

return 1 + max_height; 

C++ < 11.

if (node == NULL) return 0; 

trieNodeType ** i = node->children; 
trieNodeType ** end = i + (sizeof(node->children)/sizeof(trieNodeType *)); 

int max_height = height(i++); 

while (i != end) { 
    max_height = std::max(max_height, height(i++)); 
} 

return 1 + max_height; 

Answer 2

Другой подход C++ 11

return 1 + std::accumulate(std::begin(node->children) + 1, std::end(node->children), 
    height(node->children[0]), 
    [](int curMax, trieNodeType* child) { return std::max(curMax, height(child)); }); 

Там существует также std::max_element функцию, но в простой реализации использование этого приведет к вычислению высоты одного и того же дочернего узла ral раз.