c - 将递归算法重构为迭代算法？

Question

我有以下递归算法需要编辑成迭代过程。 CvSeq是一个树结构。其中contour->h_next给出了同一层级的下一个节点。 contour->v_next 给出下一层的下一个轮廓。(子节点)

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
    }

}

我想将这个逻辑重构为迭代算法。 对此有什么建议吗？

Answer 1

要遍历没有递归的节点，您将需要堆栈来保存以前的状态。 [递归实际上也是在使用堆栈...]:

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;
    }
}