必須懂的二元樹公式

1、一般二元樹的性質 

性質1、在非空二元樹的i層上，至多有2^i個結點。 

性質2、高度為K的二元樹中，最多有2^(k 1)-1個結點。 

性質3、對於任何一棵非空的二元樹，若葉結點的個數為n0，度為2的結點個數為n2，則有n0=n2 1。

2、完全二元樹 

定義：若一棵二元樹中，只有最下面的兩層結點度數小於2，其餘各層結點度數都等於2，並且最下面一層的結點，都集中在該層最左邊的若干位置上，則此二元樹稱為完全二元樹。 

性質1、具有n個結點的完全二元樹的高度k為[log^2n]。

性質2、對於具有n個結點的完全二元樹，如果按照從上（根結點）到下(葉結點)和從左到右的順序對二叉樹中的所有結點從0開始到n-1進行編號，則對於任意的下標為i的結點，有： 

#（1）如果i=0，則它是根結點，它沒有父結點；如果i>0,則它的父結點的下標為（i-1）/2。

（2）如果2i 1<=n-1，則下標為i的結點的左子結點的下標為2i 1；否則，下標為i的結點沒有左子結點。

（3）如果2i 2<=n-1，則下標為i的結點的右子結點的下標為2i 2；否則，下標為i的結點沒有右子結點。

3、滿二叉樹 

定義：如果一二叉的任何結點或樹葉，或有兩棵非空子樹，則此二元樹稱為滿二叉樹。 

性質、在滿二元樹中，葉結點的個數比分支結點個數多1。

4、擴充二元樹 

定義：擴充二元樹是對一個已有二元樹的擴充，擴充後原二元樹的結點都變成度數為2的分支結點。也是是說，如果原結點的度數為2，則不變；度數為1，則增加一個分支；度數為0，則增加兩個分支。 

性質1、在擴充二元樹中，外部結點的數量比內部結點的數量多1。 

性質2、對任意擴充二元樹，外部路徑長度E和內部路徑長度I之間滿足以下關係：E=I 2n，其中n是內部結點個數。

更多常見問題的相關技術文章，請造訪常見問題欄位進行學習！

以上是必須懂的二元樹公式的詳細內容。更多資訊請關注PHP中文網其他相關文章！