二叉樹
定義：二叉樹是最多只有兩個節(jié)點的樹石咬，二叉樹具有唯一根節(jié)點花颗。
二叉樹的特點：
1、二叉樹每個節(jié)點最多有兩個孩子筐骇；
2债鸡、二叉樹每個節(jié)點最多有一個父親。
二分搜索樹
二分搜索樹特點：
1铛纬、二分搜索樹的每個節(jié)點的值厌均，大于其左子樹的所有節(jié)點的值；小于其右子樹的所有節(jié)點的值告唆；
2棺弊、每一顆子樹也是二分搜索樹。
源碼分析：
????首先擒悬，二分搜索樹的泛型必須是實現(xiàn)了 Comparable 的模她，即可以比較的。屬性 Node 有三個變量懂牧，類似于LinkedList侈净。記錄著當前節(jié)點的值，左右節(jié)點僧凤。
向二分搜索樹中添加元素 add(E e)：
????采用遞歸方式——遞歸的終止條件：最后一步是遞歸到最后一個根元素 NULL畜侦，此時將新節(jié)點放入該位置；遞歸的步驟：這里要根據(jù)當前節(jié)點的值和 e 的大小躯保，來判斷走左右子樹旋膳。然后遞歸函數(shù)add(node.left , e) 或者 add(node.right, e)。
查找元素 contains(E e):
和 add 類似的遞歸操作途事，只是查找元素不需要賦值验懊。
遞歸終止條件：1、走到最后一個節(jié)點 NULL盯孙，還沒找到鲁森；2、找到了元素 E振惰。
遞歸操作：依舊是根據(jù)當前節(jié)點的值和 e 的大小歌溉，來判斷走左右子樹的遞歸。
遍歷二分搜索樹——前序遍歷
前序遍歷（又稱深度優(yōu)先遍歷骑晶，即會優(yōu)先走完左子樹痛垛，然后往回走）：先根節(jié)點，再左右分支桶蛔。
遞歸終止條件：走到最后一個節(jié)點 NULL匙头。
遞歸操作：分別從左右兩邊開始遞歸。
遍歷二分搜索樹——中序遍歷
中序遍歷：左分支——> 根節(jié)點 ——> 右分支仔雷。
遍歷二分搜索樹——后序遍歷
后序遍歷：左芬子——> 右分支——> 根節(jié)點蹂析。
遍歷結果分析
只有中序遍歷有明顯的特征舔示，即可以自然排序。
????每個根節(jié)點都會遍歷三次电抚，圖中 1,2,3 點惕稻。1 點代表該根節(jié)點第一次訪問；2 點代表左子樹走完之后（走到最后一步左 NULL 節(jié)點返回）蝙叛，再次訪問該根節(jié)點俺祠；3 點表示右子樹走完之后（走到最后一步右 NULL 節(jié)點返回），再次訪問該節(jié)點借帘。
????對于前序遍歷來說蜘渣，走到1 點就會輸出；中序遍歷肺然，走到2 點才會輸出蔫缸；后序遍歷，走到 3點才會輸出际起。并且捂龄，遍歷的順序是左子樹到右子樹。
前序遍歷結果：即執(zhí)行1 號點的輸出順序加叁，28 16 13 22 30 29 42倦沧；
中序遍歷結果：即執(zhí)行2 號點的輸出順序，13 16 22 28 30 29 42它匕；
后序遍歷結果：即執(zhí)行3 號點的輸出順序展融，13 22 16 29 42 30 28；
二分搜索樹其他遍歷擴展：
????二分搜索樹的前序遍歷（深度優(yōu)先遍歷）豫柬，非遞歸實現(xiàn)：由于前序遍歷的順序是 根節(jié)點——> 左子樹 ——> 右子樹告希，并且輸出是在第一次訪問節(jié)點時。于是可以使用棧烧给，來記錄節(jié)點的訪問順序燕偶，因為棧是后進先出的，于是必須先壓入右節(jié)點再壓入左節(jié)點础嫡。
? ? 二分搜索樹的層序遍歷：按層遍歷指么。
層序遍歷的輸出結果為： 28 16 30 13 22 29 42；
查找二分搜索樹的最大值和最小值：
????思路分析：因為二分搜索樹的左子樹是小于根節(jié)點的榴鼎，右子樹是大于跟節(jié)點的伯诬，于是最小值是在左子樹的最左邊節(jié)點（node.left == null）；最大值在右子樹的最右邊那個節(jié)點（node.right == null）巫财。
刪除二分搜索樹的最小值或者最大值：
????思路分析：刪除最小值時盗似，找到左子樹的最左節(jié)點（最小值節(jié)點，node.left == null）平项，然后讓其上一個節(jié)點的左節(jié)點指向當前最小值節(jié)點的右子樹赫舒，同時刪除最小值節(jié)點（node.right = null）悍及；刪除最大值時，找到右子樹的最右節(jié)點（最大值節(jié)點接癌，node.right == null）并鸵，然后讓其上一個節(jié)點的右節(jié)點指向當前最大值節(jié)點的左子樹，同時刪除最大值節(jié)點（node.left = null）扔涧。
刪除二分搜索樹的任意節(jié)點：
????思路分析：當刪除的元素沒有左子樹（node.left == null）或者沒有右子樹（node.right == null），這個邏輯跟刪除最小值和最大值時一樣的届谈；當刪除的元素有左右子樹枯夜，則需要采用后繼或者前驅策略（本案例采用后繼策略，前驅類似）艰山。
后繼：使用比當前需要刪除的元素的值大的且最近的節(jié)點湖雹，替換當前需要刪除的元素，即使用當前需要刪除的節(jié)點的右子樹的最小值曙搬；
前驅：使用比當前需要刪除的元素的值小的且最近的節(jié)點摔吏，替換當前需要刪除的元素，即使用當前需要刪除的節(jié)點的左子樹的最大值纵装；
時間復雜度分析：
對于鏈表結構征讲，add、contains橡娄、remove操作都需要遍歷元素诗箍，即是O(n)的時間復雜度；對于二分搜索樹來說挽唉，如果是滿二叉樹的情況滤祖，上面的操作都是O(h)的時間復雜度，其中 h 為樹的高度瓶籽，并且 h = log n匠童，所以時間復雜度為O(log n)；但是如果二叉樹的元素在一邊塑顺，即 h = n汤求，則時間復雜度跟鏈表結構是一樣的，為 O(n)严拒。
