1

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

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

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”将为真。

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

谢谢你。

4

1 回答 1

5

您可以使用一个递归函数来完成它，该函数接受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;
}
于 2014-11-27T02:20:34.037 回答