共计 43310 个字符，预计需要花费 109 分钟才能阅读完成。
前言
【从蛋壳到满天飞】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 主要用于处理字符串这类特殊的数据，
要想实现快速搜索的算法，
它的本质依然是需要使用树结构的，
树结构不见得是显式的展示在你面前，
它同时也可以用来处理很多抽象的问题，
这就像栈的应用一样，
从用户的角度看只看撤销这个操作或者只看括号匹配的操作，
用户根本想不到这背后使用了一个栈的数据结构，
但是为了组建出这样的功能是需要使用这种数据结构的，
同理树也是如此，很多看起来非常高效的运算结果，
它的背后其实是因为有树这种数据结构作为支撑的，
这也是数据结构、包括数据结构在计算机科学领域非常重要的意义，
数据结构虽然解决的是数据存储的问题，
但是在使用的层面上不仅仅是因为要存储数据，
更重要的是在你使用某些特殊的数据结构存储数据后，
可以帮助你辅助你更加高效的解决某些算法问题
甚至对于某些问题来说如果没有这些数据结构，
那么根本无从解决。
二分搜索树(Binary Search Tree)
二叉树
和链表一样，也属于动态数据结构，
不需要创建这个数据结构的时候就定好存储的容量，
如果要添加元素，直接 new 一个新的空间，
然后把它添加到这个数据结构中，删除也是同理，
每一个元素也是存到一个节点中，
这个节点和链表不同，它除了要存放这个元素 e，
它还有两个指向其它节点的变量，分别叫做 left、right，
class Node {
E e;
Node left;
Node right;
}
二叉树也叫多叉树，
它每一个节点最多只能分成两个叉，
根据这个定义也能定义出多叉树，
如果每个节点可以分出十个叉，
那就可以叫它十叉树，能分多少叉就叫多少叉树，
Trie 字典书本身就是一个多叉树。
在数据结构领域对应树结构来说
二叉树是最常用的一种树结构，
二叉树具有一个唯一的根节点，
也就是最上面的节点。
每一个节点最多有两个子节点，
这两个子节点分别叫做这个节点的左孩子和右孩子，
子节点指向左边的那个节点就是左孩子，
子节点指向右边的那个节点就是右孩子。
二叉树每个节点最多有两个孩子，
一个孩子都没有的节点通常称之为叶子节点，
二叉树每个节点最多有一个父亲，
根节点是没有父亲节点的。
二叉树和链表一样具有天然递归的结构
链表本身是线性的，
它的操作既可以使用循环也可以使用递归。
和树相关的很多操作，
使用递归的方式去写要比使用非递归的方式简单很多。
二叉树每一个节点的左孩子同时也是一个二叉树的根节点，
通常叫管这棵二叉树做左子树。
二叉树每一个节点的右孩子同时也是一个二叉树的根节点，
通常叫管这棵二叉树做右子树。
也就是说每一个二叉树它的左侧和右侧右分别连接了两个二叉树，
这两个二叉树都是节点个数更小的二叉树，
这就是二叉树所具有的天然的递归结构。
二叉树不一定是“满”的
满二叉树就是除了叶子节点之外，
每一个节点都有两个孩子。
就算你整个二叉树上只有一个节点，
它也是一个二叉树，只不过它的左右孩子都是空，
这棵二叉树只有一个根节点，
甚至 NULL(空)也是一棵二叉树。
就像链表中，只有一个节点它也是一个链表，
也可以把 NULL(空)看作是一个链表。
二分搜索树是一棵二叉树
在二叉树定义下所有其它的术语在二分搜索树中也适用，
如 根节点、叶子节点、左孩子右孩子、左子树、右子树、
父亲节点等等，这些在二分搜索树中也一样。
二分搜索树的每一个节点的值
都要大于其左子树的所有节点的值，
都要小于其右子树的所有节点的值。
在叶子节点上没有左右孩子，
那就相当于也满足这个条件。
二分搜索树的每一棵子树也是二分搜索树
对于每一个节点来说，
它的左子树所有的节点都比这个节点小，
它的右子树所有的节点都比这个节点大，
那么用二分搜索树来存储数据的话，
那么再来查找一个数据就会变得非常简单，
可以很快的知道从左侧找还是右侧找，
甚至可以不用看另外一侧，
所以就大大的加快了查询速度。
在生活中使用树结构，本质也是如此，
例如我要找一本 java 编程的书，
那么进入图书馆我直接进入计算机科学这个区域找这本书，
其它的类的图书我根本不用去管，
这也是树这种结构存储数据之后再对数据进行操作时
才能够非常高效的核心原因。
为了能够达到二分搜索树的性质
必须让存储的元素具有可比较性，
你要定义好 元素之间如何进行比较，
因为比较的方式是具有多种的，
必须保证元素之间可以进行比较。
在链表和数组中则没有这个要求，
这个就是二分搜索树存储数据的一个局限性，
也说明了凡事都是有代价的，
如果想加快搜索的话就必须对数据有一定的要求。
代码示例
二分搜索树其实不是支持所有的类型
所以应该对元素的类型有所限制，
这个限制就是 这个类型必须拥有可比较性，
所以在 java 里面的表示就是 对泛型进行约束，
泛型 E 必须满足 Comparable<E>，
也就是这个类型 E 必须具有可比较性。
代码实现
public class MyBinarySearchTree<E extends Comparable<E>> {
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<E extends Comparable<E>> {
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<E extends Comparable<E>> {
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<E extends Comparable<E>> {
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);
}
}
代码示例(class: MyBinarySearchTree, class: Main)
MyBinarySearchTree
public class MyBinarySearchTree<E extends Comparable<E>> {
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<Integer> mbst = new MyBinarySearchTree<Integer>();
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。
代码示例(class: MyBinarySearchTree, class: Main)
MyBinarySearchTree
public class MyBinarySearchTree<E extends Comparable<E>> {
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\n”);
return;
}
sb.append(generateDepthString(depath) + node.e + “\n”);
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<Integer> mbst = new MyBinarySearchTree<Integer>();
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++ 语言中需要手动的控制内存，
那么在二分搜索树内存释放这方面就需要使用后序遍历。
对于一些树结构的问题，
很多时候也是需要先针对一个节点的孩子节点求解出答案，
最终再由这些答案组合成针对这个节点的答案，
树形问题有分治算法、回溯算法、动态规划算法等等。
二分搜索树的前中后序遍历
主要从程序的角度进行分析，
很多时候对一些问题的分析，如果直接给你一个树结构，
然后你能够直接看出来对于这棵树来说它的前中后序遍历的结果是怎样的，
那就可以大大加快解决问题的速度，
同时这样的一个问题也是和计算机相关的考试的题目，
对于这样的一个问题的更加深入的理解
也可以帮助你理解二分搜索树这种数据结构。
代码示例(class: MyBinarySearchTree, class: Main)
MyBinarySearchTree
public class MyBinarySearchTree<E extends Comparable<E>> {
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\n”);
return;
}
sb.append(generateDepthString(depath) + node.e + “\n”);
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<Integer> mbst = new MyBinarySearchTree<Integer>();
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);
}
前序遍历的非递归写法
使用另外一个数据结构栈来模拟递归调用时的系统栈。
先访问根节点，将根节点压入栈，
然后把栈顶元素拿出来，对这个节点进行操作，
这个节点操作完毕之后，再访问这个节点的两个子树，
也就是把这个节点的左右两个孩子压入栈中，
压入栈的顺序是先压入右孩子、再压入左孩子，
这是因为栈是后入先出的，所以要先压入后续要访问的那个节点，
再让栈顶的元素出栈，对这个节点进行操作，
这个节点操作完毕之后，再访问这个节点的两个子树，
但是这个节点是叶子节点，它的两个孩子都为空，
那么什么都不用压入了，再去取栈顶的元素，
对这个节点进行操作，这个节点操作完毕之后，
再访问这个节点的两个子树，但是这个节点也是叶子节点，
那么什么都不用压入了，栈中也为空了，整个访问操作结束。
无论是非递归还是递归的写法，结果都是一致的
非递归的写法中，栈的应用是帮助你记录你下面要访问的哪些节点，
这个过程非常像使用栈模拟了一下在系统栈中相应的一个调用，
相当于在系统栈中记录下一步依次要访问哪些节点。
将递归算法转换为非递归算法
是栈这种数据结构非常重要的一种应用。
二分搜索树遍历的非递归实现比递归实现复杂很多
因为你使用了一个辅助的数据结构才能完成这个过程，
使用了栈这种数据结构模拟了系统调用栈，
在算法语意解读上远远比递归实现的算法语意解读要难很多。
二分搜索树的中序遍历和后序遍历的非递归实现更复杂
尤其是对于后序遍历来说难度更大，
但是中序遍历和后序遍历的非递归实现，实际应用并不广泛。
但是你可以尝试实现中序、后序遍历的非递归实现，
主要是锻炼你算法实现、思维逻辑实现思路，
在解决这个问题的过程中可能会遇到一些困难，
可以通过查看网上的资料来解决这个问题，
这样的问题有可能会在面试题及考试中出现，
也就是中序和后序遍历相应的非递归实现。
在经典的教科书中一般都会有这三种遍历的非递归实现，
通过二分搜索树的前序遍历非递归的实现方式中可以看出，
完全可以使用模拟系统的栈来完成递归转成非递归这样的操作，
在慕课上 有一门课《玩转算法面试》中完全模拟了系统栈的写法，
也就是将前中后序的遍历都转成了非递归的算法，
这与经典的教科书上的实现不一样，
但是这种方式对你进一步理解栈这种数据结构还是二分搜索树的遍历
甚至是系统调用的过程都是很有意义的。
对于前序遍历来说无论是递归写法还是非递归写法
对于这棵树来说都是在遍历的过程中一直到底，
这样的一种遍历方式也叫深度优先遍历，
最终的遍历结果都会先来到整颗树最深的地方，
直到不能再深了才会开始返回到上一层，
所以这种遍历就叫做深度优先遍历。
与深度优先遍历相对应的就是广度优先遍历，
广度优先遍历遍历出来的结果它的顺序其实是
整个二分搜索树的一个层序遍历的顺序。
代码示例(class: MyBinarySearchTree, class: Main)
MyBinarySearchTree
import java.util.Stack;
public class MyBinarySearchTree<E extends Comparable<E>> {
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<Node> stack = new Stack<Node>();
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\n”);
return;
}
sb.append(generateDepthString(depath) + node.e + “\n”);
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<Integer> mbst = new MyBinarySearchTree<Integer>();
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 相应的节点，
如果以计算机世界里索引的定义为准那就是使用 0，
根节点就是第 0 层。
先遍历第 0 层、再遍历第 1 层、再遍历下一层，
这样的一层一层的遍历就称为广度优先遍历，
逐层向下遍历的节点在广度上进行拓展，
这样的一个遍历顺序就叫做层序遍历、广度优先遍历，
而不像之前那样 先顺着一个枝杈向着最深的地方走。
对于层序遍历的实现或者广度优先遍历的实现
通常不是使用递归的方式进行实现的，
而是使用非递归的方式进行实现的，
并且在其中需要使用另外的一个数据结构队列，
从根节点开始排着队的进入这个队列，
队列中存储的就是待遍历的元素，
每一次遍历的它的元素之后再将它的左右孩子也排进队列中，
整个过程依此类推。
先入队根节点，然后看队首是否有元素，
有的话就对队首的元素进行操作，
操作完毕后就将操作完毕的元素的左右孩子也入队，
然后再对队列中的元素进行操作，
队列中的元素又操作完毕了，
再让操作完毕的这些元素的左右孩子入队，
最后在对队列中的元素进行操作，
这些元素都是叶子节点没有左右孩子了，，
不用入队了，队列中没有元素，整个过程处理完毕，
这个处理过程就是一层一层的进行处理的一个顺序，
这就是二分搜索树的广度优先遍历，也叫层序遍历。
相对于深度优先遍历来说，广度优先遍历的优点
它能更快的找到你想要查询的那个元素，
这样的区别主要用于搜索策略上，
而不是用在遍历这个操作上，
虽然遍历要将整个二叉树上所有的元素都访问一遍，
这种情况下深度优先遍历和广度优先遍历是没有区别的。
但是如果想在一棵树中找到某一个问题的解，
那对于深度优先遍历来说
它会从根节点一股脑的跑到这棵树非常深的地方，
但是很有可能这个问题的解并不在那么深的地方而是很浅的地方，
这样一来深度优先遍历要花很长时间才能访问到这个很浅的地方，
例如前序遍历，如果这个问题的解在右子树上很浅的位置，
你从一开始就从根节点遍历到左子树的最深处，那就没必要了，
但是这个常用于算法设计中，如无权图的最短路径，
树这种结构在算法设计里也有非常重要的应用，
尤其是很多时候设计出一个算法，可能真正不需要把这个树发现出来，
但是这个算法的整个过程就是在一棵虚拟的树中完成的。
在图中也是有深度优先遍历和广度优先遍历的
在树中和图中进行深度优先遍历其实它们的实质是一样的，
不同的点，对于图来说需要记录一下对于某一个节点之前是否曾经遍历过，
因为对于图来说每一个节点的前驱或者放在树这个模型中
相应的术语就是每一节点它的父亲可能有多个，
从而产生重复访问这样的问题，而这样的问题在树结构中是不存在的，
所以在图结构中需要做一个相应的记录。
代码示例(class: MyBinarySearchTree, class: Main)
MyBinarySearchTree
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class MyBinarySearchTree<E extends Comparable<E>> {
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<Node> stack = new Stack<Node>();
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);
}
// 二分搜索树的层序遍历
public void levelOrder () {
// java 中的 Queue 是一个接口，但是它有链表和队列的实现，
// 所以你可以 new 一个子类链表类来进行进行使用，可以达到同样的效果
Queue<Node> queue = new LinkedList<Node>();
queue.add(root);
while (!queue.isEmpty()) {
Node node = queue.remove();
System.out.println(node.e);
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(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\n”);
return;
}
sb.append(generateDepthString(depath) + node.e + “\n”);
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<Integer> mbst = new MyBinarySearchTree<Integer>();
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();
mbst.levelOrder(); // 5 3 6 2 4 8
System.out.println();
// // 输出 调试字符串
// System.out.println(mbst.toString());
}
}
学习方法
很多时候学习知识
并不是简单的一块儿一块儿把它们学过了就可以了，
很多时候要想能够达到灵活运用能够达到理解的深刻，都需要进行比对，
刻意的去找到从不同方法之间它们的区别和联系，
以及自己去总结不同的方法适用于什么样的场合，
只有这样，这些知识才能够在你的脑海中才不是一个一个的碎片，
而是有机的联系起来的，面对不同的问题才能非常的快的
并且准确的说出来用怎样的方法去解决更加的好。
二分搜索树的删除节点 - 删除最大最小值
对于二分搜索树来说删除一个节点相对来说是比较复杂的
可以先对这个操作进行拆解，从最简单的开始。
删除二分搜索树的最小值和最大值
删除二分搜索树中任意元素会复用到
删除二分搜索树最大值和最小值相应的逻辑。
要想删除二分搜索树中最大值和最小值，
那么就要先找到二分搜索树中的最大值和最小值。
找到二分搜索树中的最大值和最小值是非常容易的
每一个节点的左子树上所有的节点的值都小于当前这个节点，
每一个节点的右子树上所有的节点的值都大于当前这个节点，
那么从根节点开始一直向左，直到不能再左了，就能找到最小值，
反之从根节点开始一直向右，知道不能再右了，就能找到最大值。
这个操作就像操作链表一样，就像是在找一条链上的尾节点。
删除最大元素节点
要删除最大元素的这个节点可能有左孩子节点但是没有右孩子节点，
所以可能会导致无法继续向右于是递归就终止了，
那么这个时候删除这个节点可以采用当前节点的左孩子替代当前这个节点，
覆盖操作也算是删除了当前这个节点了。
如果你像返回被删除的这个最大元素节点，你可以先查询出这个最大的元素节点，
然后存到一个变量中，最后再调用删除这个最大元素节点的方法，最终返回存的这个变量。
删除最小元素节点
要删除的最小元素的节点可能有右孩子节点但是没有左孩子节点，
会导致无法继续向左而递归终止，你不能删除这个节点的同时连右孩子一起删除，
所以这个时候删除这个节点可以采用当前节点的右孩子替代当前这个节点，
覆盖操作也算是删除了当前这个节点了，
其它的和删除最大元素一样，先查询出来，然后存起来，删除这个最大元素后，
再返回之前存起来的最大元素的变量。
代码示例(class: MyBinarySearchTree, class: Main)
MyBinarySearchTree
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class MyBinarySearchTree<E extends Comparable<E>> {
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<Node> stack = new Stack<Node>();
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);
}
// 二分搜索树的层序遍历
public void levelOrder () {
// java 中的 Queue 是一个接口，但是它有链表和队列的实现，
// 所以你可以 new 一个子类链表类来进行进行使用，可以达到同样的效果
Queue<Node> queue = new LinkedList<Node>();
queue.add(root);
while (!queue.isEmpty()) {
Node node = queue.remove();
System.out.println(node.e);
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
}
// 寻找二分搜索树的最小值元素
public E minimum () {
if (size == 0) {
throw new IllegalArgumentException(“BST is empty.”);
}
return minimum(root).e;
}
// 返回以 node 为根的二分搜索树的最小值所在的节点
private Node minimum (Node node) {
// 向左走再也走不动了，就返回这个节点。
if (node.left == null) return node;
return minimum(node.left);
}
// 从二分搜索树种删除最小值所在节点，返回这个最小值
public E removeMin () {
E result = minimum();
// removeMin(root);
root = removeMin(root);
return result;
}
// 删除掉以 node 为根的二分搜索树中的最小节点
// 返回删除节点后新的二分搜索树的根
private Node removeMin (Node node) {
// if (node.left == null) {
// node = node.right;
// size –;
// return node;
// }
//
// return removeMin(node.left);
if (node.left == null) {
Node rightNode = node.right;
node.right = null;
size –;
return rightNode;
}
node.left = removeMin(node.left);
return node;
}
// 寻找二分搜索树的最大值元素
public E maximum () {
if (size == 0) {
throw new IllegalArgumentException(“BST is empty.”);
}
return maximum(root).e;
}
// 返回以 node 为根的二分搜索树的最大值所在的节点
private Node maximum (Node node) {
// 向右走再也走不动了，就返回这个节点。
if (node.right == null) return node;
return maximum(node.right);
}
// 从二分搜索树种删除最大值所在节点，返回这个最大值
public E removeMax () {
E result = maximum();
root = removeMax(root);
return result;
}
// 删除掉以 node 为根的二分搜索树中的最大节点
// 返回删除节点后新的二分搜索树的根
private Node removeMax (Node node) {
if (node.right == null) {
Node leftNode = node.left;
node.left = null;
size –;
return leftNode;
}
node.right = removeMax(node.right);
return node;
}
@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\n”);
return;
}
sb.append(generateDepthString(depath) + node.e + “\n”);
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
import java.util.ArrayList;
import java.util.Random;
public class Main {
public static void main(String[] args) {
MyBinarySearchTree<Integer> mbst = new MyBinarySearchTree<Integer>();
Random random = new Random();
int n = 100;
for (int i = 0; i < n; i++) {
mbst.add(random.nextInt(Integer.MAX_VALUE));
}
// 动态数组
ArrayList<Integer> arrayList = new ArrayList<Integer>();
while (!mbst.isEmpty()) {
arrayList.add(mbst.removeMin());
// arrayList.add(mbst.removeMax());
}
// 数组中就是从小到大排序的
System.out.println(arrayList);
// 验证一下
for (int i = 1; i < arrayList.size() ; i++) {
// 如果前面的数大于后面的数就报异常
if (arrayList.get(i – 1) > arrayList.get(i)) {
// 如果前面的数小于后面的数就报异常
// if (arrayList.get(i – 1) < arrayList.get(i)) {
throw new IllegalArgumentException(“error.”);
}
}
System.out.println(“removeMin test completed.”);
// System.out.println(“removeMax test completed.”);
}
}
二分搜索树的删除节点 - 删除任意元素
在二分搜索树种删除最大值最小值的逻辑
从根节点开始，向左或者向右遍历，
遍历到最左或者最右时，
记录这个节点的右子树或者左子树，
然后返回，然后让这条分支上每个节点的左或者右子树进行层层覆盖，
然后层层返回新的节点，直到最后返回给根节点、覆盖掉根节点，
从而达到了删除最小或最大节点的目的。
删除最小值的节点就不停的向左遍历，最后记录右子树，
因为被删除的节点要被这个节点的右子树替代掉，
只有这样才能够达到删除最小值的节点的效果。
删除最大值的节点就不停的向右遍历，最后记录左子树，
因为被删除的节点要被这个节点的左子树替代掉，
只有这样才能够达到删除最大值的节点的效果。
删除二分搜索树上任意节点会发生的情况
删除的这个节点只有左孩子，这个逻辑和上面的类似，
就让这个节点的左孩子取代这个节点的位置。
删除的这个节点只有右孩子，这个逻辑也是一样，
就让这个节点的右孩子取代这个节点的位置。
删除的这个节点是叶子节点，这个逻辑也一样，
因为 null 也是一个二分搜索树、也是一个节点、也是一个孩子，
直接让 null 取代这个节点的位置即可。
真正难的地方是去删除左右都有孩子这样的节点，
在 1962 年，Hibbard(计算机科学家)提出 -Hibbard Deletion，
找到离这个节点的值最近并且大的那个节点来取代这个节点，
也就是找到 这个节点的右孩子的左孩子(右子树的左子树上最小的节点)，
例如待删除的节点为 d，那么就是 s = min(d->right)，
找到比当前节点大最小且最近的节点，这个 s 就是 d 的后继，
执行 s->right = delMin(d->right)这样的操作，
之后让 s->left = d->left，
删除的 d 后，s 是新的子树的根，返回这个 s 节点就可以了。
除了找待删除节点 d 的后继 s 之外，还可以找待删除节点的前驱 p，
也就是找到 这个节点的左孩子的右孩子(左子树的右子树上最大的节点)。
无论使用前驱还是后继来取代待删除的这个节点
都能够继续保持二分搜索树的性质。
对于二分搜索树来说
相对于数组、栈、队列、链表这些数据结构要复杂一些，
二分搜索树本身也是学习其它的树，如 平衡二叉树的基础。
代码示例(class: MyBinarySearchTree, class: Main)
MyBinarySearchTree
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class MyBinarySearchTree<E extends Comparable<E>> {
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<Node> stack = new Stack<Node>();
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);
}
// 二分搜索树的层序遍历
public void levelOrder () {
// java 中的 Queue 是一个接口，但是它有链表和队列的实现，
// 所以你可以 new 一个子类链表类来进行进行使用，可以达到同样的效果
Queue<Node> queue = new LinkedList<Node>();
queue.add(root);
while (!queue.isEmpty()) {
Node node = queue.remove();
System.out.println(node.e);
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
}
// 寻找二分搜索树的最小值元素
public E minimum () {
if (size == 0) {
throw new IllegalArgumentException(“BST is empty.”);
}
return minimum(root).e;
}
// 返回以 node 为根的二分搜索树的最小值所在的节点
private Node minimum (Node node) {
// 向左走再也走不动了，就返回这个节点。
if (node.left == null) return node;
return minimum(node.left);
}
// 从二分搜索树种删除最小值所在节点，返回这个最小值
public E removeMin () {
E result = minimum();
// removeMin(root);
root = removeMin(root);
return result;
}
// 删除掉以 node 为根的二分搜索树中的最小节点
// 返回删除节点后新的二分搜索树的根
private Node removeMin (Node node) {
// if (node.left == null) {
// node = node.right;
// size –;
// return node;
// }
//
// return removeMin(node.left);
if (node.left == null) {
Node rightNode = node.right;
node.right = null;
size –;
return rightNode;
}
node.left = removeMin(node.left);
return node;
}
// 寻找二分搜索树的最大值元素
public E maximum () {
if (size == 0) {
throw new IllegalArgumentException(“BST is empty.”);
}
return maximum(root).e;
}
// 返回以 node 为根的二分搜索树的最大值所在的节点
private Node maximum (Node node) {
// 向右走再也走不动了，就返回这个节点。
if (node.right == null) return node;
return maximum(node.right);
}
// 从二分搜索树种删除最大值所在节点，返回这个最大值
public E removeMax () {
E result = maximum();
root = removeMax(root);
return result;
}
// 删除掉以 node 为根的二分搜索树中的最大节点
// 返回删除节点后新的二分搜索树的根
private Node removeMax (Node node) {
if (node.right == null) {
Node leftNode = node.left;
node.left = null;
size –;
return leftNode;
}
node.right = removeMax(node.right);
return node;
}
// 从二分搜索树中删除元素 e 的节点
public void remove (E e) {
root = remove(root, e);
}
// 删除掉以 node 为根的二分搜索树中值为 e 的节点 递归算法
// 返回删除节点后新的二分搜索树的根
private Node remove(Node node, E e) {
if (node == null) return null;
if (e.compareTo(node.e) < 0) {
node.left = remove(node.left, e);
return node;
} else if (e.compareTo(node.e) > 0) {
node.right = remove(node.right, e);
return node;
} else {// e == node.e
// 待删除的节点左子树为空
if (node.left == null) {
Node rightNode = node.right;
node.right = null;
size –;
return rightNode;
}
// 待删除的节点右子树为空
if (node.right == null) {
Node leftNode = node.left;
node.left = null;
size –;
return leftNode;
}
// 待删除的节点左右子树都不为空的情况
// 找到比待删除节点大的最小节点，即待删除节点右子树的最小节点
// 用这个节点顶替待删除节点的位置
Node successor = minimum(node.right);
successor.right = removeMin(node.right);
// 在 removeMin 这个操作中维护了一次 size –，但是并没有删除节点
// 所以这里要进行一次 size ++ 操作
size ++;
successor.left = node.left;
// 让 node 这个节点与当前这个二分搜索树脱离关系
node.left = node.right = null;
// 维护一下 size
size –;
return successor;
}
}
@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\n”);
return;
}
sb.append(generateDepthString(depath) + node.e + “\n”);
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
import java.util.ArrayList;
import java.util.Random;
public class Main {
public static void main(String[] args) {
MyBinarySearchTree<Integer> mbst = new MyBinarySearchTree<Integer>();
// 动态数组
ArrayList<Integer> arrayList = new ArrayList<Integer>();
Random random = new Random();
int n = 10;
for (int i = 0; i < n; i++) {
int value = random.nextInt(Integer.MAX_VALUE);
mbst.add(value);
arrayList.add(value);
}
// 输出二分搜索树
System.out.println(mbst.getSize());
// 输出数组中内容
System.out.println(arrayList);
for (int i = 0; i < arrayList.size(); i++) {
mbst.remove(arrayList.get(i));
}
// 输出二分搜索树
System.out.println(mbst.getSize());
System.out.println(“remove test completed.”);
}
}
更多与二分搜索树相关
已经实现的二分搜索树功能
添加元素 add
删除元素 remove
查询元素 contains
遍历元素 order
其它实现的二分搜索树功能
可以非常方便的拿到二分搜索树中最大值和最小值，
这是因为二分搜索树本身有一个非常重要的特性，
也就是二分搜索树具有顺序性，
这个顺序性就是指 二分搜索树中所有的元素都是有序的，
例如使用中序遍历遍历的元素就是将元素从小到大排列起来，
也正是有顺序性才能够很方便的获得
二分搜索树中最大值 (maximum) 最小值(minimum)，
包括给定一个值可以拿到它的前驱 (predecessor) 和后继(successor)。
也因为这个顺序性也可以对它进行 floor 和 ceil 的操作，
也就是找比某一个元素值大的元素或者值小的元素，
前驱、后继中指定的元素一定要在这棵二分搜索树中，
而 floor 和 ceil 中指定的这个元素可以不在这棵二分搜索树中。
相应的二分搜索树还可以实现 rank 和 select 方法，
rank 也就是指定一个元素找到它的排名，
select 是一个反向的操作，也就是找到排名为多少名的那个元素。
对于二分搜索树来说都可以非常容易的实现这两个操作。
实现 rank 和 select 最好的方式是对于二分搜索树每一个节点
同时还维护一个 size，
这个 size 就是指以这个节点为根的二分搜索树有多少个元素，
也就是每一个节点为根的二分搜索树中有多少的元素，
那么这个 size 就为多少，
也就是每一个节点包括自己以及下面的子节点的个数，
每一个 node 在维护了一个 size 之后，
那么实现 rank 和 select 这两个操作就会容易很多，
也就是给 node 这个成员变量添加一个 size，
那么对于二分搜索树其它操作如添加和删除操作时，
也要去维护一下这个节点的 size，
只有这样实现这个 rank 和 select 就会非常简单，
这样做之后，对于整棵二分搜索树而言，
就不再需要二分搜索树的 size 变量了，
如果要看整棵二分搜索树有多少个节点，
直接看 root.size 就好了，非常的方便。
维护 depth 的二分搜索树
对于二分搜索树的每一个节点还可以维护一个深度值，
也就是这个节点的高度值，也就是这个节点处在第几层的位置，
维护这个值在一些情况下是非常有帮助的。
支持重复元素的二分搜索树
只需要定义每一个根节点的左子树所有的节点都是
小于等于这个根节点值的，
而每一个根节点的右子树所有的节点都是大于这个根节点值的，
这样的定义就很好的支持了重复元素的二叉树的实现。
还可以通过维护每一个节点的 count 变量来实现重复元素的二分搜索树，
也就是记录一下这个节点所代表的元素在这个二分搜索树中存储的个数，
当你添加进重复的节点后，直接让相应节点的 count++ 即可，
如果你删除这个重复的节点时，直接让相应节点的 count– 即可，
如果 count 减减之后为 0，那么就从二分搜索树中真正删除掉。
其它
在二分搜索树中相应的变种其实大多是在 node 中维护一些数据
就可以方便你进行一些其它特殊情况的处理，
相关的习题可以去 leetcode 中找到，
树标签：https://leetcode-cn.com/tag/tree/
如第一题，二叉树的最大深度，这个题和链表是非常像的，
它有一个答题的模板，你提交的时候要按照这个模板来进行提交。
其它
二分搜索树的复杂度分析，
二分搜索树有两个重要的应用集合和映射，
其实用数组和链表也能够实现集合和映射，
二分搜索树也有它的局限性。