1.定義

二叉樹（Binary Tree）是另一種樹型結構。 ? ?

二叉樹的特點：

1）每個結點至多只有兩棵子樹（即二叉樹中不存在度大于2的結點）；

2）二叉樹的子樹有左右之分，其次序不能任意顛倒。 ? ?

二叉樹的遞歸定義 ?

二叉樹(BinaryTree)是n(n≥0)個結點的有限集。它或者是空集(n=0)，或者同時滿足以下兩個條件：?

(1) 有且僅有一個根結點； ?

(2) 其余的結點分成兩棵互不相交的左子樹和右子樹。

二叉樹的抽象數據類型 ? ADT BinaryTree { ?D、R、P ? }

?二叉樹與樹有區別：樹的子樹沒有順序，但如果二叉樹的根結點只有一棵子樹，必須明確區分它是左子樹還是右子樹，因為兩者將構成不同形態的二叉樹。因此，二叉樹不是樹的特例。它們是兩種不同的數據結構。

二叉樹有5種基本形態：

2.性質

性質1：若二叉樹的層次從1開始, 則在二叉樹的第 i 層最多有 2i-1 個結點。(i ? 1)

性質2：深度為k的二叉樹至多有2k-1個結點（k>0）。

性質3：對于任何一棵二叉樹，若度2的結點數有n2個，葉子結點數為n0，則n0=n2+1。

特例：

1）滿二叉樹：深度為k且有 2k-1個結點的二叉樹。

特點：每一層上的結點數都是最大結點數。滿二叉樹不存在度數為1的節點，且樹葉都在最下一層。可以對滿二叉樹的結點進行連續編號。

2）完全二叉樹：深度為k，有n個結點的二叉樹，當且僅當其每一個結點都與深度為k的滿二叉樹中編號從1至n 的結點一一對應時，稱之為完全二叉樹。

特點:

（1）葉子結點只可能在層次最大的兩層上出現； ? ? ? ? ? ? ?

（2）對任一結點，若其右分支下的子孫的最大層次為h，則其左分支下的子孫的最大層次數必為h或h+1。

對于特殊性質的二叉樹，還具備以下2個性質：

性質4：具有n個結點的完全二叉樹的深度必為log2n＋1。

性質5：如果對一棵有n個結點的完全二叉樹(其深度為log2n＋1)的結點按層序編號，則對任一結點i（1≤i≤n），有：

1）如果i=1，則結點i是二叉樹的根，無雙親；如果i>1，則其雙親parent（i）是結點?i/2 ； ? ? ? ?

2）如果2i>n，則結點i無左孩子(結點i為葉子結點)；否則其 左孩子lchild（i）是結點2i； ? ? ? ?

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

3.存儲結構

1.順序存儲結構

?二叉樹的順序存儲，是采用一組連續的存儲單元來存放二叉樹中的結點，但是，由于二叉樹是非線性結構，所以結點之間的邏輯關系難以從存儲的先后確定。不過，由二叉樹的性質5可知，對于完全二叉樹，如果按照從上（根結點）到下（葉結點）和從左到右的順序，對二叉樹中的所有結點從0到n-1編號，這樣存放到一維數組中。只要通過數組元素的下標關系，就可以確定二叉樹中結點之間的邏輯關系。

#define  MAXSIZE  100	
typedef  int  ElemType;	
typedef struct wqbtree
{ElemType SequenBiTree[MAXSIZE];int n;		/*記錄節點總數*/
}Fbitree;

對于一般的二叉樹，如果仍采用順序表示，首先要對它進行擴充，增加一些并不存在的空結點，使之成為一棵完全二叉樹，然后再用一維數組順序存儲。

缺點：浪費存儲空間。

完全二叉樹用順序存儲結構，一般二叉樹用鏈式存儲結構。

2.鏈表存儲結構

1.二叉鏈表

由于二叉樹每個結點至多只有2個孩子，分別為左孩子和右孩子。因此可以把每個結點分成三個域：一個域存放結點本身的信息，另外兩個是指針域，分別存放指向左、右孩子的指針。每個結點的結構表示為：

typedef  int  ElemType;	
typedef struct BiTreeNode
{ 	ElemType data;struct BiTreeNode *lchild, *rchild;
}BiTreeNode, *BiTree;

一個二叉鏈表由根指針root唯一確定。若二叉樹為空，則root=NULL；若結點的某個孩子不存在，則相應的指針為空。?

具有n個結點的二叉鏈表中，共有2n個指針域。其中只有n-1個用來指示結點的左、右孩子，其余的n+1個指針域為空。

?若一個二叉樹含有n個結點，則它的二叉鏈表中必含有2n個指針域， 其中必有n＋1個空的鏈域。

2.三叉鏈表

為了便于找到結點的雙親，可以在結點結構中增加一個指向其雙親結點的指針域，此時二叉鏈表變為三叉鏈表。 三叉鏈表的結點結構

typedef  int  ElemType;
typedef struct ThrTreeNode{ElemType data;struct ThrTreeNode  *lchild, *rchild，*parent；
}ThrTreeNode, *ThrTree;