二叉樹
之前介紹的數組、連結清單、棧、隊列 都是線性結構。
二叉樹為樹形結構
一棵樹可以沒有任何節點，稱為空樹。
一棵樹可以隻有一個節點，也就隻有根節點。
節點的度：子樹的個數。
樹的度：所有節點中度中的最大值。
葉子節點：（leaf）度為0的節點。
層數：根節點在第一層，根節點的子節點在第二層，以此類推，（有些資料也從第0層開始）。
節點的深度： 從根節點到目前節點的唯一路徑上的節點總數。
節點的高度： 從目前節點到最遠葉子節點的路徑上的節點總數。
樹的深度 所有節點深度中的最大值
樹的高度：所有節點高度中的最大值
樹的深度等于樹的高度
二叉樹：
每個節點的度最大值為2（最多擁有2棵子樹）
左子樹和右子樹是有順序的
即使某個節點隻有一棵子樹，也要區分左右子樹。
二叉樹中 葉子節點的個數等于度為2的節點個數加一。
真二叉樹：
所有節點的度要麼為0 ，要麼為2。
滿二叉樹：
所有節點的度要麼為0 ，要麼為2，所有的葉子節點都在最後一層。
滿二叉樹屬于真二叉樹。
完全二叉樹：
葉子節點隻會出現在最後兩層，且最後一層的葉子節點都靠左對齊。
完全二叉樹的節點從左到右，從上到下順序排布。
完全二叉樹從根節點到倒數第二層是一棵滿二叉樹。
完全二叉樹的性質：
度為1的節點隻有左子樹。
度為1的節點要麼是1個要個是0個。
總結：
總結點數為n
n如果是偶數
葉子節點數量 n0=n/2
r如果n是奇數
葉子節點數n0=（n+1）/2
n0=floor（（n+1）/2）
因為在程式設計中總是 向下取整 是以： n0=（n+1）/2或者n0=（n+1）>>1
二叉搜尋樹
使用二叉搜尋樹，添加、删除、搜尋的最壞的時間複雜度均可優化至O（logn）
二叉搜尋樹是二叉樹的一種，是一種應用非常廣泛的二叉樹，英文簡稱BST。
特點：
任意一個節點的值都大于其左子樹 所有節點的值。
任意一個節點的值都小于其右子樹所有節點的值
它的左右子樹也是一棵二叉搜尋樹。
可以大大提高搜尋效率
接口設計：
二叉樹的周遊
前序周遊通路順序：
根節點，前序周遊左子樹、前序周遊右子樹。
中序周遊通路順序：
中序周遊左子樹、根節點、中序周遊右子樹。
後序周遊通路順序：
後序周遊左子樹、後序通路右子樹、根節點。
層序周遊通路順序：
從上到下、從左到右依次通路每一個節點。
層序周遊：
周遊的應用
二叉搜尋樹的複雜度：
添加搜尋删除元素的時間複雜度和二叉樹的高度有關，O(h)==O(logn)
平衡：
當節點數量固定是，左右子樹高度越接近，這顆二叉樹就越平衡
理想平衡：像完全二叉樹和滿二叉樹一樣高度是最小的
AVL樹
AVL樹是最早發明的自平衡二叉搜尋樹之一。
平衡因子：某節點的左右子樹高度差。（左子樹高度-右子樹高度）
AVL樹特點：
每個節點的左右子樹高度差隻可能是1 、0、-1；
每個節點的左右子樹高度差不超過1
添加、搜尋删除的時間複雜度是O（logn）.
繼承關系：AVL樹可以設計為從二叉搜尋樹繼承而來。
添加、删除元素時會使二叉樹失衡
添加元素導緻的失衡：
解決辦法：
1.LL(LEFT-LEFT)情況：右旋轉（單旋）
（LL表示g、p、n的走勢）
2.RR情況：-左旋轉（單旋）
3.LR情況：先左旋轉變為LL情況、再右旋轉（雙旋）。
4.RL情況 先右旋轉變為RR情況，再左旋轉（雙旋）。
删除元素導緻的失衡：