Троичное дерево поиска - PullRequest
Новая
       23

Троичное дерево поиска

5 голосов
/ 01 ноября 2011 
struct Ternary {

    char current;
    bool wordend;
    Ternary* left;
    Ternary* mid;
    Ternary* right;
    Ternary(char c='@',Ternary* l=NULL, Ternary* m=NULL, Ternary* r=NULL,bool end=false)
    {
        wordend=end;
        current=c;
        left=l;
        mid=m;
        right=r;
    }
};

void add(Ternary* t, string s, int i) {

    if (t == NULL) {
        Ternary* temp = new Ternary(s[i],NULL,NULL,NULL,false);
        t=temp;
    }

    if (s[i] < t->current) {
        add(t->left,s,i);
    }
    else if (s[i] > t->current) {
        add(t->right,s,i);
    }
    else
    {
        if ( i + 1 == s.length()) {
            t->wordend = true;
        }
        else
        {
            add(t->mid,s,i+1);
        }
    }
}

Когда я добавляю последовательность слов, используя add(), строка печатается внутри сегмента if(t==NULL), но дерево не формируется, т.е. узлы не связываются.

Ответы [ 2 ]

4 голосов
/ 01 ноября 2011 
t=temp;

Эта строка не действует вне функции add().Указатель вызывающего абонента не обновляется.

Вы можете изменить свою функцию, чтобы она возвращала Ternary* (в этом случае возвращать t в этом случае), и изменить сайты вызовов на: 

Ternary *tree = 0;
tree = add(tree, "hello", 1);
tree = add(tree, "bye", 1);
...
0 голосов
/ 10 января 2013

Небольшой трюк подойдет:

Заменить: 

void add(Ternary* t, string s, int i)

С: 

void add(Ternary*& t, string s, int i)

Это чище, чем проходить, а затем читать вывод следующим образом: 

tree = add(tree, "bye", 1);

В C ++ используйте их ссылки :) В C вы бы изменили сигнатуру функции на: 

void add(Ternary** t, string s, int i)

и не забудьте исправить t в соответствующих местах.

Ну, C ++ явно чище:)

...