Trie

[Hsue66]

include

using namespace std;

include

define ALPHA 26

define MAX 100

struct TrieNode { TrieNode *child[ALPHA]; bool terminal;

void init() {
    terminal = false;
    for (int i = 0; i < ALPHA; i++)
        child[i] = 0;
}

};

struct Trie { TrieNode node[MAX]; int size; TrieNode *root;

TrieNode* alloc() {
    return &node[size++];
}

void init() {
    size = 0;
    root = alloc();
    root->init();
}

void insert(TrieNode *now, char* str) {
    if (*str == '\0') {
        now->terminal = true;
        return;
    }
    if (now->child[*str - 'a'] == 0) {
        now->child[*str - 'a'] = alloc();
        now->child[*str - 'a']->init();
        cout << "new" << endl;
    }
    insert(now->child[*str - 'a'], str + 1);
}

TrieNode* find(TrieNode *now, const char* str) {
    if (*str == '\0') {
        return now;
    }
    if (now->child[*str - 'a'] == 0)
        return nullptr;
    return find(now->child[*str - 'a'], str + 1);
}

};

int main() { Trie trie; trie.init(); trie.insert(trie.root, (char)"hello"); trie.insert(trie.root, (char)"help"); if (trie.find(trie.root, (char*)"hello") != 0) cout << "hello IN" << endl;

if (trie.find(trie.root, (char*)"hel") != 0)
    cout << "hel IN" << endl;
if (trie.find(trie.root, (char*)"hte") == 0)
    cout << "hte IN" << endl;

}