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

Question

我无法编写算法来查找特里树的高度.我没有想法如何开始或如何做到这一点.对不起,如果这是一个'noob'问题,但我对尝试很新,这是我的任务中唯一缺少的部分.

无论如何这里是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'是一个孩子,在孩子[0]中会有一个Trie,如果'b'不是孩子,孩子[1]将是NULL.正如您所看到的,字符由链接索引隐式定义,如果过去节点的字符形成一个字直到当前节点,'Boolean IsItAWord'将为true.

你们能帮我个忙吗？我唯一知道的是,高度可以用最长的单词+ 1的长度来定义.但我不知道该怎么做.我真的只是想要一个解决方案,所以任何找到这个特里的高度的方法都将非常感激.

谢谢.

Answer 1

你可以使用递归函数来获取ImplTrie并返回一个int.

基础案例检查,如果ImplTrie是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;
}