search — Поиск дерева в c ++ (не бинарный)

Question

search — Поиск дерева в c ++ (не бинарный)

Я задавал подобный вопрос раньше, но теперь я ищу причину, по которой это не работает, вместо того, чтобы «помочь мне исправить».

Я должен создать общее дерево, которое выглядит так:

                       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).

Рекурсивный стек выглядит следующим образом (по крайней мере, мне так кажется):

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.

Кто-нибудь знает, где я заблудился?

1

c++recursion search tree tree-traversal

Решение

Другие решения

ваша проблема была здесь, это t-> siblingList! = NULL, вы никогда не попали в t-> FirstChild.

gennode* general::search(int element, gennode *t){
if(t == NULL)
{
return t;
}
if(t->item == element)
{
return t;
}
gennode* sibValue = search(element, t->siblingList);
if(sibValue != NULL)
{
return sibValue;// <-- only return if you have a valid value.
}
return search(element, t->firstChild)
}

1

Проблема в

  if(t->siblingList != NULL)
{
return search(element, t->siblingList)
}

Оператор return заставляет функцию возвращаться в любом случае, если есть братья и сестры, независимо, если что-то было найдено или нет.

На узле 2 вы вернете его с братом 3, и потомство «потомок» никогда не будет предприниматься.

Этот путь должен быть правильным

gennode* general::search(int element, gennode *t)
{
if(t == NULL) //no search at all
{ return NULL; }
if(t->item == element) // found
{ return t; }
gennode* z = search(element, t->siblingList);
if(z) return z; // if found return, otherwise ....
return search(element, t->firstChild); //... try the other way round
}

1

Источник

Accepted Answer

Вы должны контролировать 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;
}

1