Как найти высоту дерева в С

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" - один дочерний элемент, в chidren[0] будет Trie, а если "b" - не дочерний элемент, children[1] будет иметь значение NULL. Как вы можете видеть, символы неявно определяются индексом ссылки, и если символы прошлых узлов образуют слово вплоть до текущего узла, то Boolean 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;
}