介紹二叉樹(shù)之前先說(shuō)下樹(shù)狀結(jié)構(gòu)恒序，不同于線性結(jié)構(gòu)只有前后兩個(gè)方向，樹(shù)狀結(jié)構(gòu)可以有多個(gè)方向谁撼。
樹(shù)的基本概念
節(jié)點(diǎn)歧胁、根節(jié)點(diǎn)、父節(jié)點(diǎn)厉碟、子節(jié)點(diǎn)喊巍、兄弟節(jié)點(diǎn)
如上圖中的每個(gè)元素都一個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)A是根節(jié)點(diǎn)墨榄，A是B和C的父節(jié)點(diǎn)玄糟，B和C是A的子節(jié)點(diǎn)，B和C互相是兄弟節(jié)點(diǎn)袄秩；一棵樹(shù)可以沒(méi)有任何節(jié)點(diǎn)阵翎，稱為空樹(shù)
一棵樹(shù)可以只有一個(gè)節(jié)點(diǎn)逢并，即只有根節(jié)點(diǎn)
子樹(shù)、左子樹(shù)郭卫、右字樹(shù)
如上圖中砍聊，子樹(shù)B是A的左子樹(shù)，子樹(shù)C是A的右子樹(shù)節(jié)點(diǎn)的度
子樹(shù)的個(gè)數(shù)贰军，等于節(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)樹(shù)的度
所有節(jié)點(diǎn)度中的最大值葉子節(jié)點(diǎn)
度為0的節(jié)點(diǎn)非葉子節(jié)點(diǎn)
度不為0的節(jié)點(diǎn)層數(shù)
根節(jié)點(diǎn)在第一層玻蝌，根節(jié)點(diǎn)的子節(jié)點(diǎn)在第二次，依次往下類推節(jié)點(diǎn)的深度
從根節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)唯一路徑上的節(jié)點(diǎn)總數(shù)節(jié)點(diǎn)的高度
從當(dāng)前節(jié)點(diǎn)到最遠(yuǎn)葉子節(jié)點(diǎn)的路徑上的節(jié)點(diǎn)總數(shù)樹(shù)的深度
所有節(jié)點(diǎn)深度中的最大值樹(shù)的高度
所有節(jié)點(diǎn)高度中的最大值樹(shù)的深度等于樹(shù)的高度
有序樹(shù)
樹(shù)中任意節(jié)點(diǎn)的子節(jié)點(diǎn)之間有順序關(guān)系無(wú)序樹(shù)
樹(shù)中任意節(jié)點(diǎn)之間沒(méi)有順序關(guān)系词疼，也稱“自由樹(shù)”森林
有n(n ≥0)課互不相交的樹(shù)組成的集合
二叉樹(shù)(BinaryTree)
每個(gè)節(jié)點(diǎn)的度最大為2俯树，左子樹(shù)和右子樹(shù)是有序的，即使只有一顆子樹(shù)也要區(qū)分左右的樹(shù)是二叉樹(shù)贰盗；
二叉樹(shù)的性質(zhì)
- 非空二叉樹(shù)的第i層许饿，最多有
個(gè)節(jié)點(diǎn)（i>=1）
- 高度為h的二叉樹(shù)上最多有
個(gè)節(jié)點(diǎn)（h>=1）
- 對(duì)于任意一課非空二叉樹(shù)，如果葉子節(jié)點(diǎn)個(gè)數(shù)為n0舵盈，度為2的節(jié)點(diǎn)數(shù)為n2
- 若度為1的節(jié)點(diǎn)數(shù)為n1陋率，二叉樹(shù)的總結(jié)點(diǎn)數(shù)n = n0 + n1 + n2
- 二叉樹(shù)的總邊數(shù)T = n1 + 2*n2 = n - 1 = n0 + n1 + n2 -1，因此 n0 = n2 + 1
真二叉樹(shù)
所有節(jié)點(diǎn)的度要么為0秽晚，要么為2的二叉樹(shù)稱為真二叉樹(shù)瓦糟；
滿二叉樹(shù)
最后一層節(jié)點(diǎn)的度為0，其他節(jié)點(diǎn)的度都為2的二叉樹(shù)稱為滿二叉樹(shù)赴蝇；
完全二叉樹(shù)
對(duì)一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)按層編號(hào)菩浙，如果編號(hào)為i(1<=i<=n)的結(jié)點(diǎn)與同樣深度的滿二叉樹(shù)中編號(hào)為i的結(jié)點(diǎn)在二叉樹(shù)中位置完全相同，則這棵二叉樹(shù)稱為完全二叉樹(shù)
葉子節(jié)點(diǎn)只會(huì)出現(xiàn)最后兩層扯再，最后一層的葉子節(jié)點(diǎn)都靠左對(duì)齊的二叉樹(shù)
從根節(jié)點(diǎn)至倒數(shù)第二層是一棵滿二叉樹(shù)
滿二叉樹(shù)一定是完全二叉樹(shù)芍耘，完全二叉樹(shù)不一定是滿二叉樹(shù)
度為1的節(jié)點(diǎn)只有左子樹(shù)
度為1的節(jié)點(diǎn)要么是1個(gè)，要么是0個(gè)
同樣節(jié)點(diǎn)數(shù)量的二叉樹(shù)熄阻，完全二叉樹(shù)的高度最小
假設(shè)完全二叉樹(shù)的高度為h(h≥1)，那么
至少有個(gè)節(jié)點(diǎn)(
+
+···+
+ 1)
最多有- 1個(gè)節(jié)點(diǎn)(
若總結(jié)點(diǎn)數(shù)為n
< h => h = floor(
一棵有n個(gè)節(jié)點(diǎn)的完全二叉樹(shù)(n>0)秃殉，從上到下、從左到右對(duì)節(jié)點(diǎn)從1開(kāi)始進(jìn)行編號(hào)浸剩，對(duì)任意第i個(gè)節(jié)點(diǎn)
若i=1钾军，它是根節(jié)點(diǎn)
若i>1,它的父節(jié)點(diǎn)編號(hào)是floor(i/2)
若2i≤n，它的左子節(jié)點(diǎn)編號(hào)為2i
若 2i＞n绢要，它無(wú)左子節(jié)點(diǎn)
若2i+1 ≤n吏恭，它的右子節(jié)點(diǎn)編號(hào)為2i+1
若2i+1 ＞n，它無(wú)右子節(jié)點(diǎn)
從圖中可以看到重罪，對(duì)于節(jié)點(diǎn)i樱哼，它的左子節(jié)點(diǎn)等于2i哀九，右子節(jié)點(diǎn)等于2i+1；
