二叉搜尋樹

二叉樹的定義，它的子節點最多有兩個(左節點，右節點)。二叉搜尋樹是二叉樹中一個特殊的存在，它規定所有左側節點的值都小于本節點，所有右側節點的值都大于本節點。二叉搜尋樹對于關鍵值的查找非常快，執行效率是(lg N -- N)。

節點類

插入節點

主要步驟：

建立一個新節點node。

建立三個局部變量parent、temp、isLeft。

因為我們的節點類Node沒有指向父節點的引用，是以這個要有個parent局部變量，temp變量是用來周遊整個樹的，isLeft變量是用标志目前temp是左節點還是右節點。

通過while循環找到新節點就插入的位置。

如果parent為空，表示root為空，新插入的節點作為root節點

如果parent不為空，那麼根據isLeft的值，來決定新節點插入在父節點的左邊還是右邊。

删除節點

對于二叉樹來說，删除一個節點還是比較麻煩的。第一步我們還是有找到這個節點：

周遊樹，找到與要删除的節點，然後調用removeNode方法進行删除操作。

要删除二叉樹的一個節點，分三種情況：

被删除節點沒有子節點，也就是說它是一個子葉節點。那就很簡單了，直接删除這個節點，就是将它的父節點對應它的引用置位null就行了。

被删除節點有一個子節點。

如果被删除節點是父節點的左子節點，那麼它的子節點一定是比父節點小的，直接使用被删除節點子節點取代删除節點就可以了。如果被删除節點是父節點的右子節點，流程一樣。

被删除節點有兩個子節點。

這個時候就比較麻煩了，你删除了本節點後，完全不知道，用哪個子節點取代自己的位置。 根據搜尋二叉樹的定義規則，取代被删除節點的節點，也必須滿足比被删除節點左節點的值都大，比被删除節點右邊的值都小。這個就是它的後繼節點，問題就變為尋找它的後繼結點。 它的後繼節點其實就是它右子節點的最小值，也就是右測最左邊的值。

這個方法就是尋找右側最左邊的值，即後繼節點。

newNode節點用來取代被删除節點，具體的判斷邏輯與前面叙述的一樣。

用遞歸來周遊二叉樹

用棧來周遊二叉樹