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

У меня возникли проблемы с написанием алгоритма для определения высоты дерева дерева. Я понятия не имею, как начать или как я могу это сделать. Извините, если это «нубский» вопрос, но я новичок в попытках, и это единственная часть, отсутствующая в моем задании.

В любом случае, вот структура дерева дерева:

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. Но я не знаю, как это сделать. Мне просто нужно решение, поэтому любые методы определения высоты этого дерева будут очень признательны.

Спасибо.


c height tree trie radix
person Roger M    schedule 27.11.2014    source источник

Ответы (1)


arrow_upward
5
arrow_downward

Вы можете сделать это с помощью рекурсивной функции, которая принимает 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;
}
person Sergey Kalinichenko    schedule 27.11.2014
comment
Не уверен, что if (t->IsItAWord) return 1; это хорошая идея.. если узел может одновременно представлять конец слова и середину другого, вы все равно захотите проверить дочерние элементы.. и если они все NULL, вы' d по-прежнему возвращает 1 даже без этой строки. - person Dmitri; 27.11.2014