Is a recursive iterative refactoring algorithm?

Question

I have the following recursive algorithm needed to convert to an iterative process. CvSeq is a tree structure. Where contour-> h_next gives the next node at the same level. path-> v_next gives the next path at a lower level. (child node)

void helperParseCurves(CvSeq* contour, int level) { if(contour->h_next != NULL) { helperParseCurves(contour->h_next, level); } if(contour->v_next != NULL) { helperParseCurves(contour->v_next, level+1); } //Process the nodes in contour for(int i=0; i<contour->total; i++){ CvPoint* p = CV_GET_SEQ_ELEM(CvPoint, contour, i); //Paint the point p } } 

I want to reorganize this logic into an iterative algorithm. Any advice on this?

Answer 1

To move nodes without recursion, you need a stack to save previous states. [Recursion actually uses the stack as well ...]:

 struct StackData { CvSeq* contour; int level; int traversed; }; const int traversed_l = (1 << 0); const int traversed_r = (1 << 1); const int stack_size = 50; // should be at leas max depth StackData stack[stack_size]; int stack_p = 0; void helperParseCurves(CvSeq* contour, int level) { int traversed = 0; while(contour) { if(contour->h_next != NULL && !(traversed & traversed_l)) { // down to left assert(stack_p < stack_size); // and save current state traversed |= traversed_l; stack[stack_p].contour = contour; stack[stack_p].level = level; stack[stack_p].traversed = traversed; ++stack_p; contour = contour->h_next; traversed = 0; continue; } if(contour->h_next != NULL && !(traversed & traversed_r)) { // down to right assert(stack_p < stack_p); // and save current state traversed |= traversed_r; stack[stack_p].contour = contour; stack[stack_p].level = level; stack[stack_p].traversed = traversed; ++stack_p; contour = contour->v_next; level = level+1; traversed = 0; continue; } //Process the nodes in contour for(int i=0; i<contour->total; i++){ CvPoint* p = CV_GET_SEQ_ELEM(CvPoint, contour, i); //Paint the point p } // move up because either left and right nodes are NULL or already traversed if(!stack_p) break; // we are at the top contour = stack[stack_p].contour; level = stack[stack_p].level; traversed = stack[stack_p].traversed; --stack_p; } } 

Answer 2

You have an empty vector / array / queue CvSeq *. Have a pointer / pointer in it, first pointing to its beginning (where the very first element will be).

Start with the root of the tree and add its h_next and v_next to the vector.

Then, while the index is less than the number of pointers in vector-1, take the vector [index] h_next and v_next, add them to the end of the vector and the do ++ pointer.

As a result, you get pointers to all nodes of the tree in this vector / array / whatever.

Then you just iterate over it, draw things and much more.