Binary Tree 三種存儲(chǔ)結(jié)構(gòu)及四種遍歷：先根形导、中根环疼、后根、層序
一朵耕、二叉樹的分類：
- 完全二叉樹：一個(gè)二叉樹的深度為d,除了d層外炫隶，其他各層的節(jié)點(diǎn)數(shù)目均達(dá)到最大值。
滿二叉樹：所有葉節(jié)點(diǎn)都在最底層的完全二叉樹
平衡二叉樹（ALV樹）：當(dāng)且僅當(dāng)任何節(jié)點(diǎn)的兩棵子樹的高度差不大于1的二叉樹阎曹。
排序二叉樹（又稱二叉查找樹伪阶、二叉搜索樹，有序二叉樹）
霍夫曼樹（Huffman Coding又稱哈夫曼樹或最優(yōu)二叉樹）：帶權(quán)路徑最短的二叉樹处嫌≌ぬ霍夫曼編碼使用變長(zhǎng)編碼表對(duì)源符號(hào)進(jìn)行編碼，典型應(yīng)用圖文壓縮熏迹。
紅黑樹檐薯，一種自平衡二叉查找樹（區(qū)分概念：自平衡二叉查找樹，平衡二叉樹ALV）注暗，每個(gè)節(jié)點(diǎn)增加一個(gè)存儲(chǔ)位表示節(jié)點(diǎn)的顏色坛缕，可以是紅或黑（非紅即黑）。
紅黑樹確保沒有一條路徑會(huì)比其它路徑長(zhǎng)出兩倍捆昏，隨著元素個(gè)數(shù)的增加查找性能幾乎是均勻的赚楚。應(yīng)用于jdk中TreeMap和TreeSet 和jdk8的HashMap，nginx的定時(shí)器骗卜。
B樹和B+樹是一種多叉樹宠页。
二、三種表示結(jié)構(gòu)
2.1 順序存儲(chǔ)
順序存儲(chǔ)的缺點(diǎn)在非滿二叉樹的情況下浪費(fèi)空間寇仓，例如極端情況深度為h的二叉樹每個(gè)節(jié)點(diǎn)都只有右孩子举户，該結(jié)構(gòu)需要占用2^h-1的空間，實(shí)際卻占用了h個(gè)節(jié)點(diǎn)焚刺。
String[] arrayBinaryTree = {"A", "B", "C", "D", "E", "F", "G", "#", "I"};
2.2 二叉鏈表存儲(chǔ) 只包含對(duì)左右子節(jié)點(diǎn)的連接指針
class BinaryLinkedListBinaryTree {
private String data;
private BinaryLinkedListBinaryTree leftChild = null;
private BinaryLinkedListBinaryTree rightChild = null;
//…
}
2.3 三叉鏈表存儲(chǔ) 節(jié)點(diǎn)包含對(duì)父節(jié)點(diǎn)和左右子節(jié)點(diǎn)的指針
改進(jìn)于二叉鏈表敛摘，增加父節(jié)點(diǎn)的指引，能更好地實(shí)現(xiàn)節(jié)點(diǎn)間的訪問
public class TripleLinkedListBinaryTree {
private String data;
private TripleLinkedListBinaryTree fatherNode = null;
private TripleLinkedListBinaryTree leftChild = null;
private TripleLinkedListBinaryTree rightChild = null;
//…
}
三乳愉、幾種遍歷(traversal)方式：前序兄淫、中序屯远、后序、層序
針對(duì)前序遍歷捕虽、中序遍歷慨丐、后序遍歷，先左和先右的效率是一樣的泄私，按照習(xí)慣房揭，我們碰到左右排序的時(shí)候一般都采用先左邊后右邊。
3.1 前序遍歷
又稱先根遍歷晌端，按照 ROOT-LEFT-RIGHT 來遍歷.
針對(duì)一顆順序存儲(chǔ)的平衡二叉樹:{"A", "B", "C", "D", "E", "F", "G", "#", "I"}
其先根遍歷結(jié)果是：A B D I E C F G
3.2 中序遍歷
又稱中根遍歷捅暴，遍歷順序： LEFT-ROOT-RIGHT
對(duì)應(yīng)前根遍歷的二叉樹，中根遍歷結(jié)果是：D I B E A F C G
3.3 后續(xù)遍歷
又稱后根遍歷咧纠，遍歷順序： LEFT-RIGHT-ROOT
對(duì)應(yīng)前面的平衡二叉樹蓬痒，其后根遍歷結(jié)果：I D E B F G C A
3.4 層序遍歷
一層一層的遍歷，結(jié)果是：A B C D E F G I
其他：圖的搜索 深度優(yōu)先 Depth-First-Search 廣度優(yōu)先 Breadth-First-Search
- 深度優(yōu)先搜索漆羔，是一種遍歷或搜索圖的算法梧奢，類似于樹遍歷的先根遍歷。
- 廣度優(yōu)先搜索演痒，是一種遍歷或搜索圖的算法亲轨。類似于樹遍歷的層序遍歷。（又作：寬度優(yōu)先搜索鸟顺，橫向優(yōu)先搜索）
