没有至少两片叶子的树的直径是多少? [英] What is the diameter of a tree that doesn't have at least two leaves?

问题描述

一棵树的直径T是以下数量中的最大值:

The diameter of a tree T is the largest of the following quantities:

1. T的左子树的直径
2. T的右子树的直径
3. 通过T的根的叶子之间的最长路径(这可以根据T的子树的高度来计算)

来源: https://www2.cs.duke.edu/courses/spring00/cps100/assign/trees/diameter.html

但是，它没有说没有至少两片叶子的树的直径是多少，例如仅根树或1->.2?是0，未定义，无穷大还是负无穷大?

However, it doesn't say what is the diameter of tree that doesn't have at least two leaves, like a root-only tree, or 1 -> 2? Is it 0, undefined, infinity or negative infinity?

推荐答案

更好的直径定义是最长路径的长度".仅根树的直径为0，并且两个顶点上的路径的直径为1.给定的规则是不必要地".复杂，但这是因为它们还提供了一种计算直径的方法.另外，请注意，在图论的意义上，如果根缺少其子代中的所有子代，则是本身就是一片叶子，因此您可以看到第三个子句实际上涵盖了问题案例.

A better definition of diameter is simply "the length of the longest path". The root only tree has diameter 0, and the path on two vertices has diameter 1. The rules given are "unnecessarily" complicated, but that's because they also give a way to calculate the diameter. Also, note that, in a graph theoretic sense, if the root is missing all or all but one of its children, it is a leaf itself, and so you can see the third clause as actually covering the problem cases.

这篇关于没有至少两片叶子的树的直径是多少?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！