如何在C中找到特里树的高度

Roger M 发表于 Dev

罗杰·M

我很难编写算法来找到特里树的高度。我不知道如何开始或如何做。抱歉，如果这是一个“新手”问题，但是我很想尝试，这是我分配的唯一缺少的部分。

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

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”不是孩子，则children [1]将为NULL。如您所见，这些字符是由链接索引隐式定义的，并且如果过去的节点的字符直到当前节点之前都构成一个单词，则'Boolean IsItAWord'将为true。

你们能给我个启示吗？我唯一知道的是，高度可以由最长单词+ 1的长度定义。但是我不知道该怎么做。我真的只想要一个解决方案，因此，找到此高度的任何方法将不胜感激。

谢谢你。

谢尔盖·卡里尼琴科（Sergey Kalinichenko）

您可以使用需要ImplTrie并返回的递归函数来完成此操作int。

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

否则，该函数将遍历循环children，调用自身，选择最大值，然后返回最大值加1。

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

本文收集自互联网，转载请注明来源。

如有侵权，请联系[email protected] 删除。