algorithm - 二叉树的密度

Question

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

Answer 1

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

一个简单的密度测量可以是：

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

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

维基百科有很多关于二叉树的信息。

Answer 2

在二叉树中，每个级别的节点数都在一个值范围内。在级别 0，有 1 个节点，即根；在级别 1 可以有 1 或 2 个节点。在任何级别 k，节点的数量都在 1 到 2k 的范围内。每个级别的节点数有助于树的密度。直观地说，密度是相对于树高的树大小（节点数）的度量。