CODEWITHSUNDEEP
c++searchrecursiontreetree-traversal
marcinx27
marcinx27

Reputation: 253

Searching a tree in c++(not binary)

I asked a similar question before, but now I'm looking for a why this isn't working instead of "help me fix".

I have to create a general tree that looks like this:

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

My search method, which I use for every other method in the class, is 

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

Where firstChild is the vertical pointers in the picture and siblingList is the horizontal pointers in the picture.

My issue is that it is not finding 5, 6, or 7(the children of 2).

The recursive stack looks like this(at least I think it should in my head):

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.

Does anyone know where I am getting lost?

Upvotes: 1

Views: 1055

Answers (3)

Emilio Garavaglia
Emilio Garavaglia

Reputation: 20730

The problem is in 

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

The return statement makes the function return in any case if there are siblings, independently if something was found or not.

On node 2, you will return having it 3 as a sibling, and the "child" descendance will never be attempted.

This way should be correct

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
}

Upvotes: 1

Roee Gavirel
Roee Gavirel

Reputation: 19445

your problem was here, it t->siblingList != NULL you never got to 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)
}

Upvotes: 1

fatihk
fatihk

Reputation: 7919

You need to to control NULL result in the sibling search:

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

Upvotes: 1

Related Questions