CODEWITHSUNDEEP
c++treetraversal
marcinx27
marcinx27

Reputation: 253

Tree traversal in c++

I have an assignment that is simple enough. I have to create a tree using the this structure:

 struct gennode
{
 int item;
 gennode * firstChild;
 gennode * siblingList;
 gennode * prevSibling;
 gennode * parent;
};

My searching algorithm was this:

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

I cannot figure out what is going wrong. It does not seem to want to find all of the children. For example, if I have 1 as the root with 2, 3, 4 as its children and 5,6,7 as the children of 2 and 8,9 as the children of 4, I cannot get the search to find 2's children.

I cannot figure out where my issue is.

EDIT: Here is an example of how the gennode structures would look in a tree with 1 as the root and 2 and 3 as it's children.

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;

Upvotes: 0

Views: 427

Answers (1)

Scott Jones
Scott Jones

Reputation: 2908

It looks like your problem is with the logic of searching firstChild OR siblingList. That is, if you have a firstChild, you'll never look at siblings. If your tree is built from back to front, it might explain why node 4 is searched, but not node 2. Instead, you probably want to ask whether search(element, t->firstChild) succeeds, and if not, fall through to search(element, t->siblingList):

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

Upvotes: 4

Related Questions