二叉樹的簡單介紹以及二叉樹的存儲結構
什麼是二叉樹？
二叉樹是每個節點最多有兩個子樹的樹結構。通常子樹被稱作“左子樹”（left subtree）和“右子樹”（right subtree）。
二叉樹的每個結點至多隻有二棵子樹(不存在度大于2的結點)，二叉樹的子樹有左右之分，次序不能颠倒。二叉樹的第i層至多有2^{i-1}個結點（頂層為第一層）；深度為k的二叉樹至多有2^k-1個結點，一棵深度為k，且有2^k-1個節點稱之為滿二叉樹；深度為k，有n個節點的二叉樹，當且僅當其每一個節點都與深度為k的滿二叉樹中，序号為1至n的節點對應時，稱之為完全二叉樹。二叉樹常被用于實作二叉查找樹和二叉堆。
二叉樹是遞歸定義的，其結點有左右子樹之分，邏輯上二叉樹有五種基本形态：
(1)空二叉樹——如圖(a)；
(2)隻有一個根結點的二叉樹——如圖(b)；
(3)隻有左子樹——如圖(c)；
(4)隻有右子樹——如圖(d)；
(5)完全二叉樹——如圖(e)。
二叉樹的術語：
樹的結點：包含一個資料元素及若幹指向子樹的分支；
孩子結點：結點的子樹的根稱為該結點的孩子；
雙親結點：B 結點是A 結點的孩子，則A結點是B 結點的雙親；
兄弟結點：同一雙親的孩子結點； 堂兄結點：同一層上結點；
祖先結點: 從根到該結點的所經分支上的所有結點子孫結點：以某結點為根的子樹中任一結點都稱為該結點的子孫
結點層：根結點的層定義為1；根的孩子為第二層結點，依此類推；
樹的深度：樹中最大的結點層
結點的度：結點子樹的個數
樹的度： 樹中最大的結點度。
葉子結點：也叫終端結點，是度為 0 的結點；
分枝結點：度不為0的結點；
有序樹：子樹有序的樹，如：家族樹；
無序樹：不考慮子樹的順序；
二叉樹的主要性質
1.一顆非空二叉樹的第i層上最多有2i-1個結點(i>=1)。
2.一顆深度為k的二叉樹中，最多具有2k-1個結點。
3.對于一顆非空二叉樹，如果葉子結點樹為n0，度數為2的二叉樹結點為n2,則有n0=n2+1;
4.具有n個結點的完全二叉樹的深度k為[log2n]+1。
二叉樹的存儲結構
二叉樹是非線性結構，即每個資料結點至多隻有一個前驅，但可以有多個後繼。
它可采用順序存儲結構和鍊式存儲結構。而鍊式存儲結構有可以分為二叉連結清單存儲結構、 三叉連結清單存儲結構（帶雙親指針的二叉連結清單存儲結構）
1．順序存儲結構
二叉樹的順序存儲，就是用一組連續的存儲單元存放二叉樹中的結點。是以，必須把二叉樹的所有結點安排成為一個恰當的序列，結點在這個序列中的互相位置能反映出結點之間的邏輯關系，用編号的方法從樹根起，自上層至下層，每層自左至右地給所有結點編号,缺點是有可能對存儲空間造成極大的浪費，在最壞的情況下，一個深度為k且隻有k個結點的右單支樹需要2k-1個結點存儲空間。依據二叉樹的性質，完全二叉樹和滿二叉樹采用順序存儲比較合适，樹中結點的序号可以唯一地反映出結點之間的邏輯關系，這樣既能夠最大可能地節省存儲空間，又可以利用數組元素的下标值确定結點在二叉樹中的位置，以及結點之間的關系。圖5-5(a)是一棵完全二叉樹，圖5-5（b）給出的圖5-5(a)所示的完全二叉樹的順序存儲結構。
(a) 一棵完全二叉樹 (b) 順序存儲結構
圖5-5 完全二叉樹的順序存儲示意圖
對于一般的二叉樹，如果仍按從上至下和從左到右的順序将樹中的結點順序存儲在一維數組中，則數組元素下标之間的關系不能夠反映二叉樹中結點之間的邏輯關系，隻有增添一些并不存在的空結點，使之成為一棵完全二叉樹的形式，然後再用一維數組順序存儲。如圖5-6給出了一棵一般二叉樹改造後的完全二叉樹形态和其順序存儲狀态示意圖。顯然，這種存儲對于需增加許多空結點才能将一棵二叉樹改造成為一棵完全二叉樹的存儲時，會造成空間的大量浪費，不宜用順序存儲結構。最壞的情況是右單支樹，如圖5-7 所示，一棵深度為k的右單支樹，隻有k個結點，卻需配置設定2k－1個存儲單元。
(a) 一棵二叉樹 (b) 改造後的完全二叉樹
(c) 改造後完全二叉樹順序存儲狀态
圖5-6 一般二叉樹及其順序存儲示意圖
(a) 一棵右單支二叉樹 (b) 改造後的右單支樹對應的完全二叉樹
(c) 單支樹改造後完全二叉樹的順序存儲狀态
圖5-7 右單支二叉樹及其順序存儲示意圖
結構5-1二叉樹的順序存儲
1 #define Maxsize 100 //假設一維數組最多存放100個元素
2 typedef char Datatype; //假設二叉樹元素的資料類型為字元
3 typedef struct
4 { Datatype bt[Maxsize];
5 int btnum;
6 }Btseq; 2．二叉鍊式存儲結構
二叉樹的鍊式存儲結構是指，用連結清單來表示一棵二叉樹，即用鍊來訓示元素的邏輯關系。
通常的方法是連結清單中每個結點由三個域組成，資料域和左右指針域，左右指針分别用來給出該結點左孩子和右孩子所在的鍊結點的存儲位址。其結點結構為：
其中，data域存放某結點的資料資訊；lchild與rchild分别存放指向左孩子和右孩子的指針，當左孩子或右孩子不存在時，相應指針域值為空（用符号∧或NULL表示）。利用這樣的結點結構表示的二叉樹的鍊式存儲結構被稱為二叉連結清單，如圖5-8所示。
(a) 一棵二叉樹 (b) 二叉連結清單存儲結構
圖5-8 二叉樹的二叉連結清單表示示意圖
3．三叉連結清單存儲結構
為了友善通路某結點的雙親，還可以給連結清單結點增加一個雙親字段parent,用來指向其雙親結點。每個結點由四個域組成，其結點結構為：
這種存儲結構既便于查找孩子結點，又便于查找雙親結點；但是，相對于二叉連結清單存儲結構而言，它增加了空間開銷。利用這樣的結點結構表示的二叉樹的鍊式存儲結構被稱為三叉連結清單。
圖5-9給出了圖5-8 (a)所示的一棵二叉樹的三叉連結清單表示。
圖5-9二叉樹的三叉連結清單表示示意圖
盡管在二叉連結清單中無法由結點直接找到其雙親，但由于二叉連結清單結構靈活，操作友善，對于一般情況的二叉樹，甚至比順序存儲結構還節省空間。是以，二叉連結清單是最常用的二叉樹存儲方式。
結構5-2二叉樹的鍊式存儲
#define datatype char //定義二叉樹元素的資料類型為字元
typedef struct node //定義結點由資料域，左右指針組成
{ Datatype data;
struct node *lchild,*rchild;
}Bitree;