在二叉树中找到两个最远的元素

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

从这里复制代码和图像.