1

在尝试学习 c++ 时，我尝试实现表示非常基本的 trie 的类。我想出了以下内容：

class Trie {
public:
    char data;
    vector<Trie* > children;

    Trie(char data);
    Trie* addChild(Trie* ch);    // adds child node

    (skipped others members/methods)

};

方法addChild检查具有相同数据的子ch是否存在于向量children中，如果没有，则将其插入那里，如果是 - 返回指向已存在子的指针。

现在，考虑这个代码片段：

Trie t('c');
Trie* firstchild = new Trie('b');
Trie* secondchild = new Trie('a');


firstchild->addChild(secondchild);
t.addChild(firstchild);

如果我只有指向secondchild的指针，是否有可能以某种方式返回指向firstchild甚至t的指针？

我想知道是否可以这样做，因为我的工作代码的逻辑需要遍历 trie “up”（从较低的节点到较高的节点），到当前对象的父级。目前我只是使用递归函数向下旅行 - 但我想知道是否存在其他方式？

如果上面不清楚或者我在某个地方搞砸了，我很抱歉，我相当缺乏经验并且根据我的记忆写作，没有工作代码。

4

3 回答 3

4

你需要添加类似的东西

Trie* parent;

或者

Trie* previoussibling;
Trie* nextsibling;

到班级直接从firstchildtosecondchild或反之亦然，或从其中一个孩子上到t。

请注意，如果您需要这种关系，那么在添加和删除节点以保持所有链接正确时，您将需要更多维护。

于 2009-09-23T08:55:20.040 回答
2

Trie 对象不跟踪父对象。它基本上类似于单链表，除非你“知道”父级，否则你不能回溯。

class Trie {
public:
    char data;
    vector<Trie* > children;
    Trie* parent;

    Trie(char data):parent(NULL){}
    Trie* addChild(Trie* ch)
    { //set the parent
     ch->parent = this;
    }

    (skipped others members/methods)

};

然后遍历看起来像：

traverse(Trie* pPtr)
{
Trie* currentPtr = pPtr;
 while(currentPtr)
 {
  currentPtr = currentPtr->parent;
 }

}

于 2009-09-23T08:49:35.230 回答
1

我只有指向第二个孩子的指针，是否有可能以某种方式返回指向第一个孩子甚至 t 的指针？

不，您必须通过将第一个孩子作为第二个孩子的父母来建立自己的关系。

于 2009-09-23T08:52:06.223 回答