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」が 1 つの子の場合、chidren[0] に Trie があり、「b」が子でない場合、children[1] は NULL になります。ご覧のとおり、文字はリンク インデックスによって暗黙的に定義されており、過去のノードの文字が現在のノードまでの単語を形成する場合、'Boolean IsItAWord' は true になります。

これで私に光を与えてもらえますか？私が知っている唯一のことは、高さは最長の単語の長さ + 1 で定義できるということです。しかし、それを行う方法がわかりません。私は本当に解決策が欲しいので、このトライの高さを見つける方法は大歓迎です。

ありがとうございました。

4

1 に答える 1

5

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;
}
于 2014-11-27T02:20:34.037 に答える