【从蛋壳到满天飞】JAVA 数据结构解析和算法实现-二分搜索树

摘要：在数据结构领域对应树结构来说二叉树是最常用的一种树结构，二叉树具有一个唯一的根节点，也就是最上面的节点。二叉树每个节点最多有两个孩子，一个孩子都没有的节点通常称之为叶子节点，二叉树每个节点最多有一个父亲，根节点是没有父亲节点的。

【从蛋壳到满天飞】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 相