二叉樹的密度

Question

如何找到給定二叉樹的密度？我遇到了這個面試問題，並不確定他們的密度是什麼意思！任何幫助，將不勝感激。

Answer 1

密集二進制樹是接近完美（它有接近2^(h + 1) - 1 nodes)。稀疏樹更接近一個鏈表（它有接近h節點）。h是其中單個根節點的樹的高度身高0.1

密度的簡單的措施可能是：

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

我剛纔提出這個公式了，所以我不知道這是否會適合接受記者採訪時回答您的需求，但它會給你一棵退化的樹和一棵完美的樹，它會給你的數字接近1的密集樹木，a nd數字接近於0的稀疏數字。

Wikipedia有很多關於二叉樹的信息。

Answer 2

在二叉樹中，每個級別的節點數落在一個值範圍內。 在0級，有1個節點，即根;在1級可以有1或2個節點。 在任何級別k，節點的數量在1到2k的範圍內。 每層的節點數對樹的密度有貢獻。直觀地說，密度是樹的大小（節點數量）相對於樹高度的度量。