查找樹的直徑，如果對於每個節點，給出父指針

我在這裏搜索了這個問題，但是看不到任何關於優化二叉樹直徑的問題。查找樹的直徑，如果對於每個節點，給出父指針

How do we find diameter of a binary tree if parent pointer to each node is given. 

Definition of tree diameter is : Longest distance between two nodes of tree.

編輯::請使用父指針找到直徑。我知道使用遞歸發現直徑，並且通過找到的最大（直徑左樹，右邊直徑和高度）進行

節點結構如下類節點{ 節點離開; 節點正確; 節點parentPointer; int數據;

}

來源

2013-08-19 AKS

你是什麼意思，父指針給出？你有一張所有葉子的清單嗎？這不是一個非常合乎邏輯的數據結構... –

請說明父指針與直徑有什麼關係。如果將直徑定義爲任何兩個節點之間的最大距離，而不是與哪個節點是指定的父節點無關。另一方面，如果有一個區別，例如父節點是源，而其他節點是漏極，那麼您可能正在尋找從任何節點到源的最大距離，而不是樹的直徑。

也就是說，您可以通過運行廣度優先搜索（BFS）來解決任何一個問題。如果您正在尋找與專用父級運行BFS的距離，並用距父級的距離標記每個節點。

另一方面，如果您正在尋找樹直徑運行BFS兩次：第一次從您喜歡的任何節點開始，找到最遠的節點;然後從最遠的節點開始，找到距離它最遠的節點。恰巧從「最遠節點到任何給定節點」到「最遠節點距離你剛找到的最遠節點」的距離給你樹的直徑。

來源

2013-08-19 21:40:34 Michael

這從geeksforgeeks代碼顯示如何計算的二進制時間的直徑在爲O（n）。

但是，不需要父指針，所以也許我誤解了你的問題？

/*The second parameter is to store the height of tree. 
    Initially, we need to pass a pointer to a location with value 
    as 0. So, function should be used as follows: 

    int height = 0; 
    struct node *root = SomeFunctionToMakeTree(); 
    int diameter = diameterOpt(root, &height); */ 
int diameterOpt(struct node *root, int* height) 
{ 
    /* lh --> Height of left subtree 
     rh --> Height of right subtree */ 
    int lh = 0, rh = 0; 

    /* ldiameter --> diameter of left subtree 
     rdiameter --> Diameter of right subtree */ 
    int ldiameter = 0, rdiameter = 0; 

    if(root == NULL) 
    { 
    *height = 0; 
    return 0; /* diameter is also 0 */ 
    } 

    /* Get the heights of left and right subtrees in lh and rh 
    And store the returned values in ldiameter and ldiameter */ 
    ldiameter = diameterOpt(root->left, &lh); 
    rdiameter = diameterOpt(root->right, &rh); 

    /* Height of current node is max of heights of left and 
    right subtrees plus 1*/ 
    *height = max(lh, rh) + 1; 

    return max(lh + rh + 1, max(ldiameter, rdiameter)); 
}

來源

2013-08-19 18:50:32

對不起，我應該提到這個問題，必須使用父指針。我現在編輯了這個問題。 – AKS

那麼，你可以使用父指針來重建O（n）中的左和右指針，然後使用原始算法？ –

http://leisurehours.wordpress.com/2009/07/18/find-the-diameter-of-a-tree/

假設我們被賦予指針樹的任何節點。

在給定節點上執行BFS（寬度優先搜索）並查找與給定節點距離最大的節點。與給定節點距離最大的節點將是一個葉節點。讓我們稱之爲node1 現在再次在node1上應用BFS，並找到node1中任何節點的最大距離。這個距離是樹的直徑。因爲node1是樹的一個葉子，BFS找到從node1（葉子）到樹中所有其他節點的最短距離。顯然離節點1最遠的節點將是一片葉子，因此我們將得到樹的直徑。

來源

2014-05-19 22:47:51 user3654493

查找樹的直徑，如果對於每個節點，給出父指針

回答

相關問題