algorithm - 二叉树的密度

Question

如何找到给定二叉树的密度？我遇到了这个面试问题，但不确定密度是什么意思!任何帮助将不胜感激。

Answer 1

密集的二叉树接近完美(它有接近 2^(h + 1) - 1 个节点)。稀疏树更接近链表(它有接近 h 个节点)。 h 是单个根节点高度为 0 的树的高度。

密度的简单度量可以是:

(n - h)/(2^(h + 1) - h - 1)

我刚刚制定了这个公式，所以我不知道它是否适合您对面试答案的需求，但它会为退化树提供 0 分，为完美树提供 1 分。对于密集的树，它会给出接近 1 的数字，对于稀疏的树，它会给出接近 0 的数字。

Wikipedia有很多关于二叉树的资料。