时间戳

首页 > 解决方案 > 斜二叉树的直径是多少（右斜树的左斜）？

algorithm - 斜二叉树的直径是多少（右斜树的左斜）？

问题描述

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吗？

标签： algorithmdata-structuresbinary-tree

解决方案

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

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

BT中2个叶子节点之间的最长路径

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

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

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

所以至少定义应该是：

BT中2个叶子节点之间最长路径的长度

此外，提供的公式仅给出递归关系，没有基本情况。没有基本情况，这个公式没有定义任何东西。

所以我要强调的是，你在那里有一个非常不稳定的“定义”......

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

  • 沃尔夫拉姆：

    图的图直径是任意两个图顶点之间的“最长最短路径”（即最长图测地线）的长度 [...]

  • 维基百科：

    图的直径是 [...] 任何一对顶点之间的最大距离 [...]。要找到图的直径，首先要找到每对顶点之间的最短路径。这些路径中任何一条的最大长度是图形的直径。

  • 极客极客：

    图的直径是这对顶点之间的最大距离。[...] 解决它的方法是找到所有路径，然后找到所有路径中的最大值。

  • 教程点：

    一个顶点到所有其他顶点之间的所有距离中的最大值被认为是图 G 的直径。

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

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

推荐阅读