Inorder Traversal

[RAKHE]

I am trying to understand the inorder traversal, i found a snippet
like this

void inorder(NODEPR ptr)
{

if(ptr != NULL)
inorder(ptr->left);
printf("%d\n",ptr->data);
inorder(ptr->right);
}

http://www.math.bas.bg/~nkirov/2010/NETB201/slides/ch06/pic3.jpg

consider the above Tree and expalin how it works in code level ...

please anyone throw a light on this

 

[ImpalerCore]

I am trying to understand the inorder traversal, i found a snippet
like this

void inorder(NODEPR ptr)
{

if(ptr != NULL)
inorder(ptr->left);
printf("%d\n",ptr->data);
inorder(ptr->right);

}

http://www.math.bas.bg/~nkirov/2010/NETB201/slides/ch06/pic3.jpg

consider the above Tree and expalin how it works in code level ...

please anyone throw a light on this

Well, the traversal algorithm uses recursion to print out the tree in
order. Note that calling inorder on the root will end up travelling
all the way down the left side first and make its way over to the
right.

inorder( A )
|
- inorder( ptr->left == B )
|
- inorder( ptr->left == D )
|
- inorder( ptr->left == NULL ) // does nothing
printf( ptr->data ) // prints D
inorder( ptr->right == NULL ) // does nothing
|
- printf( ptr->data ) // prints B
|
- inorder( ptr->right == E )
|
- inorder( ptr->left == H )
|
- inorder( ptr->left == NULL ) // does nothing
printf( ptr->data ) // prints H
inorder( ptr->right == NULL ) // does nothing
|
- printf( ptr->data ) // prints E
|
- inorder( ptr->right == I )
|
- inorder( ptr->left == NULL ) // does nothing
printf( ptr->data ) // prints I
inorder( ptr->right == NULL ) // does nothing
|
- printf( ptr->data ) // prints A
|
- inorder( ptr->right == C )

.... continues down the right side

Hopefully you get the idea. The tree traversal from wiki is good to
look at.

http://en.wikipedia.org/wiki/Tree_traversal

 

[Eric Sosman]

I am trying to understand the inorder traversal, i found a snippet
like this

void inorder(NODEPR ptr)
{

if(ptr != NULL)
inorder(ptr->left);
printf("%d\n",ptr->data);
inorder(ptr->right);
}

The snippet as quoted is missing a pair of { braces }.

http://www.math.bas.bg/~nkirov/2010/NETB201/slides/ch06/pic3.jpg

(The tree is [A [B [D E [H I]] C [F G]]].)

consider the above Tree and expalin how it works in code level ...

Suppose the function is called with ptr pointing to A, and
trace through what happens, step by step. Since ptr (==A) is
not NULL, the function calls a deeper version of itself, passing
ptr->left (==B) from the outer level. This becomes ptr at the
second level, and since it, too is not NULL, the second level
calls a still deeper version passing its own ptr->left (==D).
This becomes ptr at the third level, and since it is not NULL the
function calls itself yet again, passing its own ptr->left to a
fourth-level invocation. Here, ptr is NULL so the function does
nothing (assuming the missing braces have been replaced) and
returns. Back at the third level, the function prints the data
of its ptr (==D) node, and then calls another fourth-level version
passing ptr->right. Again, the fourth-level invocation finds that
its ptr is NULL and simply returns. The third-level function has
now done everything it wants, and also returns. Now we're back at
the second level, which prints B's data and calls another third-
level function with ptr->right (==E). And so on, and so on.

Something you need to keep in mind is that each inorder() call
has its own value for ptr. When an outer inorder() calls a deeper
inorder(), there are two distinct variables called ptr: One at the
outer level, and a different one at the inner level. If the inner
level calls a third level, a third ptr comes into existence, with
its own value independent of the other two.

 

[RAKHE]

Well, the traversal algorithm uses recursion to print out the tree in
order.  Note that calling inorder on the root will end up travelling
all the way down the left side first and make its way over to the
right.

inorder( A )
|
- inorder( ptr->left == B )
  |
  - inorder( ptr->left == D )
    |
    - inorder( ptr->left == NULL ) // does nothing
      printf( ptr->data ) // prints D
      inorder( ptr->right == NULL ) // does nothing
  |
  - printf( ptr->data ) // prints B
  |
  - inorder( ptr->right == E )
    |
    - inorder( ptr->left == H )
      |
      - inorder( ptr->left == NULL ) // does nothing
        printf( ptr->data ) // prints H
        inorder( ptr->right == NULL ) // does nothing
    |
    - printf( ptr->data ) // prints E
    |
    - inorder( ptr->right == I )
      |
      - inorder( ptr->left == NULL ) // does nothing
        printf( ptr->data ) // prints I
        inorder( ptr->right == NULL ) // does nothing
|
- printf( ptr->data ) // prints A
|
- inorder( ptr->right == C )

... continues down the right side

Hopefully you get the idea.  The tree traversal from wiki is good to
look at.

http://en.wikipedia.org/wiki/Tree_traversal- Hide quoted text -

- Show quoted text -

Thank you very Much !!!!