c++ - 在 C++ 中搜索树(非二进制)

Question

我之前问过类似的问题，但现在我正在寻找为什么这不起作用而不是“帮助我修复”。

我必须创建一个看起来像这样的通用树:

                       1
                       /
                      v
                      2->3->4
                     /      /  
                    v       v
                    5-6-7   8-9 

我的搜索方法是

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

其中firstChild为图片中的垂直指针，siblingList为图片中的水平指针。

我的问题是找不到 5、6 或 7(2 的 child )。

递归堆栈看起来像这样(至少我认为它应该在我的脑海中):

search(5, *1)
search(5, *2)
search(5, *3)
search(5, *4)
search(5, *8)
search(5, *9)
return NULL(from *9)
return NULL(from *8)
return NULL(from *3)
search(5, *5)
return(*5) the rest of the way up.

有人知道我在哪里迷路了吗？

Answer 1

您需要在兄弟搜索中控制 NULL 结果:

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