发现二叉树

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计算每个顶点的距离。现在，取距根最远的节点（这是距离最远的一对节点的第一个节点），并将其作为新根，然后运行另一个树计算距离的遍历。距离它最远的节点是该对中的另一个节点。

为什么这项工作的证明留作练习。

还有一个计算通过计算并比较最远处对用于树从作为根（在另一个答案已经提到）的任意节点开始的每个子树的最远处的一对的另一种方式。