C語言實作資料結構代碼（三）-樹與二叉樹-二叉樹-二叉樹的定義

目錄

1.1二叉樹的定義

 1.2二叉樹的主要性質

1.3二叉樹的存儲結構

1.3.1 順序存儲結構

1.3.2 鍊式存儲結構

1.1二叉樹的定義

給一般的二叉樹加上兩個限制條件就可以得到二叉樹：

（1）每個結點最多隻有兩顆子樹，即二叉樹中結點的度隻能為0，1，2。

（2）子樹有左右順序之分，不能颠倒。

滿二叉樹	在一棵二叉樹中，所有的分支結點都有左孩子結點和右孩子結點，并且葉子結點都集中在二叉樹的最下一層。例如，圖6-4a就是一顆滿二叉樹。
完全二叉樹	① 對一棵深度為k的滿二叉樹編号。（從上到下，從左至右，從1開始。） ② 對一棵深度為k、有n個結點的二叉樹編号。 ③ 若②中各結點的編号與①中相同位置上結點的編号都相同。      那麼，②中的樹為完全二叉樹。

一棵完全二叉樹是由一棵滿二叉樹，從右至左，從下往上，逐個删除結點所得到的。如果跳着删，則得到的不是完全二叉樹。

 1.2二叉樹的主要性質

性質1：非空二叉樹上葉子結點數等于雙分支結點數+1。

 證明： 1、設二叉樹中葉子結點的個數為 N0，單分支結點的個數為N1，雙分支結點的個數為N2。

                  那麼，總結點的個數= N0+N1+N2。

             2、 在二叉樹中，所有結點的分支數=1*單分支結點的個數 + 2*雙分支結點的個數。

                 即  總分支數=N1+2N2。

             3、 在二叉樹中，除了根節點，每個結點都有一個分支指向它。 即  總分支數=總結點數-1=N0+N1+N2-1。

                （該條結論适用于所有的樹）

             是以，總分支數=N1+2N2=N0+N1+N2-1。

             得出， N0=N2+1。

性質二：二叉樹的第 i 層上最多有 

 （

）個結點。 

結點最多的情況就是滿二叉樹的情況，此時，二叉樹上每一層的結點數就構成了一個

首項為1、公比為2 的等比數列，通項為 

，i為層數。

性質三：高度（深度）為k的二叉樹，最多有 

 (

)  個結點。也就是，滿二叉樹前 k 層的結點個數為 

。

由剛剛性質二中的，等比數列求和可以算出，前k項和為 

。

性質四：完全二叉樹中，某結點的雙親結點、左孩子結點、右孩子結點。

有 n 個結點的完全二叉樹，對各結點從上往下，從左至右，依次編号，編号範圍為 1~n。設 i 為某結點 a 的編号，則：

①  

 ，則 a 雙親結點的編号為  

 。

②  

 ，則 a 的左孩子結點編号為 

 。

 ，則 a 無左孩子結點。

③ 

 ，則 a 的右孩子編号為 

 。

 ，則 a 無右孩子結點。

性質五：函數Catalan()：給定 n 個結點，能構成 h(n) 種不同的二叉樹，

 。

性質六：具有 n (n>=1) 個結點的完全二叉樹的高度（深度）為 

。

1.3二叉樹的存儲結構

1.3.1 順序存儲結構

用一個數組來存儲一棵二叉樹，這種存儲方式最适合于完全二叉樹，存儲一般的二叉樹會浪費大量的存儲空間。

将完全二叉樹中的結點值按照編号依次存入一個一維數組中，就完成了一棵二叉樹的順序存儲。

例如，知道了結點A的下标為1，要得到A的左孩子結點隻需要通路BTree[2*i]即可。

類似的，當知道一個結點的下标為 i 時，若2i <=n ，那麼 i 的左孩子結點就存在BTree[2*i]中。

1.3.2 鍊式存儲結構

data表示資料域，用來存儲對應的資料元素；lchild和rchild分别表示左指針域和右指針域，

分别用于存儲左孩子結點和右孩子結點的位置。

這種結構又稱為二叉連結清單存儲結構。

對應的結點類型定義為：

typedef struct BTNode
{
    char data;
    struct BTNode *lchild;
    struct BTNode *rchild;
}BTNode;