發現二叉樹

Question

兩個最遙遠的元素我尋找一種算法，能找到一個二叉樹的兩個最遙遠的元素，不找任何特殊的語言，只是算法。

謝謝。

Answer 1

其所謂直徑樹的。

int diameter(Tree * t) // post: return diameter of t 
{ 
    if (t == 0) return 0; 
    int lheight = height(tree->left); 
    int rheight = height(tree->right); 
    int ldiameter = diameter(tree->left); 
    int rdiameter = diameter(tree->right); 
    return max(lheight + rheight + 1, max(ldiameter,rdiameter)); 
} 

alt text http://www.cs.duke.edu/courses/spring00/cps100/assign/trees/diameter.jpg

copied code and images from here。

Answer 2

什麼您正在尋找可命名graph diameter。爲了得到它，你需要計算從任何頂點到其他任何頂點的路徑，然後遍歷所有頂點並找到最大的路徑。
可以使用Dijkstra's algorithm或者通過簡單地distance matrix來實現儘管它會比Dijkstra算法更多的時間（這可通過adjacency matrix供電來實現）。

Answer 3

由於這是一個樹，只有一個任何對頂點之間的路徑。這使我們更容易找到圖形的直徑。

做到這一點，最簡單的方法是通過做樹的兩個簡單的遍歷。首先，使用任意節點作爲根，並使用簡單的DFS/BFS計算每個頂點的距離。現在，取距根最遠的節點（這是距離最遠的一對節點的第一個節點），並將其作爲新根，然後運行另一個樹計算距離的遍歷。距離它最遠的節點是該對中的另一個節點。

爲什麼這項工作的證明留作練習。

還有一個計算通過計算並比較最遠處對用於樹從作爲根（在另一個答案已經提到）的任意節點開始的每個子樹的最遠處的一對的另一種方式。