偏斜二叉树的直径是多少（左偏或右偏树）？

Question

Diameter of binary tree is defined as:-
  The longest path between 2 leaf nodes in BT.
  let left height=lht, right height=rht,
      left left diameter=ld , right diameter= rd;
  then 
      diameter= max((lht + rht + 1), max (ld,rd));

但是在倾斜树中只有一个叶节点，那么我们如何获得倾斜树的直径。 是0吗？

Answer 1

一棵倾斜的树只有一片叶子，因此在这种情况下不会定义直径，因为它是树的两片叶子之间的最长距离。

Answer 2

如果那是二叉树的直径的定义，那么你显然需要两个叶节点。所以如果这棵树只有一片叶子，根据这个定义，直径是不确定的。

虽然这个定义看起来很可疑，因为它使直径成为 路径:

The longest path between 2 leaf nodes in BT

当然，这甚至与以下内容不一致：

diameter = max((lht + rht + 1), max (ld,rd));

...因为它将直径定义为数字，而不是路径。

所以至少定义应该是：

The length of the longest path between 2 leaf nodes in BT

另外，提供的公式只给出了递归关系，没有给出base case。没有基本情况，这个公式就没有定义任何东西。

所以我要强调你的“定义”非常不稳定...

将此与以下图的直径（不一定是树）的定义进行比较：

• Wolfram:

  The graph diameter of a graph is the length [...] of the "longest shortest path" (i.e., the longest graph geodesic) between any two graph vertices

• Wikipedia:

  The diameter of a graph is [...] the greatest distance between any pair of vertices [...]. To find the diameter of a graph, first find the shortest path between each pair of vertices. The greatest length of any of these paths is the diameter of the graph.

• Geeks for Geeks:

  The diameter of graph is the maximum distance between the pair of vertices. [...] Way to solve it is to find all the paths and then find the maximum of all.

• Tutorials Point:

  The maximum among all the distances between a vertex to all other vertices is considered as the diameter of the Graph G.

这个定义给出的结果与你引用的定义相同，只要它涉及一棵至少有两片叶子的树。但是当树只有一片叶子时，这些定义就不兼容了。根据上述来源的定义，倾斜二叉树的直径将是根与（唯一）叶之间的距离。

边界情况是树只有一个节点，即根。在这种情况下，该图的直径将为 0（根据上面的引述）。