摘要：在數據結構領域對應樹結構來說二叉樹是最常用的一種樹結構，二叉樹具有一個唯一的根節點，也就是最上面的節點。二叉樹每個節點最多有兩個孩子，一個孩子都沒有的節點通常稱之為葉子節點，二叉樹每個節點最多有一個父親，根節點是沒有父親節點的。

【從蛋殼到滿天飛】JAVA 數據結構解析和算法實現，全部文章大概的內容如下：
Arrays(數組)、Stacks(棧)、Queues(隊列)、LinkedList(鏈表)、Recursion(遞歸思想)、BinarySearchTree(二分搜索樹)、Set(集合)、Map(映射)、Heap(堆)、PriorityQueue(優先隊列)、SegmentTree(線段樹)、Trie(字典樹)、UnionFind(并查集)、AVLTree(AVL 平衡樹)、RedBlackTree(紅黑平衡樹)、HashTable(哈希表)

源代碼有三個：ES6（單個單個的 class 類型的 js 文件） | JS + HTML（一個 js 配合一個 html）| JAVA (一個一個的工程)

全部源代碼已上傳 github，點擊我吧，光看文章能夠掌握兩成，動手敲代碼、動腦思考、畫圖才可以掌握八成。

本文章適合 對數據結構想了解并且感興趣的人群，文章風格一如既往如此，就覺得手機上看起來比較方便，這樣顯得比較有條理，整理這些筆記加源碼，時間跨度也算將近半年時間了，希望對想學習數據結構的人或者正在學習數據結構的人群有幫助。

線性數據結構是把所有的數據排成一排

樹結構是倒立的樹，由一個根節點延伸出很多新的分支節點。

樹結構本身是一個種天然的組織結構

如 電腦中文件夾目錄結構就是樹結構

這種結構來源于生活，

比如 圖書館整體分成幾個大館，

如 數理館、文史館等等，

到了數理館還要分成 很多的子類，

如 數學類的圖書、物理類的圖書、化學類的圖書，計算機類的圖書，

到了計算機類的圖書還要再分成各種不同的子類，

如 按語言分類 c++、java、c#、php、python 等等，

如 按領域分類 網站編程、app 開發、游戲開發、前端、后端等等，

每一個子領域可能又要分成很多領域，

一直到最后索引到一本一本的書，

這就是一個典型的樹結構。

還有 一個公司的組織架構也是這樣的一種樹結構，

從 CEO 開始下面可能有不同的部門，

如財務部門(Marketing Head)、人事部門(HR Head)、

技術部門(Finance Head)、市場部門(Audit Officer)等等，

每個部門下面還有不同的職能分工，最后才到具體的一個一個人。

還有家譜，他本身也是一個樹結構，

其實樹結構并不抽象，在生活中隨處可見。

樹結構非常的高效

比如文件管理，

不可能將所有的文件放到一個文件夾中，

然后用一個線性的結構進行存儲，

那樣的話查找文件太麻煩了，

但是如果給它做成樹機構的話，

那么就可以很容易的檢索到目標文件，

比如說我想檢索到我的照片，

直接找到個人文件夾，然后找到圖片文件夾，

最后找到自己的照片，這樣就很快速很高效的找到了目標文件。

在公司使用這種樹形的組織架構也是這個原因，

CEO 想就技術開發的一些問題進行一些討論，

他肯定要找相應職能的一些人，

他不需要去市場部門、營銷部門、人事部門、財務部門、行政部門找人，

他直接去技術部這樣的開發部門去找人就好了，

一下子就把查詢的范圍縮小了。

在數據結構領域設計樹結構的本質也是如此。

在計算機科學領域很多問題的處理

當你將數據使用樹結構進行存儲后，出奇的高效。

二分搜索樹（Binary Search Tree）

二分搜索樹有它的局限性

平衡二叉樹：AVL;紅黑樹，

平衡二叉樹還有很多種

算法需要使用一些特殊的操作的時候將數據組織成樹結構

會針對某一類特殊的操作產生非常高效的結果，

使用堆以及并查集，

都是為了滿足對數據某一個類特殊的操作進行高效的處理，

同時對于某些特殊的數據，很多時候可以另辟蹊徑，

將他們以某種形式存儲成樹結構，

結果就是會對這類特殊的數據

它們所在的那個領域的問題

相應的解決方案提供極其高效的結果。

線段樹、Trie(字典樹、前綴樹)

線段樹主要用來處理線段這種特殊的數據，

Trie 主要用于處理字符串這類特殊的數據，

要想實現快速搜索的算法，

它的本質依然是需要使用樹結構的，

樹結構不見得是顯式的展示在你面前，

它同時也可以用來處理很多抽象的問題，

這就像棧的應用一樣，

從用戶的角度看只看撤銷這個操作或者只看括號匹配的操作，

用戶根本想不到這背后使用了一個棧的數據結構，

但是為了組建出這樣的功能是需要使用這種數據結構的，

同理樹也是如此，很多看起來非常高效的運算結果，

它的背后其實是因為有樹這種數據結構作為支撐的，

這也是數據結構、包括數據結構在計算機科學領域非常重要的意義，

數據結構雖然解決的是數據存儲的問題，

但是在使用的層面上不僅僅是因為要存儲數據，

更重要的是在你使用某些特殊的數據結構存儲數據后，

可以幫助你輔助你更加高效的解決某些算法問題

甚至對于某些問題來說如果沒有這些數據結構，

那么根本無從解決。

二叉樹

和鏈表一樣，也屬于動態數據結構，

不需要創建這個數據結構的時候就定好存儲的容量，

如果要添加元素，直接 new 一個新的空間，

然后把它添加到這個數據結構中，刪除也是同理，

每一個元素也是存到一個節點中，

這個節點和鏈表不同，它除了要存放這個元素 e，

它還有兩個指向其它節點的變量，分別叫做 left、right，

   class Node {
      E e;
      Node left;
      Node right;
   }

二叉樹也叫多叉樹，

它每一個節點最多只能分成兩個叉，

根據這個定義也能定義出多叉樹，

如果每個節點可以分出十個叉，

那就可以叫它十叉樹，能分多少叉就叫多少叉樹，

Trie 字典書本身就是一個多叉樹。

在數據結構領域對應樹結構來說

二叉樹是最常用的一種樹結構，

二叉樹具有一個唯一的根節點，

也就是最上面的節點。

每一個節點最多有兩個子節點，

這兩個子節點分別叫做這個節點的左孩子和右孩子，

子節點指向左邊的那個節點就是左孩子，

子節點指向右邊的那個節點就是右孩子。

二叉樹每個節點最多有兩個孩子，

一個孩子都沒有的節點通常稱之為葉子節點，

二叉樹每個節點最多有一個父親，

根節點是沒有父親節點的。

二叉樹和鏈表一樣具有天然遞歸的結構

鏈表本身是線性的，

它的操作既可以使用循環也可以使用遞歸。

和樹相關的很多操作，

使用遞歸的方式去寫要比使用非遞歸的方式簡單很多。

二叉樹每一個節點的左孩子同時也是一個二叉樹的根節點，

通常叫管這棵二叉樹做左子樹。

二叉樹每一個節點的右孩子同時也是一個二叉樹的根節點，

通常叫管這棵二叉樹做右子樹。

也就是說每一個二叉樹它的左側和右側右分別連接了兩個二叉樹，

這兩個二叉樹都是節點個數更小的二叉樹，

這就是二叉樹所具有的天然的遞歸結構。

二叉樹不一定是“滿”的

滿二叉樹就是除了葉子節點之外，

每一個節點都有兩個孩子。

就算你整個二叉樹上只有一個節點，

它也是一個二叉樹，只不過它的左右孩子都是空，

這棵二叉樹只有一個根節點，

甚至 NULL(空)也是一棵二叉樹。

就像鏈表中，只有一個節點它也是一個鏈表，

也可以把 NULL(空)看作是一個鏈表。

二分搜索樹是一棵二叉樹

在二叉樹定義下所有其它的術語在二分搜索樹中也適用，

如 根節點、葉子節點、左孩子右孩子、左子樹、右子樹、

父親節點等等，這些在二分搜索樹中也一樣。

二分搜索樹的每一個節點的值

都要大于其左子樹的所有節點的值，

都要小于其右子樹的所有節點的值。

在葉子節點上沒有左右孩子，

那就相當于也滿足這個條件。

二分搜索樹的每一棵子樹也是二分搜索樹

對于每一個節點來說，

它的左子樹所有的節點都比這個節點小，

它的右子樹所有的節點都比這個節點大，

那么用二分搜索樹來存儲數據的話，

那么再來查找一個數據就會變得非常簡單，

可以很快的知道從左側找還是右側找，

甚至可以不用看另外一側，

所以就大大的加快了查詢速度。

在生活中使用樹結構，本質也是如此，

例如我要找一本 java 編程的書，

那么進入圖書館我直接進入計算機科學這個區域找這本書，

其它的類的圖書我根本不用去管，

這也是樹這種結構存儲數據之后再對數據進行操作時

才能夠非常高效的核心原因。

為了能夠達到二分搜索樹的性質

必須讓存儲的元素具有可比較性，

你要定義好 元素之間如何進行比較，

因為比較的方式是具有多種的，

必須保證元素之間可以進行比較。

在鏈表和數組中則沒有這個要求，

這個就是二分搜索樹存儲數據的一個局限性，

也說明了凡事都是有代價的，

如果想加快搜索的話就必須對數據有一定的要求。

二分搜索樹其實不是支持所有的類型

所以應該對元素的類型有所限制，

這個限制就是 這個類型必須擁有可比較性，

所以在 java 里面的表示就是 對泛型進行約束，

泛型 E 必須滿足 Comparable，

也就是這個類型 E 必須具有可比較性。

代碼實現

   public class MyBinarySearchTree> {

         private class Node {
             public E e;
             public Node left, right;

             public Node (E e) {
                   this.e = e;
                   left = null;
                   right = null;
             }
         }

         private Node root;
         private int size;

         public MyBinarySearchTree () {
               root = null;
               size = 0;
         }

         public int getSize() {
               return size;
         }

         public boolean isEmpty () {
               return size == 0;
         }
   }

如果二分搜索樹的根節點為空的話

第一個添加的元素就會成為根節點，

如果再添加一個元素，那么就因該從根節點出發，

根據二分搜索樹的定義，

每個節點的值要比它的左子樹上所有節點的值大，

假設第二個添加的元素的值小于第一個添加的元素的值，

那么很顯然第二個添加的元素要被添加到根節點的左子樹上去，

根節點的左子樹上只有一個節點，

那么這個節點就是左子樹上的根節點，

這個左子樹上的根節點就是頂層根節點的左孩子。

按照這樣的規則，每來一個新元素從根節點開始，

如果小于根節點，那么就插入到根節點的左子樹上去，

如果大于根節點，那么就插入到根節點的右子樹上去，

由于不管是左子樹還是右子樹，它們又是一棵二分搜索樹，

那么這個過程就是依此類推下去，

一層一層向下比較新添加的節點的值，

大的向右，小的向左，不停的向下比較，

如果這個位置沒有被占住，那么就可以在這個位置上添加進去，

如果這個位置被占了，那就不停的向下比較，

直到找到一個合適的位置添加進去。

如果遇到兩個元素的值相同，那暫時先不去管，

也就是不添加進去，因為已經有了，

自定義二分搜索樹不包含重復元素，

如果想包含重復元素，

只需要定義左子樹小于等于節點、或者右子樹大于等于節點，

只要把“等于”這種關系放進定義里就可以了。

二分搜索樹添加元素的非遞歸寫法，和鏈表很像

但是在二分搜索樹方面的實現盡量使用遞歸來實現，

就是要鍛煉遞歸算法的書寫，

因為遞歸算法的很多細節和內容需要不斷去體會，

但是非遞歸的寫法也很實用的，

因為遞歸本身是具有更高的開銷的，

雖然在現代計算機上這些開銷并不明顯，

但是在一些極端的情況下還是可以看出很大的區別，

尤其是對于二分搜索樹來說，

在最壞的情況下它有可能會退化成一個鏈表，

那么在這種情況下使用遞歸的方式很容易造成系統棧的溢出，

二分搜索樹一些非遞歸的實現你可以自己練習一下。

在二分搜索樹方面，遞歸比非遞歸實現起來更加簡單。

代碼

   public class MyBinarySearchTree> {

         private class Node {
             public E e;
             public Node left, right;

             public Node (E e) {
                   this.e = e;
                   left = null;
                   right = null;
             }
         }

         private Node root;
         private int size;

         public MyBinarySearchTree () {
               root = null;
               size = 0;
         }

         public int getSize() {
               return size;
         }

         public boolean isEmpty () {
               return size == 0;
         }

         // 向二分搜索樹中添加一個元素 e
         public void add (E e) {
               if (root == null) {
                     root = new Node(e);
                     size ++;
               } else {
                     add(root, e);
               }
         }

         // 向以node為根的二分搜索樹種插入元素E，遞歸算法
         private void add (Node node, E e) {
               // node 是對用戶屏蔽的，用戶不用知道二分搜索樹中有怎樣一個節點結構

               // 如果出現相同的元素就不進行操作了
               if (e.equals(node.e)) {
                     return;
               } else if (e.compareTo(node.e) < 0 && node.left == null) {
                     // 給左孩子賦值
                     node.left = new Node(e);
                     size ++;
                     return;
               } else if (e.compareTo(node.e) > 0 && node.right == null) {
                     // 給右海子賦值
                     node.right = new Node(e);
                     size ++;
                     return;
               }

               // 這里是處理節點被占了，那就進入下一個層的二叉樹中
               if (e.compareTo(node.e) < 0) {
                     // 去左子樹
                     add(node.left, e);
               } else { // e.compareTo(node.e) > 0
                     // 去右子樹
                     add(node.right, e);
               }
         }
   }

對于二分搜索的插入操作

上面的代碼是相對比較復雜的，

可以進行改進一下，

讓代碼整體簡潔一些，

因為遞歸算法是有很多不同的寫法的，

而且遞歸的終止條件也是有不同的考量。

改進添加操作

遞歸算法有很多不同的寫法，

遞歸的終止條件也有不同的考量。

之前的算法

向以 node 為根的二分搜索樹中插入元素 e，

其實將新的元素插入至 node 的左孩子或者右孩子，

如果 node 的左或右孩子為空，那可以進行相應的賦值操作，

如果是 node 的左右孩子都不為空的話，

那就只能遞歸的插入到相應 node 的左或右孩子中，

因為這一層節點已經滿了，只能考慮下一層了，

下一層符合要求并且節點沒有滿，就可以進行相應的賦值操作了。

但是有對根節點做出了特殊的處理，要防止根節點為空的情況發生，

如果根節點為空，那么就將第一個元素賦值為根節點，

但是除了根節點以外，其它節點不需要做這種特殊處理，

所以導致邏輯上并不統一，并且遞歸的終止條件非常的臃腫，

代碼

   public class MyBinarySearchTree> {

         private class Node {
             public E e;
             public Node left, right;

             public Node (E e) {
                   this.e = e;
                   left = null;
                   right = null;
             }
         }

         private Node root;
         private int size;

         public MyBinarySearchTree () {
               root = null;
               size = 0;
         }

         public int getSize() {
               return size;
         }

         public boolean isEmpty () {
               return size == 0;
         }

         // 向二分搜索樹中添加一個元素 e
         // 改進：直接調用add
         public void add (E e) {
               root = add(root, e);
         }

         // 向以node為根的二分搜索樹種插入元素E，遞歸算法
         // 改進：返回插入的新節點后二分搜索樹的根
         private Node add (Node node, E e) {

               // 處理最基本的問題
               if (node == null) {
                     size ++;
                     return new Node(e);
               }

               // 空的二叉樹也是叉樹。
               if (e.compareTo(node.e) < 0) {
                     // 將處理后的結果賦值給node的左子樹
                     node.left =  add(node.left, e);
               } else if (e.compareTo(node.e) > 0) {
                     // 將處理后的結果賦值給node的右子樹
                     node.right =  add(node.right, e);
               } // 如果相同 就什么都不做

               // 最后返回這個node
               return node;
         }

   //    // 向二分搜索樹中添加一個元素 e
   //    public void add (E e) {
   //        if (root == null) {
   //            root = new Node(e);
   //            size ++;
   //        } else {
   //            add(root, e);
   //        }
   //    }

   //    // 向以node為根的二分搜索樹種插入元素E，遞歸算法
   //    private void add (Node node, E e) {
   //        // node 是對用戶屏蔽的，用戶不用知道二分搜索樹中有怎樣一個節點結構
   //
   //        // 如果出現相同的元素就不進行操作了
   //        if (e.equals(node.e)) {
   //            return;
   //        } else if (e.compareTo(node.e) < 0 && node.left == null) {
   //            // 給左孩子賦值
   //            node.left = new Node(e);
   //            return;
   //        } else if (e.compareTo(node.e) > 0 && node.right == null) {
   //            // 給右海子賦值
   //            node.right = new Node(e);
   //            return;
   //        }
   //
   //        // 這里是處理節點被占了，那就進入下一個層的二叉樹中
   //        if (e.compareTo(node.e) < 0) {
   //            // 去左子樹
   //            add(node.left, e);
   //        } else { // e.compareTo(node.e) > 0
   //            // 去右子樹
   //            add(node.right, e);
   //        }
   //    }
   }

雖然代碼量更少了，但是也更難理解的了一些

首先從宏觀的語意的角度去理解定義這個函數的語意后

整個遞歸函數處理的邏輯如何成立的，

其次從微觀的角度上可以寫一些輔助代碼來幫助你一點一點的查看，

從一個空的二分搜索樹開始，往里添加三五個元素，

看看每個元素是如何逐步的添加進去。

可以嘗試一些鏈表這個程序插入操作的遞歸算法，

其實這二者之間是擁有非常高的相似度的，

只不過在二分搜索樹中需要判斷一下是需要插入到左子樹還是右子樹而已，

對于鏈表來說直接插入到 next 就好了，

通過二者的比較就可以更加深入的理解這個程序。

查詢操作非常的容易

只需要不停的看每一個 node 里面存的元素，

不會牽扯到整個二分搜索樹的添加操作

和添加元素一樣需要使用遞歸的進行實現

在遞歸的過程中就需要從二分搜索樹的根開始，

逐漸的轉移在二分搜索樹的子樹中縮小問題的規模，

縮小查詢的樹的規模，直到找到這個元素 e 或者發現找不到這個元素 e。

在數組和鏈表中有索引這個概念，

但是在二分搜索樹中沒有索引這個概念。

代碼

   public class MyBinarySearchTree> {

         private class Node {
             public E e;
             public Node left, right;

             public Node (E e) {
                   this.e = e;
                   left = null;
                   right = null;
             }
         }

         private Node root;
         private int size;

         public MyBinarySearchTree () {
               root = null;
               size = 0;
         }

         public int getSize() {
               return size;
         }

         public boolean isEmpty () {
               return size == 0;
         }

         // 向二分搜索樹中添加一個元素 e
         // 改進：直接調用add
         public void add (E e) {
               root = add(root, e);
         }

         // 向以node為根的二分搜索樹中插入元素E，遞歸算法
         // 改進：返回插入的新節點后二分搜索樹的根
         private Node add (Node node, E e) {

               // 處理最基本的問題
               if (node == null) {
                     size ++;
                     return new Node(e);
               }

               // 空的二叉樹也是叉樹。
               if (e.compareTo(node.e) < 0) {
                     // 將處理后的結果賦值給node的左子樹
                     node.left =  add(node.left, e);
               } else if (e.compareTo(node.e) > 0) {
                     // 將處理后的結果賦值給node的右子樹
                     node.right =  add(node.right, e);
               } // 如果相同 就什么都不做

               // 最后返回這個node
               return node;
         }

         // 查詢二分搜索數中是否包含某個元素
         public boolean contains (E e) {
               return contains(root, e);
         }

         // 向以node為根的二分搜索樹 進行查找  遞歸算法
         public boolean contains (Node node, E e) {

               // 解決最基本的問題 也就是遍歷完所有節點都沒有找到
               if (node == null) {
                     return false;
               }

               // 如果 e 小于當前節點的e 則向左子樹進發
               if (e.compareTo(node.e) < 0) {
                   return contains(node.left, e);
               } else if (e.compareTo(node.e) > 0) { // 如果 e 大于當前節點的e 則向右子樹進發
                   return contains(node.right, e);
               } else { // 如果e 等于 當前節點 e 則直接返回true
                     return true;
               }
         }
   }

遍歷操作就是把這個數據結構中所有的元素都訪問一遍

在二分搜索樹中就是把所有節點都訪問一遍，

訪問數據結構中存儲的所有元素是因為與業務相關，

例如 給所有的同學加兩分，給所有的員工發補貼等等，

由于你的數據結構是用來存儲數據的，

不僅可以查詢某些特定的數據，

還應該有相關的方式將所有的數據都進行訪問。

在線性結構下，遍歷是極其容易的

無論是數組還是鏈表只要使用一下循環就好了，

但是這件事在樹結構下沒有那么簡單，

但是也沒有那么難：）。

在樹結構下遍歷操作并沒有那么難

如果你對樹結構不熟悉，那么可能就有點難，

但是如果你熟悉了樹結構，那么并非是那么難的操作，

尤其是你在掌握遞歸操作之后，遍歷樹就更加不難了。

對于遍歷操作，兩個子樹都要顧及

即要訪問左子樹中所有的節點又要訪問右子樹中所有的節點，

下面的代碼中的遍歷方式也稱為二叉樹的前序遍歷，

先訪問這個節點，再訪問左右子樹，

訪問這個節點放在了訪問左右子樹的前面所以就叫前序遍歷。

要從宏觀與微觀的角度去理解這個代碼，

從宏觀的角度來看，

定義好了遍歷的這個語意后整個邏輯是怎么組建的，

從微觀的角度來看，真正的有一個棵二叉樹的時候，

這個代碼是怎樣怎樣一行一行去執行的。

當你熟練的掌握遞歸的時候，

有的時候你可以不用遵守 那種先寫遞歸終止的條件，

再寫遞歸組成的的邏輯 這樣的一個過程，如寫法二，

雖然什么都不干，但是也是 return 了，

和寫法一中寫的邏輯其實是等價的，

也就是在遞歸終止條件這部分可以靈活處理。

寫法一看起來邏輯比較清晰，遞歸終止在前，遞歸組成的邏輯在后。

// 遍歷以node為根的二分搜索樹 遞歸算法
function traverse(node) {
   if (node === null) {
      return;
   }

   // ... 要做的事情

   // 訪問該節點 兩邊都要顧及
   // 訪問該節點的時候就去做該做的事情，
   // 如 給所有學生加兩分
   traverse(node.left);
   traverse(node.right);
}

// 寫法二 這種邏輯也是可以的
function traverse(node) {
   if (node !== null) {
      // ... 要做的事情

      // 訪問該節點 兩邊都要顧及
      // 訪問該節點的時候就去做該做的事情，
      // 如 給所有學生加兩分
      traverse(node.left);
      traverse(node.right);
   }
}

MyBinarySearchTree

   public class MyBinarySearchTree> {

         private class Node {
             public E e;
             public Node left, right;

             public Node (E e) {
                   this.e = e;
                   left = null;
                   right = null;
             }
         }

         private Node root;
         private int size;

         public MyBinarySearchTree () {
               root = null;
               size = 0;
         }

         public int getSize() {
               return size;
         }

         public boolean isEmpty () {
               return size == 0;
         }

         // 向二分搜索樹中添加一個元素 e
         // 改進：直接調用add
         public void add (E e) {
               root = add(root, e);
         }

         // 向以node為根的二分搜索樹中插入元素E，遞歸算法
         // 改進：返回插入的新節點后二分搜索樹的根
         private Node add (Node node, E e) {

               // 處理最基本的問題
               if (node == null) {
                     size ++;
                     return new Node(e);
               }

               // 空的二叉樹也是叉樹。
               if (e.compareTo(node.e) < 0) {
                     // 將處理后的結果賦值給node的左子樹
                     node.left =  add(node.left, e);
               } else if (e.compareTo(node.e) > 0) {
                     // 將處理后的結果賦值給node的右子樹
                     node.right =  add(node.right, e);
               } // 如果相同 就什么都不做

               // 最后返回這個node
               return node;
         }

         // 查詢二分搜索數中是否包含某個元素
         public boolean contains (E e) {
               return contains(root, e);
         }

         // 向以node為根的二分搜索樹 進行查找  遞歸算法
         public boolean contains (Node node, E e) {

               // 解決最基本的問題 也就是遍歷完所有節點都沒有找到
               if (node == null) {
                     return false;
               }

               // 如果 e 小于當前節點的e 則向左子樹進發
               if (e.compareTo(node.e) < 0) {
                   return contains(node.left, e);
               } else if (e.compareTo(node.e) > 0) { // 如果 e 大于當前節點的e 則向右子樹進發
                   return contains(node.right, e);
               } else { // 如果e 等于 當前節點 e 則直接返回true
                     return true;
               }
         }

         // 二分搜索樹的前序遍歷
         public void preOrder () {
               preOrder(root);
         }

         // 前序遍歷以node為根的二分搜索樹 遞歸算法
         public void preOrder (Node node) {
               if (node == null) {
                     return;
               }

               // 輸出
               System.out.println(node.e);

               preOrder(node.left);
               preOrder(node.right);

   //        // 這種邏輯也是可以的
   //        if (node != null) {
   //            // 輸出
   //            System.out.println(node.e);
   //
   //            preOrder(node.left);
   //            preOrder(node.right);
   //        }
         }
   }

Main

   public class Main {

         public static void main(String[] args) {

               MyBinarySearchTree mbst = new MyBinarySearchTree();

               int [] nums = {5, 3, 6, 8, 4, 2};
               for (int i = 0; i < nums.length ; i++) {
                     mbst.add(nums[i]);
               }

               /////////////////
               //      5      //
               //    /       //
               //   3    6    //
               //  /        //
               // 2  4     8  //
               /////////////////
               mbst.preOrder();
         }
   }

遍歷輸出二分搜索樹

可以寫一個輔助函數自動遍歷所有節點生成字符串，

輔助函數叫做 generateBSTString，

這個函數的作用是，生成以 node 為根節點，

深度為 depth 的描述二叉樹的字符串，

這樣一來要新增一個輔助函數，

這個函數的作用是，根據遞歸深度生成字符串，

這個輔助函數叫做 generateDepthString。

MyBinarySearchTree

   public class MyBinarySearchTree> {

         private class Node {
             public E e;
             public Node left, right;

             public Node (E e) {
                   this.e = e;
                   left = null;
                   right = null;
             }
         }

         private Node root;
         private int size;

         public MyBinarySearchTree () {
               root = null;
               size = 0;
         }

         public int getSize() {
               return size;
         }

         public boolean isEmpty () {
               return size == 0;
         }

         // 向二分搜索樹中添加一個元素 e
         // 改進：直接調用add
         public void add (E e) {
               root = add(root, e);
         }

         // 向以node為根的二分搜索樹中插入元素E，遞歸算法
         // 改進：返回插入的新節點后二分搜索樹的根
         private Node add (Node node, E e) {

               // 處理最基本的問題
               if (node == null) {
                     size ++;
                     return new Node(e);
               }

               // 空的二叉樹也是叉樹。
               if (e.compareTo(node.e) < 0) {
                     // 將處理后的結果賦值給node的左子樹
                     node.left =  add(node.left, e);
               } else if (e.compareTo(node.e) > 0) {
                     // 將處理后的結果賦值給node的右子樹
                     node.right =  add(node.right, e);
               } // 如果相同 就什么都不做

               // 最后返回這個node
               return node;
         }

         // 查詢二分搜索數中是否包含某個元素
         public boolean contains (E e) {
               return contains(root, e);
         }

         // 向以node為根的二分搜索樹 進行查找  遞歸算法
         public boolean contains (Node node, E e) {

               // 解決最基本的問題 也就是遍歷完所有節點都沒有找到
               if (node == null) {
                     return false;
               }

               // 如果 e 小于當前節點的e 則向左子樹進發
               if (e.compareTo(node.e) < 0) {
                   return contains(node.left, e);
               } else if (e.compareTo(node.e) > 0) { // 如果 e 大于當前節點的e 則向右子樹進發
                   return contains(node.right, e);
               } else { // 如果e 等于 當前節點 e 則直接返回true
                     return true;
               }
         }

         // 二分搜索樹的前序遍歷
         public void preOrder () {
               preOrder(root);
         }

         // 前序遍歷以node為根的二分搜索樹 遞歸算法
         public void preOrder (Node node) {
               if (node == null) {
                     return;
               }

               // 輸出
               System.out.println(node.e);

               preOrder(node.left);
               preOrder(node.right);

   //        // 這種邏輯也是可以的
   //        if (node != null) {
   //            // 輸出
   //            System.out.println(node.e);
   //
   //            preOrder(node.left);
   //            preOrder(node.right);
   //        }
         }

         @Override
         public String toString () {
               StringBuilder sb = new StringBuilder();
               generateBSTString(root, 0, sb);
               return sb.toString();
         }

         // 生成以node為根節點，深度為depth的描述二叉樹的字符串
         private void generateBSTString (Node node, int depath, StringBuilder sb) {
               if (node == null) {
                     sb.append(generateDepthString(depath) + "null
");
                     return;
               }

               sb.append(generateDepthString(depath) + node.e + "
");

               generateBSTString(node.left, depath + 1, sb);
               generateBSTString(node.right, depath + 1, sb);

         }

         // 生成路徑字符串
         private String generateDepthString (int depth) {
               StringBuilder sb = new StringBuilder();
               for (int i = 0; i < depth; i++) {
                     sb.append("-- ");
               }
               return  sb.toString();
         }
   }

Main

   public class Main {

         public static void main(String[] args) {

               MyBinarySearchTree mbst = new MyBinarySearchTree();

               int [] nums = {5, 3, 6, 8, 4, 2};
               for (int i = 0; i < nums.length ; i++) {
                     mbst.add(nums[i]);
               }

               /////////////////
               //      5      //
               //    /       //
               //   3    6    //
               //  /        //
               // 2  4     8  //
               /////////////////
               mbst.preOrder();

               System.out.println();

               // 輸出 調試字符串
               System.out.println(mbst.toString());
         }
   }

前序遍歷

前序遍歷是最自然的一種遍歷方式，

同時也是最常用的一種遍歷方式，

如果沒有特殊情況的話，

在大多數情況下都會使用前序遍歷。

先訪問這個節點，

然后訪問這個節點的左子樹，

再訪問這個節點的右子樹，

整個過程循環往復。

前序遍歷的前表示先訪問的這個節點。

function preOrder(node) {
   if (node == null) return;

   // ... 要做的事情
   // 訪問該節點

   // 先一直往左，然后不斷返回上一層 再向左、終止，
   // 最后整個操作循環往復，直到全部終止。
   preOrder(node.left);
   preOrder(node.right);
}

中序遍歷

先訪問左子樹，再訪問這個節點，

最后訪問右子樹，整個過程循環往復。

中序遍歷的中表示先訪問左子樹，

然后再訪問這個節點，最后訪問右子樹，

訪問這個節點的操作放到了訪問左子樹和右子樹的中間。

function inOrder(node) {
   if (node == null) return;

   inOrder(node.left);

   // ... 要做的事情
   // 訪問該節點

   inOrder(node.right);
}

中序遍歷后輸出的結果是排序后的結果。

中序遍歷的結果是二分搜索樹中

存儲的所有的元素從小到大進行排序后的結果，

這是二分搜索樹一個很重要的一個性質。

二分搜索樹任何一個節點的左子樹上所有的節點值都比當前節點的小，

二分搜索樹任何一個節點的右子樹上所有的節點值都比當前節點的大，

每一個節點的遍歷都是從左往自己再往右，

先遍歷這個節點的左子樹，先把比自己節點小的所有元素都遍歷了，

再遍歷這個節點，然后再遍歷比這個節點大的所有元素，這個過程是遞歸完成的，

以 小于、等于、大于的順序遍歷得到的結果自然就是一個從小到大的排序的，

你也可以 使用大于 等于 小于的順序遍歷，那樣結果就是從大到小排序了。

也正是因為這個原因，二分搜索樹有的時候也叫做排序樹，

這是二分搜索樹額外的效能，

當你使用數組、鏈表時如果想讓你的元素是順序的話，

必須做額外的工作，否則沒有辦法保證一次遍歷得到的元素都是順序排列的，

但是對于二分搜索樹來說，你只要遵從他的定義，

然后使用中序遍歷的方式遍歷整棵二分搜索樹就能夠得到順序排列的結果。

后序遍歷

先訪問左子樹，再訪問右子樹，

最后訪問這個節點，整個過程循環往復。

后序遍歷的后表示先訪問左子樹，

然后再訪問右子樹，最后訪問這個節點，

訪問這個節點的操作放到了訪問左子樹和右子樹的后邊。

function inOrder(node) {
   if (node == null) return;

   inOrder(node.left);
   inOrder(node.right);
   // ... 要做的事情
   // 訪問該節點
}

二分搜索樹的前序遍歷和后序遍歷并不像中序遍歷那樣進行了排序

后續遍歷的應用場景是那些必須先處理完左子樹的所有節點，

然后再處理完右子樹的所有節點，最后再處理當前的節點，

也就是處理完這個節點的孩子節點之后再去處理當前這個節點。

一個典型的應用是在內存釋放方面，如果需要你手動的釋放內存，

那么就需要先把這個節點的孩子節點全都釋放完然后再來釋放這個節點本身，

這種情況使用二叉樹的后序遍歷的方式，

先處理左子樹、再處理右子樹、最后處理自己。

但是例如java、c#這樣的語言都有垃圾回收機制，

所以不需要你對內存管理進行手動的控制，

c++ 語言中需要手動的控制內存，

那么在二分搜索樹內存釋放這方面就需要使用后序遍歷。

對于一些樹結構的問題，

很多時候也是需要先針對一個節點的孩子節點求解出答案，

最終再由這些答案組合成針對這個節點的答案，

樹形問題有分治算法、回溯算法、動態規劃算法等等。

二分搜索樹的前中后序遍歷

主要從程序的角度進行分析，

很多時候對一些問題的分析，如果直接給你一個樹結構，

然后你能夠直接看出來對于這棵樹來說它的前中后序遍歷的結果是怎樣的，

那就可以大大加快解決問題的速度，

同時這樣的一個問題也是和計算機相關的考試的題目，

對于這樣的一個問題的更加深入的理解

也可以幫助你理解二分搜索樹這種數據結構。

MyBinarySearchTree

   public class MyBinarySearchTree> {

         private class Node {
             public E e;
             public Node left, right;

             public Node (E e) {
                   this.e = e;
                   left = null;
                   right = null;
             }
         }

         private Node root;
         private int size;

         public MyBinarySearchTree () {
               root = null;
               size = 0;
         }

         public int getSize() {
               return size;
         }

         public boolean isEmpty () {
               return size == 0;
         }

         // 向二分搜索樹中添加一個元素 e
         // 改進：直接調用add
         public void add (E e) {
               root = add(root, e);
         }

         // 向以node為根的二分搜索樹中插入元素E，遞歸算法
         // 改進：返回插入的新節點后二分搜索樹的根
         private Node add (Node node, E e) {

               // 處理最基本的問題
               if (node == null) {
                     size ++;
                     return new Node(e);
               }

               // 空的二叉樹也是叉樹。
               if (e.compareTo(node.e) < 0) {
                     // 將處理后的結果賦值給node的左子樹
                     node.left =  add(node.left, e);
               } else if (e.compareTo(node.e) > 0) {
                     // 將處理后的結果賦值給node的右子樹
                     node.right =  add(node.right, e);
               } // 如果相同 就什么都不做

               // 最后返回這個node
               return node;
         }

         // 查詢二分搜索數中是否包含某個元素
         public boolean contains (E e) {
               return contains(root, e);
         }

         // 向以node為根的二分搜索樹 進行查找  遞歸算法
         private boolean contains (Node node, E e) {

               // 解決最基本的問題 也就是遍歷完所有節點都沒有找到
               if (node == null) {
                     return false;
               }

               // 如果 e 小于當前節點的e 則向左子樹進發
               if (e.compareTo(node.e) < 0) {
                   return contains(node.left, e);
               } else if (e.compareTo(node.e) > 0) { // 如果 e 大于當前節點的e 則向右子樹進發
                   return contains(node.right, e);
               } else { // 如果e 等于 當前節點 e 則直接返回true
                     return true;
               }
         }

         // 二分搜索樹的前序遍歷
         public void preOrder () {
               preOrder(root);
         }

         // 前序遍歷以node為根的二分搜索樹 遞歸算法
         private void preOrder (Node node) {
               if (node == null) {
                     return;
               }

               // 輸出
               System.out.println(node.e);

               preOrder(node.left);
               preOrder(node.right);

   //        // 這種邏輯也是可以的
   //        if (node != null) {
   //            // 輸出
   //            System.out.println(node.e);
   //
   //            preOrder(node.left);
   //            preOrder(node.right);
   //        }
         }

         // 二分搜索樹的中序遍歷
         public void inOrder () {
               inOrder(root);
         }

         // 中序遍歷以node為根的二分搜索樹 遞歸算法
         private void inOrder (Node node) {
               if (node == null) return;

               inOrder(node.left);
               System.out.println(node.e);
               inOrder(node.right);

         }

         // 二分搜索樹的后序遍歷
         public void postOrder () {
               postOrder(root);
         }

         // 后續遍歷以node為根的二分搜索樹 遞歸算法
         private void postOrder (Node node) {
               if (node == null) return;

               postOrder(node.left);
               postOrder(node.right);
               System.out.println(node.e);
         }

         @Override
         public String toString () {
               StringBuilder sb = new StringBuilder();
               generateBSTString(root, 0, sb);
               return sb.toString();
         }

         // 生成以node為根節點，深度為depth的描述二叉樹的字符串
         private void generateBSTString (Node node, int depath, StringBuilder sb) {
               if (node == null) {
                     sb.append(generateDepthString(depath) + "null
");
                     return;
               }

               sb.append(generateDepthString(depath) + node.e + "
");

               generateBSTString(node.left, depath + 1, sb);
               generateBSTString(node.right, depath + 1, sb);

         }

         // 生成路徑字符串
         private String generateDepthString (int depth) {
               StringBuilder sb = new StringBuilder();
               for (int i = 0; i < depth; i++) {
                     sb.append("-- ");
               }
               return  sb.toString();
         }
   }

Main

   public class Main {

         public static void main(String[] args) {

               MyBinarySearchTree mbst = new MyBinarySearchTree();

               int [] nums = {5, 3, 6, 8, 4, 2};
               for (int i = 0; i < nums.length ; i++) {
                     mbst.add(nums[i]);
               }

               /////////////////
               //      5      //
               //    /       //
               //   3    6    //
               //  /        //
               // 2  4     8  //
               /////////////////

               // 前序遍歷
               mbst.preOrder(); // 5 3 2 4 6 8
               System.out.println();

               // 中序遍歷
               mbst.inOrder(); // 2 3 4 5 6 8
               System.out.println();

               // 后序遍歷
               mbst.postOrder(); // 2 4 3 8 6 5
               System.out.println();

   //        // 輸出 調試字符串
   //        System.out.println(mbst.toString());
         }
   }

再看二分搜索樹的遍歷

對每一個節點都有三次的訪問機會，

在遍歷左子樹之前會去訪問一下這個節點然后才能遍歷它的左子樹，

在遍歷完左子樹之后才能夠回到這個節點，之后才會去遍歷它的右子樹，

在遍歷右子樹之后又回到了這個節點。

這就是每一個節點使用這種遞歸遍歷的方式其實會訪問它三次，

對二分搜索樹前中后這三種順序的遍歷

其實就對應于這三個訪問機會是在哪里進行真正的那個訪問操作，

在哪里輸出訪問的這個節點的值，

是先訪問這個節點后再遍歷它的左右子樹，

還是先遍歷左子樹然后訪問這個節點最后遍歷右子樹，

再或者是 先遍歷左右子樹再訪問這個節點。

function traverse(node) {
   if (node === null) return;

   // 1. 第一個訪問的機會   前

   traverse(node.left);

   // 2. 第二個訪問的機會   中

   traverse(node.right);

   // 3. 第三個訪問的機會   后
}

二叉樹前中后序遍歷訪問節點的不同

前序遍歷訪問節點都是在第一個訪問機會的位置才去訪問節點，

中序遍歷訪問節點都是在第二個訪問機會的位置才去訪問節點，

后序遍歷訪問節點都是在第三個訪問機會的位置才去訪問節點，

前序遍歷的遞歸寫法

前序遍歷是最自然的一種遍歷方式，

同時也是最常用的一種遍歷方式，

如果沒有特殊情況的話，

在大多數情況下都會使用前序遍歷。

先訪問這個節點，

然后訪問這個節點的左子樹，

再訪問這個節點的右子樹，

整個過程循環往復。

前序遍歷的前表示先訪問的這個節點。

function preOrder(node) {
   if (node == null) return;

   // ... 要做的事情
   // 訪問該節點

   // 先一直往左，然后不斷返回上一層 再向左、終止，
   // 最后整個操作循環往復，直到全部終止。
   preOrder(node.left);
   preOrder(node.right);
}

前序遍歷的非遞歸寫法

使用另外一個數據結構棧來模擬遞歸調用時的系統棧。

先訪問根節點，將根節點壓入棧，

然后把棧頂元素拿出來，對這個節點進行操作，

這個節點操作完畢之后，再訪問這個節點的兩個子樹，

也就是把這個節點的左右兩個孩子壓入棧中，

壓入棧的順序是先壓入右孩子、再壓入左孩子，

這是因為棧是后入先出的，所以要先壓入后續要訪問的那個節點，

再讓棧頂的元素出棧，對這個節點進行操作，

這個節點操作完畢之后，再訪問這個節點的兩個子樹，

但是這個節點是葉子節點，它的兩個孩子都為空，

那么什么都不用壓入了， 再去取棧頂的元素，

對這個節點進行操作，這個節點操作完畢之后，

再訪問這個節點的兩個子樹，但是這個節點也是葉子節點，

那么什么都不用壓入了，棧中也為空了，整個訪問操作結束。

無論是非遞歸還是遞歸的寫法，結果都是一致的

非遞歸的寫法中，棧的應用是幫助你記錄你下面要訪問的哪些節點，

這個過程非常像使用棧模擬了一下在系統棧中相應的一個調用，

相當于在系統棧中記錄下一步依次要訪問哪些節點。

將遞歸算法轉換為非遞歸算法

是棧這種數據結構非常重要的一種應用。

二分搜索樹遍歷的非遞歸實現比遞歸實現復雜很多

因為你使用了一個輔助的數據結構才能完成這個過程，

使用了棧這種數據結構模擬了系統調用棧，

在算法語意解讀上遠遠比遞歸實現的算法語意解讀要難很多。

二分搜索樹的中序遍歷和后序遍歷的非遞歸實現更復雜

尤其是對于后序遍歷來說難度更大，

但是中序遍歷和后序遍歷的非遞歸實現，實際應用并不廣泛。

但是你可以嘗試實現中序、后序遍歷的非遞歸實現，

主要是鍛煉你算法實現、思維邏輯實現思路，

在解決這個問題的過程中可能會遇到一些困難，

可以通過查看網上的資料來解決這個問題，

這樣的問題有可能會在面試題及考試中出現，

也就是中序和后序遍歷相應的非遞歸實現。

在經典的教科書中一般都會有這三種遍歷的非遞歸實現，

通過二分搜索樹的前序遍歷非遞歸的實現方式中可以看出，

完全可以使用模擬系統的棧來完成遞歸轉成非遞歸這樣的操作，

在慕課上 有一門課《玩轉算法面試》中完全模擬了系統棧的寫法，

也就是將前中后序的遍歷都轉成了非遞歸的算法，

這與經典的教科書上的實現不一樣，

但是這種方式對你進一步理解棧這種數據結構還是二分搜索樹的遍歷

甚至是系統調用的過程都是很有意義的。

對于前序遍歷來說無論是遞歸寫法還是非遞歸寫法

對于這棵樹來說都是在遍歷的過程中一直到底，

這樣的一種遍歷方式也叫深度優先遍歷，

最終的遍歷結果都會先來到整顆樹最深的地方，

直到不能再深了才會開始返回到上一層，

所以這種遍歷就叫做深度優先遍歷。

與深度優先遍歷相對應的就是廣度優先遍歷，

廣度優先遍歷遍歷出來的結果它的順序其實是

整個二分搜索樹的一個層序遍歷的順序。

MyBinarySearchTree

      import java.util.Stack;

      public class MyBinarySearchTree> {

            private class Node {
                public E e;
                public Node left, right;

                public Node (E e) {
                      this.e = e;
                      left = null;
                      right = null;
                }
            }

            private Node root;
            private int size;

            public MyBinarySearchTree () {
                  root = null;
                  size = 0;
            }

            public int getSize() {
                  return size;
            }

            public boolean isEmpty () {
                  return size == 0;
            }

            // 向二分搜索樹中添加一個元素 e
            // 改進：直接調用add
            public void add (E e) {
                  root = add(root, e);
            }

            // 向以node為根的二分搜索樹中插入元素E，遞歸算法
            // 改進：返回插入的新節點后二分搜索樹的根
            private Node add (Node node, E e) {

                  // 處理最基本的問題
                  if (node == null) {
                        size ++;
                        return new Node(e);
                  }

                  // 空的二叉樹也是叉樹。
                  if (e.compareTo(node.e) < 0) {
                        // 將處理后的結果賦值給node的左子樹
                        node.left =  add(node.left, e);
                  } else if (e.compareTo(node.e) > 0) {
                        // 將處理后的結果賦值給node的右子樹
                        node.right =  add(node.right, e);
                  } // 如果相同 就什么都不做

                  // 最后返回這個node
                  return node;
            }

            // 查詢二分搜索數中是否包含某個元素
            public boolean contains (E e) {
                  return contains(root, e);
            }

            // 向以node為根的二分搜索樹 進行查找  遞歸算法
            private boolean contains (Node node, E e) {

                  // 解決最基本的問題 也就是遍歷完所有節點都沒有找到
                  if (node == null) {
                        return false;
                  }

                  // 如果 e 小于當前節點的e 則向左子樹進發
                  if (e.compareTo(node.e) < 0) {
                      return contains(node.left, e);
                  } else if (e.compareTo(node.e) > 0) { // 如果 e 大于當前節點的e 則向右子樹進發
                      return contains(node.right, e);
                  } else { // 如果e 等于 當前節點 e 則直接返回true
                        return true;
                  }
            }

            // 二分搜索樹的前序遍歷
            public void preOrder () {
                  preOrder(root);
            }

            // 前序遍歷以node為根的二分搜索樹 遞歸算法
            private void preOrder (Node node) {
                  if (node == null) {
                        return;
                  }

                  // 輸出
                  System.out.println(node.e);

                  preOrder(node.left);
                  preOrder(node.right);

      //        // 這種邏輯也是可以的
      //        if (node != null) {
      //            // 輸出
      //            System.out.println(node.e);
      //
      //            preOrder(node.left);
      //            preOrder(node.right);
      //        }
            }

            // 二分搜索樹的前序遍歷 非遞歸算法
            public void preOrderNonRecursive () {

                  Stack stack = new Stack();
                  stack.push(root);

                  Node node = null;
                  while (!stack.isEmpty()) {
                        node = stack.pop();

      //            // 第一種寫法 不符合要求也可以壓入棧，但是不符合要求的在出棧后不處理它
      //            if (node != null) {
      //                System.out.println(node.e);
      //                stack.push(node.right);
      //                stack.push(node.left);
      //            }

      //            // 第二種寫法 不符合要求也可以壓入棧，但是不符合要求的在出棧后不處理它
      //            if (node == null) continue;
      //
      //            System.out.println(node.e);
      //            stack.push(node.right);
      //            stack.push(node.left);

                        // 寫法三 不符合要求就不壓入棧
                        System.out.println(node.e);

                        if (node.right != null) {
                              stack.push(node.right);
                        }
                        if (node.left != null) {
                              stack.push(node.left);
                        }
                  }
            }

            // 二分搜索樹的中序遍歷
            public void inOrder () {
                  inOrder(root);
            }

            // 中序遍歷以node為根的二分搜索樹 遞歸算法
            private void inOrder (Node node) {
                  if (node == null) return;

                  inOrder(node.left);
                  System.out.println(node.e);
                  inOrder(node.right);

            }

            // 二分搜索樹的中序遍歷 非遞歸算法
            public void inOrderNonRecursive () {
            }

            // 二分搜索樹的后序遍歷
            public void postOrder () {
                  postOrder(root);
            }

            // 后續遍歷以node為根的二分搜索樹 遞歸算法
            private void postOrder (Node node) {
                  if (node == null) return;

                  postOrder(node.left);
                  postOrder(node.right);
                  System.out.println(node.e);
            }

            @Override
            public String toString () {
                  StringBuilder sb = new StringBuilder();
                  generateBSTString(root, 0, sb);
                  return sb.toString();
            }

            // 生成以node為根節點，深度為depth的描述二叉樹的字符串
            private void generateBSTString (Node node, int depath, StringBuilder sb) {
                  if (node == null) {
                        sb.append(generateDepthString(depath) + "null
");
                        return;
                  }

                  sb.append(generateDepthString(depath) + node.e + "
");

                  generateBSTString(node.left, depath + 1, sb);
                  generateBSTString(node.right, depath + 1, sb);

            }

            // 生成路徑字符串
            private String generateDepthString (int depth) {
                  StringBuilder sb = new StringBuilder();
                  for (int i = 0; i < depth; i++) {
                        sb.append("-- ");
                  }
                  return  sb.toString();
            }
      }

Main

   public class Main {

         public static void main(String[] args) {

               MyBinarySearchTree mbst = new MyBinarySearchTree();

               int [] nums = {5, 3, 6, 8, 4, 2};
               for (int i = 0; i < nums.length ; i++) {
                     mbst.add(nums[i]);
               }

               /////////////////
               //      5      //
               //    /       //
               //   3    6    //
               //  /        //
               // 2  4     8  //
               /////////////////

               // 前序遍歷
               mbst.preOrder(); // 5 3 2 4 6 8
               System.out.println();

               // 中序遍歷
               mbst.inOrder(); // 2 3 4 5 6 8
               System.out.println();

               // 后序遍歷
               mbst.postOrder(); // 2 4 3 8 6 5
               System.out.println();

               // 前序遍歷 非遞歸
               mbst.preOrderNonRecursive(); // 5 3 2 4 6 8
               System.out.println();

   //        // 輸出 調試字符串
   //        System.out.println(mbst.toString());
         }
   }

二分搜索樹的 前序、中序、后序遍歷

它們本質上都是深度優先遍歷。

對于二分搜索樹來說

每一個節點都有一個相應的深度的值，

根節點作為深度為 0 相應的節點，

有一些教科書 會把根節點作為深度為 1 相