0

我在这里搜索了这个问题，但没有看到任何关于二叉树优化直径的问题。

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.

编辑:: 请使用父指针查找直径。我知道使用递归找到直径，这是通过找到（左直径，右直径和树的高度）的最大值来完成的

节点结构如下 class Node{ Node left; 节点对；节点父指针；整数数据；

}

4

3 回答 3

1

来自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-19T18:50:32.500 回答
0

请澄清父指针与直径有什么关系。如果将直径定义为任意两个节点之间的最大距离，则与哪个节点是指定的父节点无关。另一方面，如果存在区别，例如父节点是源，其他节点是排水管，那么您可能正在寻找从任何节点到源的最大距离，而不是树的直径。

也就是说，您可以通过运行广度优先搜索 (BFS) 来解决任一问题。如果您正在寻找与专用父节点的距离，请运行 BFS 并用与父节点的距离标记每个节点。

另一方面，如果您正在寻找树直径运行 BFS 两次：第一次从您喜欢的任何节点开始并找到最远的节点；然后从最远的节点开始，找到离它最远的一个。碰巧的是，从“距任何给定节点的最远节点”到“距您刚刚找到的最远节点的最远节点”的距离为您提供了树的直径。

于 2013-08-19T21:40:34.717 回答
0

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

假设我们得到了指向树的任何节点的指针。

在给定节点上执行 BFS（广度优先搜索）并找到与给定节点距离最大的节点。与给定节点距离最大的节点将是叶节点。让我们称之为 node1 现在再次在 node1 上应用 BFS 并找到任何节点到 node1 的最大距离。这个距离就是树的直径。因为 node1 是树的叶子，BFS 找到从 node1（叶子）到树中所有其他节点的最短距离。显然，离 node1 最远的节点将是一片叶子，因此我们将得到树的直径。

于 2014-05-19T22:47:51.837 回答