計算特定級別二叉堆中的節點數

Question

我們有一個由2016節點組成的二叉堆。

Decompositing成二進制我們得到

11111100000 

堆與節點512 256 128 64 32和16

但我們如何能夠計算某些級別的節點的數目由6期應激？什麼是計算數字和什麼節點在例如3級的公式？

是否有任何這方面的最終解決方案？謝謝

Answer 1

術語「二叉樹」來自這樣一個事實，即在n階二叉樹中，給定任意整數0，在該級別的二叉樹中恰好有n個選擇k個節點。正如您在問題中提到的那樣，您可以通過使用相關數字的二進制表示來確定哪些樹將出現在二項堆中。因此，如果你有一個快速的計算方法n選擇k（使用查找表或其他方法），你可以通過查看n中設置的一個位來確定二叉堆中第k級的節點數並且對於每組1位，計算該單獨樹中的節點數量，然後將結果相加在一起。