从树上的递归到数组上的迭代（kd-tree Nearest Neighbor）

我有一个递归函数（在树上），我需要使它在没有递归的情况下工作并将树表示为隐式数据结构（数组）。从树上的递归到数组上的迭代（kd-tree Nearest Neighbor）

下面是函数：

kdnode* kdSearchNN(kdnode* here, punto point, kdnode* best=NULL, int depth=0) 
{ 
if(here == NULL) 
    return best; 

if(best == NULL) 
    best = here; 

if(distance(here, point) < distance(best, point)) 
    best = here; 

int axis = depth % 3; 

kdnode* near_child = here->left; 
kdnode* away_child = here->right; 

if(point.xyz[axis] > here->xyz[axis]) 
{ 
    near_child = here->right; 
    away_child = here->left; 
} 

best = kdSearchNN(near_child, point, best, depth + 1); 

if(distance(here, point) < distance(best, point)) 
{ 
    best = kdSearchNN(away_child, point, best, depth + 1); 
} 

return best; 
}

我使用这个属性来代表该树作为数组：

root: 0 
left: index*2+1 
right: index*2+2

enter image description here

这是我做了什么：

punto* kdSearchNN_array(punto *tree_array, int here, punto point, punto* best=NULL, int depth=0, float dim=0) 
{ 
if (here > dim) { 
    return best; 
} 

if(best == NULL) 
    best = &tree_array[here]; 

if(distance(&tree_array[here], point) < distance(best, point)) 
    best = &tree_array[here]; 

int axis = depth % 3; 

int near_child = (here*2)+1; 
int away_child = (here*2)+2; 

if(point.xyz[axis] > tree_array[here].xyz[axis]) 
{ 
    near_child = (here*2)+2; 
    away_child = (here*2)+1; 
} 

best = kdSearchNN_array(tree_array, near_child, point, best, depth + 1, dim); 

if(distance(&tree_array[here], point) < distance(best, point)) 
{ 
    best = kdSearchNN_array(tree_array, away_child, point, best, depth + 1, dim); 
} 

return best; 
}

现在最后一步是摆脱递归，但我找不到任何方法，任何提示？谢谢

来源

2011-03-29 LoRdCoStE

你总是自我复发，所以你可以把你的函数的全部内容包装在一个循环中，并在你想继续搜索的地方，简单地设置新的参数并继续循环？

来源

2011-03-30 07:27:35

从树上的递归到数组上的迭代（kd-tree Nearest Neighbor）

回答

相关问题