0

我有一个很简单的任务。我必须使用以下结构创建一棵树：

 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;
4

1 回答 1

4

看起来您的问题在于搜索firstChild 或兄弟列表的逻辑。也就是说，如果你有第一个孩子，你永远不会看兄弟姐妹。如果您的树是从后到前构建的，它可能会解释为什么搜索节点 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);
于 2013-04-29T03:51:18.780 回答