二叉樹的性質一
在二叉樹的第i層上最多有2^(i-1)個結點(i>=1)
第i層上最多有2^(i-1)個結點(i>=1)
二叉樹的性質二
深度為k的二叉樹最多有2^k-1個結點(k>=1)
注意 這里是2^k再減1
深度為k的二叉樹最多有2^k-1個結點(k>=1)
二叉樹的性質三
對任何一棵二叉樹T，如果其終端結點數為n0叭首，度為2的結點數為n2,則n0=n2+1
推導過程：
- 假設度為1的結點數為n1习勤，則二叉樹T的結點總數為
n=n0+n1+n2 - 其次我們發(fā)現
連接數總數等于總結點數n-1，并且等于``n1+2*n2 - 所以
n-1=n1+2*n2 n0+n1+n2-1=n1+2*n2- 得出結論
n0=n2+1
二叉樹的性質四
具有n個結點的完全二叉樹的深度為?log?n?+1
推導過程:略
二叉樹的性質五
如果對一棵有n個結點的完全二叉樹的結點按層序編號焙格，對任一結點i(1<=i<=n)有以下性質：
- 如果i=1图毕，則結點i是二叉樹的根，無雙親眷唉；如果i>1予颤，則其雙親是結點?i/2?
- 如果2i > n，則結點 i 無做左孩子(結點 i 為葉子結點)冬阳；否則其左孩子是結點2i
- 如果2i+1 > n蛤虐，則結點 i 無右孩子；否則其右孩子是結點2i+1
