c++ - C++中的树遍历

Question

我的作业很简单。我必须使用此结构创建一棵树:

 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);
}

我不知道出了什么问题。它似乎不想找到所有的 child 。例如，如果我将 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;

Answer 1

看起来您的问题出在搜索firstChild OR siblingList 的逻辑上。也就是说，如果你有第一个 child ，你永远不会看 sibling 。如果您的树是从后往前构建的，它可能会解释为什么搜索节点 4 而不是节点 2。相反，您可能想询问 search(element, t->firstChild) 是否成功，如果没有成功，则跳转到搜索(元素，t->siblingList):

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