I'm trying to write a function that will return the number of levels from one node to the other in a quad tree.
Here's what I have so far, but I'm sure it's incorrect, I just cant figure out why:
int levels(QtreeNode * orig, QtreeNode * n) {
//calculates the number of levels from orig to n
if(orig开发者_高级运维==n)
return 0;
if(!orig->isLeaf())
return 1 + levels(orig->nwChild, n) + levels(orig->neChild, n) + levels(orig->swChild, n)+ levels(orig->seChild, n);
return 0;
}
Any ideas?
your mistake is that you add levels on path to dead end's, but you need to calc way linked that two nodes
int levels(QtreeNode * orig, QtreeNode * n)
{
int path;
// found!
if (orig == n)
return 0;
// it's dead end, do not calc that way
if (orig->isLeaf())
return -1;
path = levels(orig->nwChild, n);
// not dead end? it's fine, return that path
if (path >= 0)
return 1 + path;
path = levels(orig->neChild, n);
// not dead end? it's fine, return that path
if (path >= 0)
return 1 + path;
path = levels(orig->swChild, n);
// not dead end? it's fine, return that path
if (path >= 0)
return 1 + path;
path = levels(orig->seChild, n);
// not dead end? it's fine, return that path
if (path >= 0)
return 1 + path;
// there is no path between this nodes
return -2;
}
精彩评论