[Algo] Trie 간단 insert, find code

TRIE를 이용하여 insert 및 find, print를 하는 코드이다.

 

#include <stdio.h>
#include <iostream>
using namespace std;
 
#define rr register int
#define null 0
 
typedef struct trie {
    bool finish;
    trie* child[26];
    trie() {
        finish = 0;
        for (rr i =0; i < 26; i++)
            child[i] = null;
    }
    void insert(char* str) {
        if (*str == null) {
            finish = true;
            return;
        }
 
        int id = *str - 'a';
        if(child[id] == null)
            child[id] = new trie();
        child[id]->insert(str + 1);
    }
    bool find(char* str) {
        if (*str == null) {
            return finish;
        }
        int id = *str - 'a';
        if (child[id] == null)
            return false;
        return child[id]->find(str + 1);
    }
    void printAll(int id) {
        //cout << ('a' + id) << endl;
        printf("%c", ('a' + id));
        if (finish)
            cout << endl;
        for (rr i = 0; i < 26; i++) {
            if(child[i] != null)
                child[i]->printAll(i);
        }
    }
};
 
trie root;
 
void printAll(trie* node, char buffer[10], int id) {
    if (node->finish) {
        buffer[id] = null;
        cout << buffer << endl;
    }
    for (rr i = 0; i < 26; i++) {
        if (node->child[i] != null) {
            buffer[id] = 'a' + i;
            printAll(node->child[i], buffer, id + 1);
        }
    }
}
 
int main(void) {
 
    cout << "d"<<endl;
    {
        char input[] = "string";
        root.insert(input);
    } {
        char input[] = "strong";
        root.insert(input);
    }
    int a = 0;
    {
        char input[] = "string";
        cout << root.find(input) << endl;
    }
    {
        char input[] = "strin";
        cout << root.find(input) << endl;
    }
    {
        char input[] = "strongg";
        cout << root.find(input) << endl;
    }
    {
        char input[] = "strong";
        cout << root.find(input) << endl;
    }
 
    cout << "all node 탐색" << endl;
    for(rr i =0; i <26; i++)
        if(root.child[i] != null)
            root.printAll(i); //
 
    cout << "all node 정렬" << endl;
    for (rr i = 0; i < 26; i++) {
        if (root.child[i] != null) {
            char buffer[10] = { 0, };
            printAll(&root, buffer, 0);
        }
    }
 
    return 0;
}