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.
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.
#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.


Sign In
Create Account


Back to top









