c - 如何在C中找到一棵特里树的高度

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' 是一个 child ，那么 children[0] 中会有一个 Trie，如果 'b' 不是 child ，那么 children[1] 将为 NULL。如您所见，字符是由链接索引隐式定义的，如果过去节点的字符组成一个词直到当前节点，'Boolean IsItAWord' 将为真。

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

谢谢。

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