Ako rekurzívne nájsť výšku Trie Tree - c ++, stromu, výšky, trie

Mám trochu problémy s tým, ako zistiť výšku stromovej štruktúry dát stromu. Viem, že pre strom AVL by bola jednoduchá funkcia rekurzívnej výšky:

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));
}

ale teraz môj strom trie má deti s 26 rôznymi indexmi, musí existovať jednoduchý spôsob, ako nájsť maximálnu výšku bez zadania všetkých 26 rôznych možných indexov. Ako by som mohol ísť na to?

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
}
}

odpovede:

Opakovanie je cesta.

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;

Ďalší prístup 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)); });

Existuje aj std :: max_element ale v priamej implementácii by to viedlo k výpočtu výšky rovnakého detského uzla niekoľkokrát.