开发者

Find number of levels from one node to another

开发者 https://www.devze.com 2023-02-20 05:28 出处:网络
I\'m trying to write a function that will return the number of levels from one node to the other in a quad tree.

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

精彩评论

暂无评论...
验证码 换一张
取 消