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

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
    }

}

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

- Ashika Umanga Umagiliya

---

你会从哪里开始？你尝试过什么，为什么会遇到问题？ - Mahmoud Al-Qudsi

你有成员h_previous和v_previous吗？ - Mahmoud Al-Qudsi

常见问题：“如何用迭代替换递归？”回答：“使用栈数据结构。”有时还有比这更简单的答案（例如，使用循环代替递归），但这取决于问题的复杂性。 - Merlyn Morgan-Graham

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

- GreenScape

---

看起来你在第一个“if”语句的结尾忘记了加上“continue”。 - Konstantin Oznobihin

Answer 2

创建一个CvSeq*类型的空向量/数组/队列。在开始时，将索引/指针指向其开头（即第一个元素所在位置）。

从树的根节点开始，将其h_next和v_next添加到向量中。

然后，只要索引小于向量中指针的数量减1，就取出vector[index]的h_next和v_next，将它们添加到向量的末尾，并执行++index操作。

这样，你就可以在该向量/数组/其他数据结构中获得指向所有树节点的指针。

最后，你只需要遍历它，进行绘制等操作即可。

- Alexey Frunze

---

@MahmoudAl-Qudsi：从概念上讲很容易，但是确实有更好的方法来做到这一点。 - Alexey Frunze

如果我有更多关于cvesq的信息，那么继续下去会更容易...但无论如何，最紧凑的方法是要么使用预先存在的，要么添加h_previous和v_previous，然后迭代到结尾并向后走，而不必存储任何东西。 - Mahmoud Al-Qudsi

@Mahmoud Al-Qudsi：这是一棵树，h_previous和v_previous成员对它有什么意义呢？难道应该将必要的信息存储在节点本身而不是单独的堆栈中吗？ - Konstantin Oznobihin