**樹 **
是由n（n>=1）個有限節(jié)點組成一個具有層次關(guān)系的集合。
它具有以下特點：
1.每個節(jié)點有零個或多個子節(jié)點俭缓；
2.沒有父節(jié)點的節(jié)點稱為根節(jié)點贸典；
3.每一個非根節(jié)點有且只有一個父節(jié)點 ；
4.除了根節(jié)點外拍鲤，每個子節(jié)點可以分為多個不相交的子樹十性。
Paste_Image.png
二叉樹
二叉樹是每個節(jié)點最多有兩棵子樹的樹結(jié)構(gòu)斤富。
通常子樹被稱作“左子樹”和“右子樹”熊尉。
二叉樹常被用于實現(xiàn)二叉查找樹和二叉堆。
性質(zhì)：
二叉樹的每個結(jié)點至多只有2棵子樹(不存在度大于2的結(jié)點)掌腰，二叉樹的子樹有左右之分狰住，次序不能顛倒。
二叉樹的第i層至多有2^(i-1)個結(jié)點齿梁；
深度為k的二叉樹至多有2^k-1個結(jié)點催植。
滿二叉樹
一棵深度為k，且有2^k-1個節(jié)點的二叉樹稱之為滿二叉樹勺择；
完全二叉樹
深度為k创南，有n個節(jié)點的二叉樹省核，當(dāng)且僅當(dāng)其每一個節(jié)點都與深度為k的滿二叉樹中稿辙，序號為1至n的節(jié)點對應(yīng)時气忠，并且最下層上的結(jié)點都集中在該層最左邊的若干位置上赋咽，稱之為完全二叉樹。
Paste_Image.png
三種遍歷方法
二叉樹主要是由3個基本單元組成吨娜，根節(jié)點脓匿、左子樹和右子樹宦赠。
如果限定先左后右陪毡，那么根據(jù)這三個部分遍歷的順序不同勾扭，可以分為先序遍歷毡琉、中序遍歷和后續(xù)遍歷三種。
先序遍歷：
若二叉樹為空尺借，則空操作绊起，否則先訪問根節(jié)點燎斩，再先序遍歷左子樹虱歪，最后先序遍歷右子樹
中序遍歷:
若二叉樹為空栅表，則空操作，否則先中序遍歷左子樹怪瓶，再訪問根節(jié)點，最后中序遍歷右子樹
后序遍歷:
若二叉樹為空找岖，則空操作，否則先后序遍歷左子樹訪問根節(jié)點许布，再后序遍歷右子樹，最后訪問根節(jié)點蜜唾。
Paste_Image.png
樹與二叉樹的區(qū)別
1.二叉樹每個節(jié)點最多有2個節(jié)點庶艾，樹則無限制
2.二叉樹中節(jié)點的子樹分為左子樹和右子樹，即使某節(jié)點只有一棵樹咱揍，也要指明該子樹是左子樹還是右子樹，即二叉樹是有序的
3.樹絕不能為空，它至少有一個節(jié)點蟹地，而一棵二叉樹可以是空的
二叉查找樹
二叉查找樹就是二叉排序樹藤为，也叫二叉搜索樹。
二叉查找樹或者是一顆空樹缅疟，或者是具有下列性質(zhì)的二叉樹：
1：若左子樹不空，則左子樹上所有節(jié)點的值均小于它的根節(jié)點的值
2：若右子樹不空存淫，則右子樹上所有節(jié)點的值均大于它的根節(jié)點的值
3：左，右子樹也分別為二叉排序樹
4：沒有鍵值相等的節(jié)點
Paste_Image.png
平衡二叉樹
平衡二叉樹又稱AVL樹括授，它或者一顆沒有空樹岩饼，或者是具有下列性質(zhì)的二叉樹：
它的左子樹和右子樹都是平衡二叉樹，且左子樹和右子樹的深度之差的絕對值不超過1
Paste_Image.png
AVL樹是最先發(fā)明的自平衡二叉查找樹算法籍茧。在AVL中任何節(jié)點的兩個兒子子樹的高度最大差別為1，所以它稱為高度平衡樹渴析，n個節(jié)點的AVL樹最大深度約為1.44log2n
查找、插入和刪除在平均和最壞情況下都是O(logn)吮龄。
紅黑二叉樹
紅黑樹是平衡二叉樹的一種俭茧，它保證在最壞情況下基本動態(tài)集合操作的事件復(fù)雜度為O(logn)
紅黑樹和平衡二叉樹區(qū)別如下:
1.紅黑樹放棄了追求完全平衡，追求大致平衡漓帚，在與平衡二叉樹的時間復(fù)雜度相差不大的情況下，保證每次插入最多需要三次旋轉(zhuǎn)就能達(dá)到平衡