查找從一個節點到另一個節點的層數

Question

我正在嘗試編寫一個函數，該功能將從四個樹中的一個節點返回到另一個節點的層數。

這裏是我到目前爲止，但我敢肯定，這是不正確的，我只是不能找出原因：

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; 

} 

任何想法？

Answer 1

你的錯誤是您在路徑末路的添加水平，但你需要計算的方式連接兩個節點

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