一. 二叉樹
二叉樹binary tree是指每個(gè)節(jié)點(diǎn)最多含有兩個(gè)子樹的樹結(jié)構(gòu)。
特點(diǎn)：
1.所有節(jié)點(diǎn)最多擁有兩個(gè)子節(jié)點(diǎn)箕别，即度不大于2
2.左子樹的鍵值小于根的鍵值铜幽，右子樹的鍵值大于根的鍵值。
遍歷
二叉樹的遍歷有三種方式 (簡(jiǎn)記：把根放哪)
（1）前序遍歷（DLR）究孕，首先訪問根結(jié)點(diǎn)啥酱，然后遍歷左子樹爹凹，最后遍歷右子樹厨诸。簡(jiǎn)記根-左-右。
（2）中序遍歷（LDR）禾酱，首先遍歷左子樹微酬，然后訪問根結(jié)點(diǎn)，最后遍歷右子樹颤陶。簡(jiǎn)記左-根-右颗管。
（3）后序遍歷（LRD），首先遍歷左子樹滓走，然后遍歷右子樹垦江，最后訪問根結(jié)點(diǎn)。簡(jiǎn)記左-右-根搅方。
比如上圖二叉樹遍歷結(jié)果
前序遍歷：ABCDEFGHK
中序遍歷：BDCAEHGKF
后序遍歷：DCBHKGFEA
二. 平衡二叉樹
1.符合二叉樹的條件下
2.任何節(jié)點(diǎn)的兩個(gè)子樹的高度最大差為1
如果在avl 樹比吭，中進(jìn)行插入和刪除節(jié)點(diǎn)操作绽族，可能導(dǎo)致avl樹失去平衡，那么可以通過旋轉(zhuǎn)重新達(dá)到平衡衩藤。因此我們說的二叉樹也稱自平衡二叉樹吧慢。
三. 紅黑樹
紅黑樹和avl樹類似，都是在進(jìn)行插入和刪除操作時(shí)通過特定的操作保持二叉樹的平衡赏表，從而獲得較高的查找性能检诗。
特點(diǎn)：
1.節(jié)點(diǎn)是紅色或黑色
2.根節(jié)點(diǎn)是黑色
3.葉子節(jié)點(diǎn)（nil,空節(jié)點(diǎn)）是黑色
4.每個(gè)紅色節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)都是黑色
