我有以下递归算法需要编辑成迭代过程。 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
}
}
我想将这个逻辑重构为迭代算法。 对此有什么建议吗?
最佳答案
要遍历没有递归的节点,您将需要堆栈来保存以前的状态。 [递归实际上也是在使用堆栈...]:
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;
}
}
关于c - 将递归算法重构为迭代算法?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/7608682/