CODEWITHSUNDEEP
calgorithm
andre
andre

Reputation: 175

Traversing a tree using linked list structure

I have a struct node which contains a next and a child. 

struct Node{
Node *parent;
Node *next;
Node *child;
}

The following picture shows the structure of the tree.

How would I write a function that traverse that tree? without recursion ? enter image description here

I have a pseudo code in my mind but not sure if its correct or no, because each node can have a child and I need to search using that child too

while ( root !=NULL)
{

root = root->next;
}

I would like to visit all the nodes.

Upvotes: 1

Views: 876

Answers (3)

A.S.H
A.S.H

Reputation: 29332

A Depth-First traversal can be done in the following way, without the need of the parent pointer:

  std::stack<Node*> Q; Q.push(root);
  while(!Q.empty())
  {  Node* node = Q.top(); Q.pop();
     // visit the node, do stuff
     if(node->next) Q.push(node->next);
     if(node->child) Q.push(node->child);
  }

Notice it is depth first because the child, if any, will be visited before the nodes at the same level, which are chained via the next pointer.

Upvotes: 1

M Oehm
M Oehm

Reputation: 29126

I guess you tree look like this:

-> grandma
    -> dad
        -> me
        -> sister
            -> niece
        -> brother
    -> uncle
        -> cousin

where indentation means a level of ancestry. The recursive function is simple:

void traverse_rec(const Node *node)
{
    if (node) {
        process(node);
        traverse_rec(node->child);
        traverse_rec(node->next);
    }
}

This can be rewritten as a loop. If the current node has a child, that's the next node to visit. Otherwise, you want to visit its sibling. But the node may not have actually a sibling. Because you have a link to the parent node (and the root node's parent should be ´NULL), you can backtrack up the tree until you find a sibling to follow or until the node is NULL.

void traverse2(const Node *node)
{
    while (node) {
        puts(node->name);

        if (node->child) {
            node = node->child;
        } else {
            while (node && node->next == NULL) {
                node = node->parent;
            }

            if (node) node = node->next;
        }
    }
}

This is more complicated than the recursive function, but it can be transformed to an iterator-like code, where you get the next node:

const Node *next(const Node *node)
{
    if (node == NULL) return NULL;
    if (node->child) return node->child;

    while (node && node->next == NULL) {
        node = node->parent;
    }

    if (node) return node->next;
    return NULL;
}

With this "iterator", you can then write code like:

for (const Node *p = root; p; p = next(p)) {
    puts(p->name);
}

Upvotes: 2

BLUEPIXY
BLUEPIXY

Reputation: 40145

the tree convert to liner list by queue. and process each node of liner list.

Pseudo code (not tested):

enqueue(q, root);//queue *q;
while(NULL!=(current_node = dequeue(q))){
    //do stuff current_node

    if(has_child(current_node)){//unnecessary, include for-loop
        for(node = current_node->child; node != NULL; node = node->next){
            enqueue(q, node);
        }
    }
}

Upvotes: 1

Related Questions