代码之家  ›  专栏  ›  技术社区  ›  attwad

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

  •  7
  • attwad  · 技术社区  · 16 年前

    我正在寻找一个算法,可以找到两个最遥远的元素在一个二叉树,不寻找任何特殊的语言,只是为算法。

    谢谢

    3 回复  |  直到 16 年前
        1
  •  10
  •   Glorfindel Doug L.    7 年前

    它叫 树木直径 .

    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

    copied code and images from here

        2
  •  4
  •   Li0liQ    16 年前

    你要找的东西可以命名为 graph diameter . 为了得到它,你需要计算从一个顶点到另一个顶点的路径,然后遍历所有顶点,找到最大的一个。
    Dijkstra's algorithm distance matrix (这可以通过给 adjacency matrix )尽管这比Dijkstra的算法要花更多的时间。

        3
  •  1
  •   MAK    16 年前

    因为这是一棵树,所以任何一对顶点之间只有一条路径。这使我们更容易找到图的直径。

    证明这一点有效的证据被留作练习。

    还有另一种计算最远对的方法,通过计算和比较树的每个子树的最远对,从作为根的任意节点开始(在另一个答案中已经提到)。