如何在 C 中查找 trie 树的高度

Question

我在编写算法以找到trie树的高度时遇到了麻烦。我不知道如何开始或如何做到这一点。抱歉，如果这是一个"菜鸟"问题，但我对尝试很陌生，这是我作业中唯一缺少的部分。

无论如何，这是trie树的结构：

typedef struct RegTrie * ImplTrie;
typedef struct RegTrie {
  Boolean IsItAWord; /* true if it is a word, false if it is not a word */
  ImplTrie children[ALPHABETsize];
} RegTrie;

所以基本上，如果 'a' 是一个孩子，那么在 chidren[0] 中将有一个 Trie，如果 'b' 不是孩子，则 child[1] 将为 NULL。如您所见，字符是由链接索引隐式定义的，如果过去节点的字符在当前节点之前形成一个单词，则"布尔 IsItAWord"将为真。

你们能给我一个灯吗？我唯一知道的是，高度可以通过最长单词的长度 + 1 来定义。但我不知道该怎么做。我真的只是想要一个解决方案，所以任何找到这个尝试高度的方法都将不胜感激。

谢谢。

Answer 1

您可以使用递

归函数来实现，该函数接受ImplTrie并返回int。

基本情况检查ImplTrie是否NULL，在这种情况下，函数返回0。

否则，该函数将遍历children，调用自身，选取最大值，并返回最大值加一。

int height(ImplTrie t) {
    if (!t) return 0;
    int res = 0;
    for (int i = 0 ; i != ALPHABETsize ; i++) {
        int h = height(t->children[i]);
        if (h > res) {
            res = h;
        }
    }
    return res + 1;
}