Tree traversal

[Ankit]

I’m trying to create a function in C++ that would make an iterator traverse a tree in the following way: Visit root node first, traverse right subtree, traverse left subtree. I have already created a separate function that would initialize the iterator at the root.

Below is the function that I have written so far that would traverse the tree assuming that the iterator is already at the root.                               
                                                                                                                                                              

<br /> if (n.HasRightChild() )<br />   n++;<br /> else if n.HasLeftChild())<br />   ++n;<br /> else<br /> {<br />   --n;<br />   if (n.HasLeftChild() )<br />    ++n;<br /> }<br />  <br /> return *this;

1 2 3 4 5 6 7 8 9 10 11 12 13

<br /> if (n.HasRightChild() )<br />   n++;<br /> else if n.HasLeftChild())<br />   ++n;<br /> else<br /> {<br />   --n;<br />   if (n.HasLeftChild() )<br />    ++n;<br /> }<br />  <br /> return *this;

 
The problem I’m having with this function is that once the iterator reaches the end of the right subtree, it will go into an infinite loop. The “n++” makes the iterator go down to the right while the “–n” makes the iterator go up. The iterator goes back and forth between two nodes causing an infinite loop. How can I correct this problem?

[will]

Hello
You will need to use this function recursively and mantain the visiting of the nodes. you will need to keep track of all the nodes which have been traversed and on that criteria you will call this dunction. At the moment you are just calling this function from any location and it gets stuck in loop. So in order to break that loop you will need a criteria to break the loop. And that criteria can be fulfilled by using another linked list or a variable which will hold the number of nodes traversed and then compare that variable with the actual number of nodes of the tree.
Hopefully this answers your question.

[Author]

Posts