查找樹的直徑

Question

我已經編寫了查找二叉樹直徑的代碼。但我無法弄清楚它出錯的地方。我寫的兩個函數及其定義如下： -

int btree::diameteroftree(node* leaf) 
    { 
    if (leaf==NULL) 
    return 0; 

    int lheight = hieghtoftree(leaf->left); 
    int rheight = hieghtoftree(leaf->right); 

    int ldiameter = diameteroftree(leaf->left); 
    int rdiameter = diameteroftree(leaf->right); 

    return max(lheight + rheight + 1,max(ldiameter,rdiameter)); 
    } 


    int btree::hieghtoftree(node* leaf) 
    { 
    int left=0,right=0; 
    if(leaf==NULL) 
    return -1; 
    else 
    { 
    left=hieghtoftree(leaf->left); 
    right=hieghtoftree(leaf->right); 
    if(left > right) 
    return left +1; 
    else 
    return right+1; 
    } 
    } 

我無法弄清楚我在哪裏出錯了。有人可以讓我知道......

Answer 1

您想要返回最長路徑上的節點數量。因此，在你的算法問題是這一行：

return max(lheight + rheight + 1,max(ldiameter,rdiameter)); 

其中

rootDiameter = lheight + rheight + 1 

是路徑的從左邊樹到右樹的節點最深最深節點的長度。但是，這個計算是不正確的。單個節點返回0的高度，所以不會被計數。你有兩個選擇：

1. 變化hieghtoftree返回節點的數量最深的路徑，而不是「跳」
2. 解決這個問題，在您的總和

的數量。

return max(lheight + rheight + 3,max(ldiameter,rdiameter)); 

Answer 2

在一個定向的，有根的樹中，任何一對節點之間總是最多有一條路徑，並且任何節點的最長路徑總是從根開始。由此可見，diameter僅僅是整個樹height(root)的高度，可以用遞歸

height(leaf) = 0 
height(node) = max(height(node.left), height(node.right)) + 1 

編輯來計算：您的評論鏈接到網頁描述了無向樹的直徑。你需要一個不同的樹形表示，例如一個鄰接矩陣。

Answer 3

考慮具有根R和2個葉L1，L2的3節點樹。然後heightoftree（L1）== heightoftree（L2）== -1。因此Diameteroftree（R）將是（-1）+（ - 1）+1 = -1？！？

我建議返回-1; - > return 0; and return max（lheight + rheight + 1，max（ldiameter，rdiameter））; - > return max（lheight + rheight + 2，max（ldiameter，rdiameter））;

結果將是路徑上的邊數。如果您計算節點的數量，則根據您的需要添加一個或從最終結果中減去一個。