完全二叉樹葉子節點的演算法

1樓：總愛偷懶的貓

設：度為i的結點數為ni，由二叉樹的性質可知：

n0 = n2 + 1………式。

n = n0 + n1 + n2………式。

由①式可得 n2 = n0 - 1，帶入②式得：

n0 = n + 1 - n1）/ 2

由完全二叉樹性質可知：

將兩式合併，寫作：n0 = n+1）/2⌋（向下取整符號不能丟彎氏灶）

2樓：網友

設二叉樹坦跡賣中度為0葉子有n0個，度為1 結點有n1 個，度為2 結點有n2個。

n0 + n1 + n2 = n (1)

按照二叉樹性質：n0 = n2 + 1，也就是n2 = n0 -1於是代入(1) 得：2n0 + n1 - 1 = n按照完全二叉樹性質，度為1 的結點最多1個。

因此當n為偶數時，n1 = 1，因此n0 = n / 2當州蠢n為奇數時，n1 = 0，因此n0 = n + 1)/2合併這兩個結果有：n0 = n + 1)/2 ，實際是整讓逗數除法，也就是下取整。

3樓：匿名使用者

設二叉樹的葉子節點數為n0，度數為2的節點數為n2.設n1為二叉樹中度為1的節點數。因為二叉樹中所有節點的度都釣魚或者等於2，所以二叉樹節點總差悉數n=n0+n1+n2再看二叉樹的分支數，除了根節點外，其餘節點都有乙個分支進侍慶液入，設b為分支總數，則n=b+1。

由於這些分支都是有度為1或者2 的節點射出的，所老物以b=n1+n2;於是有：n=n1+2*n2+1；綜合n=n0+n1+n2和n=n1+2*n2+1兩式即可得到n0=n2+1；完全二叉樹是特殊的二叉樹，對於n0=n2+1當然成立。

4樓：匿名使用者

仔細想想 1 2 4 8完全二叉樹其實就是乙個等比數列嗎這麼一說你應該會推導了吧。

完全二叉樹的葉子節點數公式是什麼？

5樓：阿zi是個好大兒

完全二叉樹的葉子節點數公式為：設葉子節點數為n0, 度為1的節點數為n1，度為2的節點數為n2，總節乎宴點為n。

1、當n為奇數時（即度為1的節點為0個），n0= (n+1)/2。

2、當n為偶數（即度為型滾1的節點為1個）， n0= n/2。

完全二叉樹的性質：1、具有n個結點的完全二叉樹的深度為logn+1。

2、如果對一棵有n個結點的完全二叉樹的結點按層序編號，則對任一結點i，有：

1）如果i=1，則結點i是二叉樹的根節點，無雙親；如果i>1，則其雙親是結點⌊i/2⌋。

2）如果2i>n，則結點i無左孩子；否則其左孩子是結點2i。歲租銀。

3）如果2i+1>n，則結點i無右孩子；否則其右孩子是結點2i+1。