摘要：在數(shù)據(jù)結(jié)構(gòu)領域?qū)獦浣Y(jié)構(gòu)來說二叉樹是最常用的一種樹結(jié)構(gòu)，二叉樹具有一個唯一的根節(jié)點，也就是最上面的節(jié)點。二叉樹每個節(jié)點最多有兩個孩子，一個孩子都沒有的節(jié)點通常稱之為葉子節(jié)點，二叉樹每個節(jié)點最多有一個父親，根節(jié)點是沒有父親節(jié)點的。

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

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

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

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

線性數(shù)據(jù)結(jié)構(gòu)是把所有的數(shù)據(jù)排成一排

樹結(jié)構(gòu)是倒立的樹，由一個根節(jié)點延伸出很多新的分支節(jié)點。

樹結(jié)構(gòu)本身是一個種天然的組織結(jié)構(gòu)

如 電腦中文件夾目錄結(jié)構(gòu)就是樹結(jié)構(gòu)

這種結(jié)構(gòu)來源于生活，

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

如 數(shù)理館、文史館等等，

到了數(shù)理館還要分成 很多的子類，

如 數(shù)學類的圖書、物理類的圖書、化學類的圖書，計算機類的圖書，

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

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

如 按領域分類 網(wǎng)站編程、app 開發(fā)、游戲開發(fā)、前端、后端等等，

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

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

這就是一個典型的樹結(jié)構(gòu)。

還有 一個公司的組織架構(gòu)也是這樣的一種樹結(jié)構(gòu)，

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

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

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

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

還有家譜，他本身也是一個樹結(jié)構(gòu)，

其實樹結(jié)構(gòu)并不抽象，在生活中隨處可見。

樹結(jié)構(gòu)非常的高效

比如文件管理，

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

然后用一個線性的結(jié)構(gòu)進行存儲，

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

但是如果給它做成樹機構(gòu)的話，

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

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

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

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

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

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

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

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

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

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

在數(shù)據(jù)結(jié)構(gòu)領域設計樹結(jié)構(gòu)的本質(zhì)也是如此。

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

當你將數(shù)據(jù)使用樹結(jié)構(gòu)進行存儲后，出奇的高效。

二分搜索樹（Binary Search Tree）

二分搜索樹有它的局限性

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

平衡二叉樹還有很多種

算法需要使用一些特殊的操作的時候?qū)?shù)據(jù)組織成樹結(jié)構(gòu)

會針對某一類特殊的操作產(chǎn)生非常高效的結(jié)果，

使用堆以及并查集，

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

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

將他們以某種形式存儲成樹結(jié)構(gòu)，

結(jié)果就是會對這類特殊的數(shù)據(jù)

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

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

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

線段樹主要用來處理線段這種特殊的數(shù)據(jù)，

Trie 主要用于處理字符串這類特殊的數(shù)據(jù)，

要想實現(xiàn)快速搜索的算法，

它的本質(zhì)依然是需要使用樹結(jié)構(gòu)的，

樹結(jié)構(gòu)不見得是顯式的展示在你面前，

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

這就像棧的應用一樣，

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

用戶根本想不到這背后使用了一個棧的數(shù)據(jù)結(jié)構(gòu)，

但是為了組建出這樣的功能是需要使用這種數(shù)據(jù)結(jié)構(gòu)的，

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

它的背后其實是因為有樹這種數(shù)據(jù)結(jié)構(gòu)作為支撐的，

這也是數(shù)據(jù)結(jié)構(gòu)、包括數(shù)據(jù)結(jié)構(gòu)在計算機科學領域非常重要的意義，

數(shù)據(jù)結(jié)構(gòu)雖然解決的是數(shù)據(jù)存儲的問題，

但是在使用的層面上不僅僅是因為要存儲數(shù)據(jù)，

更重要的是在你使用某些特殊的數(shù)據(jù)結(jié)構(gòu)存儲數(shù)據(jù)后，

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

甚至對于某些問題來說如果沒有這些數(shù)據(jù)結(jié)構(gòu)，

那么根本無從解決。

二叉樹

和鏈表一樣，也屬于動態(tài)數(shù)據(jù)結(jié)構(gòu)，

不需要創(chuàng)建這個數(shù)據(jù)結(jié)構(gòu)的時候就定好存儲的容量，

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

然后把它添加到這個數(shù)據(jù)結(jié)構(gòu)中，刪除也是同理，

每一個元素也是存到一個節(jié)點中，

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

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

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

二叉樹也叫多叉樹，

它每一個節(jié)點最多只能分成兩個叉，

根據(jù)這個定義也能定義出多叉樹，

如果每個節(jié)點可以分出十個叉，

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

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

在數(shù)據(jù)結(jié)構(gòu)領域?qū)獦浣Y(jié)構(gòu)來說

二叉樹是最常用的一種樹結(jié)構(gòu)，

二叉樹具有一個唯一的根節(jié)點，

也就是最上面的節(jié)點。

每一個節(jié)點最多有兩個子節(jié)點，

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

子節(jié)點指向左邊的那個節(jié)點就是左孩子，

子節(jié)點指向右邊的那個節(jié)點就是右孩子。

二叉樹每個節(jié)點最多有兩個孩子，

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

二叉樹每個節(jié)點最多有一個父親，

根節(jié)點是沒有父親節(jié)點的。

二叉樹和鏈表一樣具有天然遞歸的結(jié)構(gòu)

鏈表本身是線性的，

它的操作既可以使用循環(huán)也可以使用遞歸。

和樹相關的很多操作，

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

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

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

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

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

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

這兩個二叉樹都是節(jié)點個數(shù)更小的二叉樹，

這就是二叉樹所具有的天然的遞歸結(jié)構(gòu)。

二叉樹不一定是“滿”的

滿二叉樹就是除了葉子節(jié)點之外，

每一個節(jié)點都有兩個孩子。

就算你整個二叉樹上只有一個節(jié)點，

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

這棵二叉樹只有一個根節(jié)點，

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

就像鏈表中，只有一個節(jié)點它也是一個鏈表，

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

二分搜索樹是一棵二叉樹

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

如 根節(jié)點、葉子節(jié)點、左孩子右孩子、左子樹、右子樹、

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

二分搜索樹的每一個節(jié)點的值

都要大于其左子樹的所有節(jié)點的值，

都要小于其右子樹的所有節(jié)點的值。

在葉子節(jié)點上沒有左右孩子，

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

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

對于每一個節(jié)點來說，

它的左子樹所有的節(jié)點都比這個節(jié)點小，

它的右子樹所有的節(jié)點都比這個節(jié)點大，

那么用二分搜索樹來存儲數(shù)據(jù)的話，

那么再來查找一個數(shù)據(jù)就會變得非常簡單，

可以很快的知道從左側(cè)找還是右側(cè)找，

甚至可以不用看另外一側(cè)，

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

在生活中使用樹結(jié)構(gòu)，本質(zhì)也是如此，

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

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

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

這也是樹這種結(jié)構(gòu)存儲數(shù)據(jù)之后再對數(shù)據(jù)進行操作時

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

為了能夠達到二分搜索樹的性質(zhì)

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

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

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

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

在鏈表和數(shù)組中則沒有這個要求，

這個就是二分搜索樹存儲數(shù)據(jù)的一個局限性，

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

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

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

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

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

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

泛型 E 必須滿足 Comparable，

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

代碼實現(xiàn)

   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;
         }
   }

如果二分搜索樹的根節(jié)點為空的話

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

如果再添加一個元素，那么就因該從根節(jié)點出發(fā)，

根據(jù)二分搜索樹的定義，

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

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

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

根節(jié)點的左子樹上只有一個節(jié)點，

那么這個節(jié)點就是左子樹上的根節(jié)點，

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

按照這樣的規(guī)則，每來一個新元素從根節(jié)點開始，

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

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

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

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

一層一層向下比較新添加的節(jié)點的值，

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

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

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

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

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

也就是不添加進去，因為已經(jīng)有了，

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

如果想包含重復元素，

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

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

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

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

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

因為遞歸算法的很多細節(jié)和內(nèi)容需要不斷去體會，

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

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

雖然在現(xiàn)代計算機上這些開銷并不明顯，

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

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

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

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

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

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

代碼

   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 是對用戶屏蔽的，用戶不用知道二分搜索樹中有怎樣一個節(jié)點結(jié)構(gòu)

               // 如果出現(xiàn)相同的元素就不進行操作了
               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;
               }

               // 這里是處理節(jié)點被占了，那就進入下一個層的二叉樹中
               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 的左或右孩子中，

因為這一層節(jié)點已經(jīng)滿了，只能考慮下一層了，

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

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

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

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

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

代碼

   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
         // 改進：直接調(diào)用add
         public void add (E e) {
               root = add(root, e);
         }

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

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

               // 空的二叉樹也是叉樹。
               if (e.compareTo(node.e) < 0) {
                     // 將處理后的結(jié)果賦值給node的左子樹
                     node.left =  add(node.left, e);
               } else if (e.compareTo(node.e) > 0) {
                     // 將處理后的結(jié)果賦值給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 是對用戶屏蔽的，用戶不用知道二分搜索樹中有怎樣一個節(jié)點結(jié)構(gòu)
   //
   //        // 如果出現(xiàn)相同的元素就不進行操作了
   //        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;
   //        }
   //
   //        // 這里是處理節(jié)點被占了，那就進入下一個層的二叉樹中
   //        if (e.compareTo(node.e) < 0) {
   //            // 去左子樹
   //            add(node.left, e);
   //        } else { // e.compareTo(node.e) > 0
   //            // 去右子樹
   //            add(node.right, e);
   //        }
   //    }
   }

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

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

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

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

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

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

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

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

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

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

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

查詢操作非常的容易

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

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

和添加元素一樣需要使用遞歸的進行實現(xiàn)

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

逐漸的轉(zhuǎn)移在二分搜索樹的子樹中縮小問題的規(guī)模，

縮小查詢的樹的規(guī)模，直到找到這個元素 e 或者發(fā)現(xiàn)找不到這個元素 e。

在數(shù)組和鏈表中有索引這個概念，

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

代碼

   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
         // 改進：直接調(diào)用add
         public void add (E e) {
               root = add(root, e);
         }

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

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

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

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

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

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

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

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

遍歷操作就是把這個數(shù)據(jù)結(jié)構(gòu)中所有的元素都訪問一遍

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

訪問數(shù)據(jù)結(jié)構(gòu)中存儲的所有元素是因為與業(yè)務相關，

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

由于你的數(shù)據(jù)結(jié)構(gòu)是用來存儲數(shù)據(jù)的，

不僅可以查詢某些特定的數(shù)據(jù)，

還應該有相關的方式將所有的數(shù)據(jù)都進行訪問。

在線性結(jié)構(gòu)下，遍歷是極其容易的

無論是數(shù)組還是鏈表只要使用一下循環(huán)就好了，

但是這件事在樹結(jié)構(gòu)下沒有那么簡單，

但是也沒有那么難：）。

在樹結(jié)構(gòu)下遍歷操作并沒有那么難

如果你對樹結(jié)構(gòu)不熟悉，那么可能就有點難，

但是如果你熟悉了樹結(jié)構(gòu)，那么并非是那么難的操作，

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

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

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

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

先訪問這個節(jié)點，再訪問左右子樹，

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

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

從宏觀的角度來看，

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

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

這個代碼是怎樣怎樣一行一行去執(zhí)行的。

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

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

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

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

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

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

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

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

   // ... 要做的事情

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

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

      // 訪問該節(jié)點 兩邊都要顧及
      // 訪問該節(jié)點的時候就去做該做的事情，
      // 如 給所有學生加兩分
      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
         // 改進：直接調(diào)用add
         public void add (E e) {
               root = add(root, e);
         }

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

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

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

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

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

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

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

               // 如果 e 小于當前節(jié)點的e 則向左子樹進發(fā)
               if (e.compareTo(node.e) < 0) {
                   return contains(node.left, e);
               } else if (e.compareTo(node.e) > 0) { // 如果 e 大于當前節(jié)點的e 則向右子樹進發(fā)
                   return contains(node.right, e);
               } else { // 如果e 等于 當前節(jié)點 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();
         }
   }

遍歷輸出二分搜索樹

可以寫一個輔助函數(shù)自動遍歷所有節(jié)點生成字符串，

輔助函數(shù)叫做 generateBSTString，

這個函數(shù)的作用是，生成以 node 為根節(jié)點，

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

這樣一來要新增一個輔助函數(shù)，

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

這個輔助函數(shù)叫做 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
         // 改進：直接調(diào)用add
         public void add (E e) {
               root = add(root, e);
         }

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

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

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

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

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

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

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

               // 如果 e 小于當前節(jié)點的e 則向左子樹進發(fā)
               if (e.compareTo(node.e) < 0) {
                   return contains(node.left, e);
               } else if (e.compareTo(node.e) > 0) { // 如果 e 大于當前節(jié)點的e 則向右子樹進發(fā)
                   return contains(node.right, e);
               } else { // 如果e 等于 當前節(jié)點 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為根節(jié)點，深度為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();

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

前序遍歷

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

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

如果沒有特殊情況的話，

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

先訪問這個節(jié)點，

然后訪問這個節(jié)點的左子樹，

再訪問這個節(jié)點的右子樹，

整個過程循環(huán)往復。

前序遍歷的前表示先訪問的這個節(jié)點。

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

   // ... 要做的事情
   // 訪問該節(jié)點

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

中序遍歷

先訪問左子樹，再訪問這個節(jié)點，

最后訪問右子樹，整個過程循環(huán)往復。

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

然后再訪問這個節(jié)點，最后訪問右子樹，

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

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

   inOrder(node.left);

   // ... 要做的事情
   // 訪問該節(jié)點

   inOrder(node.right);
}

中序遍歷后輸出的結(jié)果是排序后的結(jié)果。

中序遍歷的結(jié)果是二分搜索樹中

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

后序遍歷

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

最后訪問這個節(jié)點，整個過程循環(huán)往復。

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

然后再訪問右子樹，最后訪問這個節(jié)點，

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

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

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

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

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

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

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

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

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

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

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

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

所以不需要你對內(nèi)存管理進行手動的控制，

c++ 語言中需要手動的控制內(nèi)存，

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

對于一些樹結(jié)構(gòu)的問題，

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

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

樹形問題有分治算法、回溯算法、動態(tài)規(guī)劃算法等等。

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

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

很多時候?qū)σ恍﹩栴}的分析，如果直接給你一個樹結(jié)構(gòu)，

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

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

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

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

也可以幫助你理解二分搜索樹這種數(shù)據(jù)結(jié)構(gòu)。

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
         // 改進：直接調(diào)用add
         public void add (E e) {
               root = add(root, e);
         }

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

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

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

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

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

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

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

               // 如果 e 小于當前節(jié)點的e 則向左子樹進發(fā)
               if (e.compareTo(node.e) < 0) {
                   return contains(node.left, e);
               } else if (e.compareTo(node.e) > 0) { // 如果 e 大于當前節(jié)點的e 則向右子樹進發(fā)
                   return contains(node.right, e);
               } else { // 如果e 等于 當前節(jié)點 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);
         }

         // 后續(xù)遍歷以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為根節(jié)點，深度為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();

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

再看二分搜索樹的遍歷

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

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

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

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

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

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

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

在哪里輸出訪問的這個節(jié)點的值，

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

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

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

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

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

   traverse(node.left);

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

   traverse(node.right);

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

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

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

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

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

前序遍歷的遞歸寫法

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

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

如果沒有特殊情況的話，

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

先訪問這個節(jié)點，

然后訪問這個節(jié)點的左子樹，

再訪問這個節(jié)點的右子樹，

整個過程循環(huán)往復。

前序遍歷的前表示先訪問的這個節(jié)點。

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

   // ... 要做的事情
   // 訪問該節(jié)點

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

前序遍歷的非遞歸寫法

使用另外一個數(shù)據(jù)結(jié)構(gòu)棧來模擬遞歸調(diào)用時的系統(tǒng)棧。

先訪問根節(jié)點，將根節(jié)點壓入棧，

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

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

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

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

這是因為棧是后入先出的，所以要先壓入后續(xù)要訪問的那個節(jié)點，

再讓棧頂?shù)脑爻鰲＃瑢@個節(jié)點進行操作，

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

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

那么什么都不用壓入了， 再去取棧頂?shù)脑兀?/p>

對這個節(jié)點進行操作，這個節(jié)點操作完畢之后，

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

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

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

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

這個過程非常像使用棧模擬了一下在系統(tǒng)棧中相應的一個調(diào)用，

相當于在系統(tǒng)棧中記錄下一步依次要訪問哪些節(jié)點。

將遞歸算法轉(zhuǎn)換為非遞歸算法

是棧這種數(shù)據(jù)結(jié)構(gòu)非常重要的一種應用。

二分搜索樹遍歷的非遞歸實現(xiàn)比遞歸實現(xiàn)復雜很多

因為你使用了一個輔助的數(shù)據(jù)結(jié)構(gòu)才能完成這個過程，

使用了棧這種數(shù)據(jù)結(jié)構(gòu)模擬了系統(tǒng)調(diào)用棧，

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

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

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

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

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

主要是鍛煉你算法實現(xiàn)、思維邏輯實現(xiàn)思路，

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

可以通過查看網(wǎng)上的資料來解決這個問題，

這樣的問題有可能會在面試題及考試中出現(xiàn)，

也就是中序和后序遍歷相應的非遞歸實現(xiàn)。

在經(jīng)典的教科書中一般都會有這三種遍歷的非遞歸實現(xiàn)，

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

完全可以使用模擬系統(tǒng)的棧來完成遞歸轉(zhuǎn)成非遞歸這樣的操作，

在慕課上 有一門課《玩轉(zhuǎn)算法面試》中完全模擬了系統(tǒng)棧的寫法，

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

這與經(jīng)典的教科書上的實現(xiàn)不一樣，

但是這種方式對你進一步理解棧這種數(shù)據(jù)結(jié)構(gòu)還是二分搜索樹的遍歷

甚至是系統(tǒng)調(diào)用的過程都是很有意義的。

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

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

這樣的一種遍歷方式也叫深度優(yōu)先遍歷，

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

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

所以這種遍歷就叫做深度優(yōu)先遍歷。

與深度優(yōu)先遍歷相對應的就是廣度優(yōu)先遍歷，

廣度優(yōu)先遍歷遍歷出來的結(jié)果它的順序其實是

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

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
            // 改進：直接調(diào)用add
            public void add (E e) {
                  root = add(root, e);
            }

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

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

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

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

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

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

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

                  // 如果 e 小于當前節(jié)點的e 則向左子樹進發(fā)
                  if (e.compareTo(node.e) < 0) {
                      return contains(node.left, e);
                  } else if (e.compareTo(node.e) > 0) { // 如果 e 大于當前節(jié)點的e 則向右子樹進發(fā)
                      return contains(node.right, e);
                  } else { // 如果e 等于 當前節(jié)點 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);
            }

            // 后續(xù)遍歷以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為根節(jié)點，深度為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();

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

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

它們本質(zhì)上都是深度優(yōu)先遍歷。

對于二分搜索樹來說

每一個節(jié)點都有一個相應的深度的值，

根節(jié)點作為深度為 0 相應的節(jié)點，

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