Jump to content




Recent Status Updates

  • Photo
      30 Sep
    rhossis

    laptop hard disk seated beneath motherboard but with no access panel. 7 hours to replace :(

    Show comments (3)
  • Photo
      19 Sep
    Chall

    I love it when you go to write a help thread, then while writing, you reach an enlightenment, and figure it out yourself.

    Show comments (3)
View All Updates

Developed by TechBiz Xccelerator
Photo
- - - - -

Using loop to traverse tree

loop

  • Please log in to reply
2 replies to this topic

#1 kmhosny

kmhosny

    CC Addict

  • Just Joined
  • PipPipPipPipPip
  • 123 posts

Posted 29 March 2010 - 12:10 PM

Hi All,
What i am going to write about is using loops to traverse trees instead of using the basic recursion technique.
The recursion technique is indeed a good method when traversing a medium size tree but most probably it may end with a buffer overflow exception if the tree is large enough.
A quick review on what happens when you use recursion:

when using recursion the program operates ordinary as the same way in a function call, since recursion is indeed a function call.

what happens is that each cycle the program calls the function, the program counter is pushed to indicate the line it stopped at before calling this function and the activation record for that function is pushed onto the program stack where the activation record contains the function local variables and addresses.

when the function terminates, the activation record of the function is removed form the top of the stack and the program counter is read and the program continues executing from the first line after the function call.

now imagine it with recursion where in each call the function is pushed onto the stack and then pushed again and again and again the memory allocated may increase in a high speed and gets fulled and overflows and that may occur frequently when traversing a large tree.
The Loop way:

So the alternative is to use loops that simulates what does happen when recursion is called.

basically what i am going to do is to create a stack of the node type and push on it first the root node, then i am going to pop the node and push it's children and next cycle pop the node and push it's children and so on till the stack is emptied and my looping condition will be loop if the stack size is > 0.

Example:
#include<iostream>
#include<stack>
using namespace std;

#define NULL 0
class Node
{
public:
    Node* left;
    Node* right;
    int id;
    Node()
    {
        left=NULL;
        right=NULL;
        id=0;

    }
};
void traverse_tree_loop(Node n)
{
    stack<Node> tree;
    tree.push(n);
    while(tree.size()>0)
    {
        Node temp=tree.top();
        tree.pop();
        cout<<"i am ID#: "<<temp.id<<endl;
        if(temp.right!=NULL)
            tree.push(*(temp.right));
        if(temp.left!=NULL)
            tree.push(*(temp.left));
    }
}
 int main()
{
    Node root;
    Node ch1;
    Node ch2;
    Node ch3;
    Node ch4;
    Node ch5;
    root.id=0;
    root.left=&ch1;
    root.right=&ch2;
    ch1.id=1;
    ch1.left=&ch3;
    ch1.right=&ch4;
    ch2.id=2;
    ch2.left=&ch5;
    ch3.id=3;
    ch4.id=4;
    ch5.id=5;
    traverse_tree_loop(root);
    return 1;
}

the tree is:
0-as root with left child 1, right child 2
1 has child 3 as left, child 4 as right
2 has child 5 as left child.
the output for this program is:
i am ID#: 0
i am ID#: 1
i am ID#: 3
i am ID#: 4
i am ID#: 2
i am ID#: 5

So by this basic tutorial we can see that trees can be traversed using loops in an easy way which is simulating what happens in the recursion way.
Thank you for reading and i hope i was helpful.
  • 0
"Recursion is just a line of code"
-Karim Hosny-
My flickr

#2 NeoCambell

NeoCambell

    CC Lurker

  • Just Joined
  • Pip
  • 1 posts

Posted 30 March 2010 - 11:49 PM

There are 3 types of traversing methods. Pre, In and Post-order.
For most of the applications including sorting, it is required to show the nodes in a particular order.
I think it will be quite difficult to do this without recursion, isn't it?
  • 0

#3 kmhosny

kmhosny

    CC Addict

  • Just Joined
  • PipPipPipPipPip
  • 123 posts

Posted 01 April 2010 - 01:55 AM

yes i guess so it's best suited for pre-order traversing.
  • 0
"Recursion is just a line of code"
-Karim Hosny-
My flickr





Also tagged with one or more of these keywords: loop

Powered by binpress