三叉搜索树

Question

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)段内打印，但树没有形成，即节点没有链接。

- CoderXX

Answer 1

t=temp;

这行代码仅在add()函数内起作用，调用者的指针不会被更新。

您可以将函数更改为返回一个Ternary*（在函数末尾返回t），并将调用站点更改为：

Ternary *tree = 0;
tree = add(tree, "hello", 1);
tree = add(tree, "bye", 1);
...

- Mat

---

或者将参数声明为add(Ternary** t, string s, int i)，然后执行*t = temp。 - AndersK

不使用 temp，我还尝试了以下语句 t = new Ternary(s[i])。如果我使用 tree = ...，那么我将失去树的根节点。 - CoderXX

@Pratik：只需在add()末尾添加return t;并按照我指示使用add，您就不会失去任何东西。 - Mat

Answer 2

只需要一个小技巧：

替换为：

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++ 显然更干净 :)

- Viet