計算二叉樹節點數

Question

是否可以計算有多少個節點有任意的二叉樹？每葉的葉數和深度是已知的（實際上它是霍夫曼樹）。

我需要它以便能夠在實際構建樹之前爲樹分配所需的內存並避免以後的內存重新分配。

Answer 1

霍夫曼樹是full binary tree，即樹中的每個節點都有0或2個孩子。在這種情況下，你需要k個葉子的k - 1個內節點。所以節點的總數是2k - 1。