一、二叉樹
1律秃、二叉樹的概念
二叉樹是每個節(jié)點(diǎn)最多有兩個子樹的樹結(jié)構(gòu)禀晓。通常子樹被稱作“左子樹”（left subtree）和“右子樹”（right subtree）原环，其次序不能任意顛倒。
2贿条、性質(zhì)
（1）若二叉樹的層次從0開始雹仿，則在二叉樹的第i層至多有2^i個結(jié)點(diǎn)(i>=0)；
（2）高度為k的二叉樹最多有2^(k+1) - 1個結(jié)點(diǎn)(k>=-1)整以。 (空樹的高度為-1)胧辽；
（3）對任何一棵二叉樹，如果其葉子結(jié)點(diǎn)(度為0)數(shù)為m, 度為2的結(jié)點(diǎn)數(shù)為n, 則m = n + 1公黑。
二邑商、幾種特殊的二叉樹
1、滿二叉樹
所有葉結(jié)點(diǎn)同處于最底層（非底層結(jié)點(diǎn)均是內(nèi)部結(jié)點(diǎn)）凡蚜，一個深度為k(>=-1)且有2^(k+1) - 1個結(jié)點(diǎn)人断。如圖（圖來源于veil的博客）：
2、完全二叉樹
葉結(jié)點(diǎn)只能出現(xiàn)在最底層的兩層番刊，且最底層葉結(jié)點(diǎn)均處于次底層葉結(jié)點(diǎn)的左側(cè)含鳞。規(guī)模為n的完全二叉樹，高度為
3芹务、平衡二叉樹
平衡二叉樹（Self-balancing binary search tree）又被稱為AVL樹（有別于AVL算法）蝉绷，且具有以下性質(zhì)：它是一 棵空樹或它的左右兩個子樹的高度差的絕對值不超過1鸭廷，并且左右兩個子樹都是一棵平衡二叉樹。平衡二叉樹的常用實(shí)現(xiàn)方法有紅黑樹熔吗、AVL辆床、替罪羊樹、Treap桅狠、伸展樹等讼载。 最小二叉平衡樹的節(jié)點(diǎn)的公式如下 F(n)=F(n-1)+F(n-2)+1 這個類似于一個遞歸的數(shù)列，可以參考Fibonacci(斐波那契)數(shù)列中跌，1是根節(jié)點(diǎn)咨堤，F(xiàn)(n-1)是左子樹的節(jié)點(diǎn)數(shù)量，F(xiàn)(n-2)是右子樹的節(jié)點(diǎn)數(shù)量漩符。
對于平衡二叉樹要特別注意的是一喘，不要求非葉節(jié)點(diǎn)都有兩個子結(jié)點(diǎn)，僅要求兩個子樹的高度差的絕對值不超過1嗜暴，或者為空樹凸克。
三、存儲方式
存儲的方式和圖一樣闷沥，有鏈表和數(shù)組兩種萎战，用數(shù)組存訪問速度快，但插入舆逃、刪除節(jié)點(diǎn)操作就比較費(fèi)時了蚂维。實(shí)際中更多的是用鏈來表示二叉樹的。
四颖侄、遍歷方式
三種遍歷方式? 訪問節(jié)點(diǎn)的順序是一致的鸟雏，不同之處在于，有的遍歷流程把訪問到的節(jié)點(diǎn)暫存起來览祖，達(dá)成某種條件后再將節(jié)點(diǎn)輸出孝鹊。約定， 根節(jié)點(diǎn)V, 其左孩子為L, 右孩子為R, 那么遍歷順序可以記為：
Pre-Order Traversal ： 到達(dá)一個節(jié)點(diǎn)后展蒂，即刻輸出該節(jié)點(diǎn)的值又活，并繼續(xù)遍歷其左右子樹。?VLR
In-Order Traversal? ：? ?到達(dá)一個節(jié)點(diǎn)后锰悼，將其暫存柳骄，遍歷完左子樹后，再輸出該節(jié)點(diǎn)的值箕般，然后遍歷右子樹LVR
Post-Order Traversal:? ?到達(dá)一個節(jié)點(diǎn)后耐薯，將其暫存，遍歷完左右子樹后，再輸出該節(jié)點(diǎn)的值曲初。?LRV
? ? ? ? 先序遍歷体谒，中序遍歷，后序遍歷臼婆，這個“順序”指的是輸出父節(jié)點(diǎn)的順序抒痒，不是訪問的順序，也不是簡單的按照二叉樹“從左往右”颁褂、“從上往下”等故响。
遍歷結(jié)果：
