C++中的遍历树

我有一个足够简单的任务。我要创建一个使用该结构的树：C++中的遍历树

struct gennode 
{ 
int item; 
gennode * firstChild; 
gennode * siblingList; 
gennode * prevSibling; 
gennode * parent; 
};

我的搜索算法是这样的：

gennode* general::search(int element, gennode *t) 
{ 
    if(t == NULL) 
    { 
     return t; 
    } 
    if(t->item == element) 
    { 
     return t; 
    } 
    if(t->firstChild != NULL) 
    { 
     return search(element, t->firstChild); 
    } 
    return search(element, t->siblingList); 
}

我想不出什么错误。它似乎不想找到所有的孩子。例如，如果我有1作为根，2,3,4作为孩子，5,6,7作为2和8,9的孩子作为4的孩子，我无法搜索找到2的孩子。

我找不出我的问题在哪里。

编辑：下面是一个gennode结构如何在树中查找的例子，其中1作为根，2和3作为子节点。

gennode * one; 
gennode * two; 
gennode * three; 

one->item = 1; 
one->firstChild = two; 
one->siblingList = NULL; 
one->prevSibling = NULL; 
one->parent = NULL; 

two->item = 2; 
two->firstChild = NULL; 
two->siblingList = three; 
two->prevSibling = NULL; 
two->parent = one; 

three->item = 3; 
three->firstChild = NULL; 
three->siblingList = NULL; 
three->prevSibling = two; 
three->parent = one;

来源

2013-04-29 marcinx27

siblingList引用了什么？如同一个单一节点如何列表？如果你有一个孩子的列表，将它们存储在一个矢量而不是单个节点中不是更好吗？ siblingList是下一个兄弟姐妹，并prevSibling前一个？这个我不清楚。 – 2013-04-29 03:43:36

与你的例子请给予节点的gennode成员值为值2 – 999k 2013-04-29 03:49:45

我编辑原始帖子，包括一个例子。 – marcinx27 2013-04-29 04:12:32

它看起来像你的问题是与搜索则firstChild OR siblingList的逻辑。也就是说，如果你有firstChild，你就永远不会看兄弟姐妹。如果您的树是从后到前构建的，它可能会解释为什么要搜索节点4，而不是节点2.相反，您可能想要问一下search（element，t-> firstChild）是否成功，如果不成功，则转到搜索（element，t-> siblingList）：

if(t->firstChild != NULL) 
{ 
    auto result = search(element, t->firstChild); 
    if(result != nullptr) 
    return result; 
} 
return search(element, t->siblingList);

来源

2013-04-29 03:51:18

我完全不理解这段代码。如果通过兄弟姐妹找到一个NULL指针，它将会中断。我只是困惑。 – marcinx27 2013-04-29 04:35:58

C++中的遍历树

回答

相关问题