樹的定義
樹是n（n>=0）個(gè)元素的的有限集合淋淀。在任何一顆非空樹中：
- 有且僅有一個(gè)節(jié)點(diǎn)被稱為根節(jié)點(diǎn)，在整棵樹最上面
- 當(dāng) n>1時(shí)朵纷，除根節(jié)點(diǎn)以外的其他節(jié)點(diǎn)可被分為 m(m>0)個(gè)互不相交的有限集合T1...Tn袍辞，其中每個(gè)集合本身又是一顆樹，并且稱為根的子數(shù)搅吁。
樹的相關(guān)術(shù)語
- 節(jié)點(diǎn)：樹中的數(shù)據(jù)元素稱為節(jié)點(diǎn)谎懦，每個(gè)節(jié)點(diǎn)都保存了該節(jié)點(diǎn)的信息，即數(shù)據(jù)元素和數(shù)據(jù)項(xiàng)與數(shù)據(jù)元素之間的關(guān)系
- 節(jié)點(diǎn)的度：節(jié)點(diǎn)擁有子樹的個(gè)數(shù)
二叉樹
樹型結(jié)構(gòu)中有一種特殊的樹叫做二叉樹吸申，二叉樹的結(jié)構(gòu)也比較簡單享甸，規(guī)律性較強(qiáng)，并且可以證明日丹，即使一般的樹也能轉(zhuǎn)化成二叉樹蚯嫌。而且許多實(shí)際問題抽象出來的數(shù)據(jù)結(jié)構(gòu)往往就是二叉樹的形式。
二叉樹的定義
二叉樹是個(gè)有限元素的集合，該集合為空或者由一個(gè)根和兩個(gè)互不相交的左子樹和右子樹組成。在二叉樹中诫硕，一個(gè)元素也稱為一個(gè)節(jié)點(diǎn)。
二叉樹基本特征
- 每個(gè)節(jié)點(diǎn)最多只有兩棵子樹，即不存在度大于 2 的節(jié)點(diǎn)
- 左子樹和右子樹次序不能顛倒摩瞎，即二叉樹是有序樹孝常，而且哪怕只有
一顆子樹，也要區(qū)分是左子樹還是右子樹上渴。
二叉樹的 5 種基本形態(tài)
- 空集
- 根有兩顆子樹
- 根只有一顆子樹（左子樹或右子樹）
- 根沒有子樹
二叉樹的性質(zhì)
- 在二叉樹的第 i 層上至多有 **2^(i-1) **個(gè)結(jié)點(diǎn) (i>0)
一棵深度為 k 的二叉樹中，最多有 2^k-1 個(gè)結(jié)點(diǎn)
具有 n 個(gè)結(jié)點(diǎn)的完全二叉樹的深度 k 為 [log2n]+1
對于一棵非空的二叉樹曹阔，如果葉子結(jié)點(diǎn)數(shù)為 n0隔披，度為 2 的結(jié)點(diǎn)數(shù)為 n2，
則 n0 = n2+1-
對于具有n個(gè)節(jié)點(diǎn)的完全二叉樹抓韩，如果按照從上至下和從左至右的順序?qū)Χ鏄渲兴薪Y(jié)點(diǎn)進(jìn)行從1的編號鬓长，則對于任意的序號為i結(jié)點(diǎn)，有:
如果 i>1彪薛，則序號為 i 的結(jié)點(diǎn)的雙親結(jié)點(diǎn)為 i/2怠蹂，如果 i==1少态，則序號為 i 的結(jié)點(diǎn)是根節(jié)點(diǎn)，無雙親結(jié)點(diǎn)
如果 2i<=n嫌佑，則序號為i的結(jié)點(diǎn)的左孩子節(jié)點(diǎn)的序號為 2i侨歉，否則i結(jié)點(diǎn)無左孩子
如果 2i+1<=n，則序號為i的結(jié)點(diǎn)的右孩子節(jié)點(diǎn)的序號為 2i炮温，否則i結(jié)點(diǎn)無右孩子注意：性質(zhì) 1,2,4 所有二叉樹都通用牵舵，性質(zhì) 3,5 只有完全二叉樹適用
二叉樹的存儲結(jié)構(gòu)
- 順序存儲結(jié)構(gòu)
- 鏈?zhǔn)酱鎯Y(jié)構(gòu)
順序存儲結(jié)構(gòu)
一組連續(xù)的存儲單元依次從上至下，從左至右存儲二叉樹上的節(jié)點(diǎn)元素担巩。對于完全二叉樹來說没炒，樹中結(jié)點(diǎn)的序號都是按照從上至下，從左至右進(jìn)行編排的拳话，所以結(jié)點(diǎn)的序號可以唯一的反映節(jié)點(diǎn)之間的邏輯關(guān)系（性質(zhì)5）
存儲在數(shù)組中，數(shù)組下標(biāo)從零開始
| 數(shù)組下標(biāo) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| 數(shù)據(jù) | A | B | C | D | E | F | G | H | I |
如果是一般的二叉樹的話胚鸯，如果我在對他進(jìn)行從上至下姜钳，從左至右進(jìn)行編號時(shí)就不能很好的反映數(shù)組元素之間的關(guān)系了形耗，如果我們進(jìn)行適當(dāng)?shù)母脑欤ㄟ^添加一些結(jié)點(diǎn)拟糕，把他補(bǔ)成一顆完全二叉樹倦踢，那么再進(jìn)行編號，就可以進(jìn)行順序存儲了
| 數(shù)組下標(biāo) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 數(shù)據(jù) | A | B | C | D | E | 0 | 0 | 0 | 0 | 0 | F |
此可以看出犁嗅，這樣的存儲方式晤碘，會造成很多空間的浪費(fèi)园爷，而且如果要進(jìn)行對樹上元素進(jìn)行刪除、插入操作需要移動(dòng)大量的數(shù)據(jù)元素童社，因此二叉樹不宜采用順序存儲結(jié)構(gòu)
二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)
用類似于鏈表的存儲方法來存儲樹上元素的邏輯關(guān)系扰楼，即用指針來表示元素之間的邏輯關(guān)系
data 是數(shù)據(jù)域，leftChild 和 rightChild 是指針域十艾，leftChild 是指向左兒子的指針腾节，rightChild 是指向右兒子的指針荤牍，當(dāng)左兒子或右兒子為空時(shí)庆冕，相應(yīng)的指針域也為空
代碼描述
//存儲的數(shù)據(jù)類型
typedef char DataType
typedef struct node
{
DataType data; //數(shù)據(jù)域
struct node* leftChild; //左兒子
struct node* rightChild; //右兒子
}BinNode;
typedef BinNode* BinTree;
這是二叉鏈表的定義，除此之外還有三叉鏈表晦嵌，三叉鏈表比起二叉鏈表多了一個(gè)指向雙親結(jié)點(diǎn)的指針域拷姿，如圖所示
代碼描述
//存儲的數(shù)據(jù)類型
typedef char DataType
typedef struct node
{
DataType data; //數(shù)據(jù)域
struct node* leftChild; //左兒子
struct node* rightChild; //右兒子
struct node* parent; //雙親
}BinNode;
typedef BinNode* BinTree;
在二叉樹中有兩種特殊的二叉樹 >>> 滿二叉樹和完全二叉樹
滿二叉樹
在一棵樹中所有的分支節(jié)點(diǎn)都存在左子樹和右子樹响巢，并且所有的葉子節(jié)點(diǎn)都在同一層上，這樣的二叉樹稱為滿二叉樹踪古。
完全二叉樹
一棵深度為 k 且具有 n 個(gè)節(jié)點(diǎn)的二叉樹伏穆，對樹中節(jié)點(diǎn)按從上至下，從左至右的順序進(jìn)行編號陪腌，當(dāng)且僅當(dāng)節(jié)點(diǎn)都與深度為 k 的滿二叉樹中編號從 1 至 n 的節(jié)點(diǎn)一一對應(yīng)
時(shí)铡原，才稱這棵二叉樹為完全二叉樹商叹。顯然滿二叉樹也是完全二叉樹的一種。
完全二叉樹的特點(diǎn)：
- 葉子節(jié)點(diǎn)只可能在層次最大的兩層上出現(xiàn)
- 對任一節(jié)點(diǎn)卵洗，其右分支下的兒子的最大層次為 h弥咪，則其左分支下的兒子最大層次為 h 或 h+1
