Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
1.1k views
in Technique[技术] by (71.8m points)

algorithm - What is the diameter of a tree that doesn't have at least two leaves?

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

  1. the diameter of T's left subtree
  2. the diameter of T's right subtree
  3. the longest path between leaves that goes through the root of T (this can be computed from the heights of the subtrees of T)

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

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?

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

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.


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...