二叉樹的定義
二叉樹也稱為二分樹，它是有限的結點集合，這個集合或者是空，或者由一個根結點和兩棵互不相交的稱為左子樹和右子樹的二叉樹組成。
二叉樹中許多概念與樹中的概念相同。
在含n個結點的二叉樹中，所有結點的度小於等於2，通常用n0表示葉子結點個數，n1表示單分支結點個數，n2表示雙分支結點個數。
度為2的樹至少有3個結點，而二叉樹的結點數可以為0。
度為2的樹不區分子樹的次序，而二叉樹中的每個結點最多有兩個孩子結點，且必須要區分左右子樹，即使在結點只有一棵子樹的情況下也要明確指出該子樹是左子樹還是右子樹。
歸納起來，二叉樹的5種形態：
二叉樹抽象資料型別的描述
滿二叉樹和完全二叉樹
在一棵二叉樹中，如果所有分支結點都有左孩子結點和右孩子結點，並且葉子結點都集中在二叉樹的最下一層，這樣的二叉樹稱為滿二叉樹。
可以對滿二叉樹的結點進行層序編號，約定編號從樹根為1開始，按照層數從小到大、同一層從左到右的次序進行。
滿二叉樹也可以從結點個數和樹高度之間的關係來定義，即一棵高度為h且有2h-1個結點的二叉樹稱為滿二叉樹。
滿二叉樹的特點如下：
葉子結點都在最下一層。
只有度為0和度為2的結點。
含n個結點的滿二叉樹的高度為log2(n+1)，葉子結點個數為n/2+1，度為2的結點個數為n/2。
若二叉樹中最多隻有最下面兩層的結點的度數可以小於2，並且最下面一層的葉子結點都依次排列在該層最左邊的位置上，則這樣的二叉樹稱為完全二叉樹。
同樣可以對完全二叉樹中每個結點進行層序編號，編號的方法同滿二叉樹相同，圖中每個結點外邊的數字為對該結點的編號。
完全二叉樹的特點如下：
葉子結點只可能出現在最下面兩層中。
對於最大層次中的葉子結點，都依次排列在該層最左邊的位置上。
如果有度為1的結點，只可能有一個，且該結點只有左孩子而無右孩子；
按層序編號後，一旦出現某結點（其編號為i）為葉子結點或只有左孩子，則編號大於i的結點均為葉子結點。
二叉樹性質
性質1 非空二叉樹上葉結點數等於雙分支結點數加1。即n0=n2+1。
證明：
總結點數n=n0+n1+n2。
一個度為1的結點貢獻1個度，一個度為2的結點貢獻2個度，所以總的度數=n1+2n2。
總的度數=總分支數=n-1。
則n1+2n2=n0+n1+n2-1，求出n0=n2+1。
性質2 非空二叉樹上第i層上至多有2i-1個結點，這裡應有i≥1。
由樹的性質2可推出。
性質3 高度為h的二叉樹至多有2h-1個結點（h≥1）。
由樹的性質3可推出。
性質4 完全二叉樹（結點個數為n）層序編號後的性質。
（1）若完全二叉樹的根結點編號為1，對於編號為i（1≤i≤n）的結點有：
若i≤n/2，即2i≤n，則編號為i的結點為分支結點，否則為葉子結點，也就是說，最後一個分支結點的編號為n/2。
若n為奇數，則n1=0，每個分支結點都是雙分支結點；若n為偶數，則n1=1，只有一個單分支結點。
若編號為i的結點有左孩子結點，則左孩子結點的編號為2i；若編號為i的結點有右孩子結點，則右孩子結點的編號為2i+1。
若編號為i的結點有左兄弟結點，左兄弟結點的編號為i-1，若有右兄弟結點，右兄弟結點的編號為i+1。
若編號為i的結點有雙親結點，其雙親結點的編號為i/2。
（2）若完全二叉樹的根結點編號為0，對於編號為i（0≤i≤n-1）的結點有：
若i≤n/2-1，則編號為i的結點為分支結點，否則為葉子結點，也就是說，最後一個分支結點的編號為n/2-1。
若n為奇數，則n1=0，每個分支結點都是雙分支結點；若n為偶數，則n1=1，只有一個單分支結點。
若編號為i的結點有左孩子結點，則左孩子結點的編號為2i+1；若編號為i的結點有右孩子結點，則右孩子結點的編號為2i+2。
若編號為i的結點有左兄弟結點，左兄弟結點的編號為i-1，若有右兄弟結點，右兄弟結點的編號為i+1。
若編號為i的結點有雙親結點，其雙親結點的編號為(i-1)/2。
性質5 具有n個（n＞0）結點的完全二叉樹的高度為log2(n+1)或log2n+1。
由完全二叉樹的定義和樹的性質3可推出。
一棵含有882個結點的二叉樹中有365個葉子結點，求度為1的結點個數和度為2的結點個數。
解：這裡n=882，n0=365。
由二叉樹的性質1可知n2=n0-1=364。
n=n0+n1+n2，即n1=n-n0-n2=882-365-364=153。
所以該二叉樹中度為1的結點和度為2的結點個數分別是153和364。
一棵完全二叉樹中有501個葉子結點，則至少有多少個結點。
解：該二叉樹中有，n0=501。
由二叉樹性質1可知n0=n2+1，所以n2=n0-1=500。
n=n0+n1+n2=1001+n1，由於完全二叉樹中n1=0或n1=1，則n1=0時結點個數最少，此時n=1001，即至少有1001個結點。
二叉樹的順序儲存結構
順序儲存一棵二叉樹時，就是用一組連續的儲存單元存放二叉樹中的結點。
由二叉樹的性質4可知，對於完全二叉樹（或滿二叉樹），樹中結點層序編號可以唯一地反映出結點之間的邏輯關係，所以可以用一維陣列按從上到下、從左到右的順序儲存樹中所有結點值，透過陣列元素的下標關係反映完全二叉樹或滿二叉樹中結點之間的邏輯關係。
一棵完全二叉樹的順序儲存結構
或者
一般的二叉樹 的順序儲存結構
或者
二叉樹順序儲存結構採用字串（假設每個結點值為單個字元）或者列表（陣列）存放。
當二叉樹中某結點為空結點或無效結點（不存在該編號的結點）時，對應位置的值用特殊值（如'#'）表示。
完全二叉樹或滿二叉樹採用順序儲存結構比較合適
如果需要增加很多空結點才能將一棵二叉樹改造成為一棵完全二叉樹，採用順序儲存結構會造成空間的大量浪費，這時不宜用順序儲存結構。
二叉樹的鏈式儲存結構
二叉樹的列表儲存結構
每個結點為"[結點值，左子樹列表，右子樹列表]"的三元組，當左或者右子樹為空時取值None。型別如下：
二叉樹的遞迴演算法設計
對於二叉樹b，設f(b)是求解的"大問題"。
f(b->lchild)和f(b->rchild)為"小問題"。
假設f(b->lchild)和f(b->rchild)是可求的，在此基礎上得出f(b)和f(b->lchild)、f(b->rchild)之間的關係，從而得到遞迴體。
再考慮b=NULL或只有一個結點的特殊情況，從而得到遞迴出口。
二叉樹的基本運算及其實現
二叉樹類設計
二叉樹的基本運算演算法實現
（1）設定二叉樹的根結點SetRoot(b)
（2）求二叉鏈的括號表示串DispBTree()
（3）查詢值為x的結點FindNode(x)
設f(t，x)在以t為根結點的二叉樹中查詢值為x的結點，找到後返回其地址，否則返回None。
（4）求高度Height()
設以t為根結點二叉樹的高度為f(t)，空樹高度為0，非空樹高度為左、右子樹中較大的高度加1。