前言
线性数据结构是把所有的数据排成一排，树结构是倒立的树，由一个根节点延伸出很多新的分支节点。在计算机科学领域很多问题的处理，当你将数据使用树结构进行存储后，出奇的高效。
这篇文章讲的二分搜索树（Binary Search Tree），二分搜索树有它的局限性。后面还会有平衡二叉树：AVL;红黑树，除了他们，平衡二叉树还有很多种。
还是那句老话：光看文章能够掌握两成，动手敲代码、动脑思考、画图才可以掌握八成。源码仓库
不要完美主义。掌握好“度”。
太过于追求完美会把自己逼的太紧，会产生各种焦虑的心态，最后甚至会怀疑自己，温故而知新，不要停止不前，掌握好这个度，不存在你把那些你认为完全掌握了，然后就成了某一个领域的专家，相反一旦你产生很浓厚的厌恶感，那么就意味着你即将会放弃或者已经选择了放弃，虽然你之前想把它做到 100 分，但是由于你的放弃让它变为 0 分。
学习本着自己的目标去。不要在学的过程中偏离了自己的目标。要分清主次。
难的东西，你可以慢慢的回头看一看。那样才会更加的柳暗花明，更能提升自己的收获。
树结构
树结构本身是一个种天然的组织结构。如 电脑中文件夹目录结构就是树结构，这种结构来源于生活。比如 图书馆整体分成几个大馆，如 数理馆、文史馆等等，到了数理馆还要分成 很多的子类。如 数学类的图书、物理类的图书、化学类的图书，计算机类的图书，到了计算机类的图书还要再分成各种不同的子类。如 按语言分类 c++、java、c#、php、python、javascript 等等。如 按领域分类 网站编程、app 开发、游戏开发、前端、后端等等，每一个子领域可能又要分成很多领域，一直到最后索引到一本一本的书，这就是一个典型的树结构。
还有 一个公司的组织架构也是这样的一种树结构，从 CEO 开始下面可能有不同的部门，如财务部门(Marketing Head)、人事部门(HR Head)、技术部门(Finance Head)、市场部门(Audit Officer)等等，每个部门下面还有不同的职能分工，最后才到具体的一个一个人。
还有家谱，他本身也是一个树结构，其实树结构并不抽象，在生活中随处可见。
树结构非常的高效。比如文件管理，不可能将所有的文件放到一个文件夹中，然后用一个线性的结构进行存储，那样的话查找文件太麻烦了，但是如果给它做成树机构的话，那么就可以很容易的检索到目标文件，比如说我想检索到我的照片，直接找到个人文件夹，然后找到图片文件夹，最后找到自己的照片，这样就很快速很高效的找到了目标文件。
在公司使用这种树形的组织架构也是这个原因，CEO 想就技术开发的一些问题进行一些讨论，他肯定要找相应职能的一些人，他不需要去市场部门、营销部门、人事部门、财务部门、行政部门找人，他直接去技术部这样的开发部门去找人就好了，一下子就把查询的范围缩小了。
在数据结构领域设计树结构的本质也是如此。
算法需要使用一些特殊的操作的时候将数据组织成树结构，会针对某一类特殊的操作产生非常高效的结果，使用堆以及并查集，都是为了满足对数据某一个类特殊的操作进行高效的处理。
同时对于某些特殊的数据，很多时候可以另辟蹊径，将他们以某种形式存储成树结构，结果就是会对这类特殊的数据它们所在的那个领域的问题相应的解决方案提供极其高效的结果。
还有线段树、Trie(字典树、前缀树)，线段树主要用来处理线段这种特殊的数据，Trie 主要用于处理字符串这类特殊的数据，要想实现快速搜索的算法，它的本质依然是需要使用树结构的，树结构不见得是显式的展示在你面前，它同时也可以用来处理很多抽象的问题。
这就像栈的应用一样，从用户的角度看只看撤销这个操作或者只看括号匹配的操作，用户根本想不到这背后使用了一个栈的数据结构，但是为了组建出这样的功能是需要使用这种数据结构的。同理树也是如此，很多看起来非常高效的运算结果，它的背后其实是因为有树这种数据结构作为支撑的，这也是数据结构、包括数据结构在计算机科学领域非常重要的意义。
数据结构虽然解决的是数据存储的问题，但是在使用的层面上不仅仅是因为要存储数据，更重要的是在你使用某些特殊的数据结构存储数据后，可以帮助你辅助你更加高效的解决某些算法问题，甚至对于某些问题来说如果没有这些数据结构，那么根本无从解决。
二分搜索树(Binary Search Tree)
二叉树和链表一样，也属于动态数据结构，不需要创建这个数据结构的时候就定好存储的容量。如果要添加元素，直接 new 一个新的空间，然后把它添加到这个数据结构中，删除也是同理。每一个元素也是存到一个节点中，这个节点和链表不同，它除了要存放这个元素 e，它还有两个指向其它节点的变量，分别叫做 left、right。
class Node {
e; // Element
left; // Node
right; // Node
}二叉树也叫多叉树，它每一个节点最多只能分成两个叉，根据这个定义也能定义出多叉树，如果每个节点可以分出十个叉，那就可以叫它十叉树，能分多少叉就叫多少叉树，Trie 字典书本身就是一个多叉树。
在数据结构领域对应树结构来说，二叉树是最常用的一种树结构，二叉树具有一个唯一的根节点，也就是最上面的节点。每一个节点最多有两个子节点，这两个子节点分别叫做这个节点的左孩子和右孩子，子节点指向左边的那个节点就是左孩子，子节点指向右边的那个节点就是右孩子。
二叉树每个节点最多有两个孩子，一个孩子都没有的节点通常称之为叶子节点，二叉树每个节点最多有一个父亲，根节点是没有父亲节点的。
二叉树和链表一样具有天然递归的结构。链表本身是线性的，它的操作既可以使用循环也可以使用递归。和树相关的很多操作，使用递归的方式去写要比使用非递归的方式简单很多。
二叉树每一个节点的左孩子同时也是一个二叉树的根节点，通常叫管这棵二叉树做左子树。二叉树每一个节点的右孩子同时也是一个二叉树的根节点，通常叫管这棵二叉树做右子树。
也就是说每一个二叉树它的左侧和右侧右分别连接了两个二叉树，这两个二叉树都是节点个数更小的二叉树，这就是二叉树所具有的天然的递归结构。
二叉树不一定是“满”的。满二叉树就是除了叶子节点之外，每一个节点都有两个孩子。就算你整个二叉树上只有一个节点，它也是一个二叉树，只不过它的左右孩子都是空，这棵二叉树只有一个根节点，甚至 NULL(空)也是一棵二叉树。就像链表中，只有一个节点它也是一个链表，也可以把 NULL(空)看作是一个链表。
二分搜索树是一棵二叉树，在二叉树定义下所有其它的术语在二分搜索树中也适用，如 根节点、叶子节点、左孩子右孩子、左子树、右子树、父亲节点等等，这些在二分搜索树中也一样。
二分搜索树的每一个节点的值都要大于其左子树的所有节点的值，都要小于其右子树的所有节点的值。在叶子节点上没有左右孩子，那就相当于也满足这个条件。
二分搜索树的每一棵子树也是二分搜索树，对于每一个节点来说，它的左子树所有的节点都比这个节点小，它的右子树所有的节点都比这个节点大。那么用二分搜索树来存储数据的话，那么再来查找一个数据就会变得非常简单，可以很快的知道从左侧找还是右侧找，甚至可以不用看另外一侧，所以就大大的加快了查询速度。
在生活中使用树结构，本质也是如此，例如我要找一本 JS 编程的书，那么进入图书馆我直接进入计算机科学这个区域找这本书，其它的类的图书我根本不用去管，这也是树这种结构存储数据之后再对数据进行操作时才能够非常高效的核心原因。
为了能够达到二分搜索树的性质，必须让存储的元素具有可比较性，你要定义好 元素之间如何进行比较，因为比较的方式是具有多种的，必须保证元素之间可以进行比较。在链表和数组中则没有这个要求，这个就是二分搜索树存储数据的一个局限性，也说明了凡事都是有代价的，如果想加快搜索的话就必须对数据有一定的要求。
代码示例
二分搜索树其实不是支持所有的类型，所以应该对元素的类型有所限制，这个限制就是 这个类型必须拥有可比较性，也就是这个类型 element 必须具有可比较性。
class MyBinarySearchTreeNode {
constructor(element, left, right) {
// 实际存储的元素
this.element = element;
// 当前节点的左子树
this.left = left;
// 当前节点的右子树
this.right = right;
}
}
class MyBinarySearchTree {
constructor() {
this.root = null;
this.size = 0;
}
// 获取二分搜索树中节点个数
getSize() {
return this.size;
}
// 返回二分搜索树是否为空的bool值
isEmpty() {
return this.size === 0;
}
}向二分搜索树中添加元素
如果二分搜索树的根节点为空的话，第一个添加的元素就会成为根节点，如果再添加一个元素，那么就因该从根节点出发。根据二分搜索树的定义，每个节点的值要比它的左子树上所有节点的值大，假设第二个添加的元素的值小于第一个添加的元素的值，那么很显然第二个添加的元素要被添加到根节点的左子树上去。根节点的左子树上只有一个节点，那么这个节点就是左子树上的根节点，这个左子树上的根节点就是顶层根节点的左孩子。
按照这样的规则，每来一个新元素从根节点开始，如果小于根节点，那么就插入到根节点的左子树上去，如果大于根节点，那么就插入到根节点的右子树上去，由于不管是左子树还是右子树，它们又是一棵二分搜索树，那么这个过程就是依此类推下去，一层一层向下比较新添加的节点的值，大的向右，小的向左，不停的向下比较，如果这个位置没有被占住，那么就可以在这个位置上添加进去，如果这个位置被占了，那就不停的向下比较，直到找到一个合适的位置添加进去。
如果遇到两个元素的值相同，那暂时先不去管，也就是不添加进去，因为已经有了，自定义二分搜索树不包含重复元素，如果想包含重复元素，只需要定义左子树小于等于节点、或者右子树大于等于节点，只要把“等于”这种关系放进定义里就可以了。
二分搜索树添加元素的非递归写法，和链表很像，但是在二分搜索树方面的实现尽量使用递归来实现，就是要锻炼递归算法的书写，因为递归算法的很多细节和内容需要不断去体会，但是非递归的写法也很实用的，因为递归本身是具有更高的开销的，虽然在现代计算机上这些开销并不明显，但是在一些极端的情况下还是可以看出很大的区别，尤其是对于二分搜索树来说，在最坏的情况下它有可能会退化成一个链表，那么在这种情况下使用递归的方式很容易造成系统栈的溢出，二分搜索树一些非递归的实现你可以自己练习一下。
在二分搜索树方面，递归比非递归实现起来更加简单。
代码示例
class MyBinarySearchTreeNode {
constructor(element, left = null, right = null) {
// 实际存储的元素
this.element = element;
// 当前节点的左子树
this.left = left;
// 当前节点的右子树
this.right = right;
}
}
class MyBinarySearchTree {
constructor() {
this.root = null;
this.size = 0;
}
// 添加元素到二分搜索树中 +
add(element) {
if (element === null) throw new Error("element is null. can't store.");
if (this.root === null) {
this.root = new MyBinarySearchTreeNode(element);
this.size++;
} else this.root = this.recursiveAdd(this.root, element);
}
// 添加元素到二分搜索树中 递归算法 -
recursiveAdd(node, newElement) {
// 解决最基本的问题 也就是递归函数调用的终止条件
if (node === null) {
node = new MyBinarySearchTreeNode(newElement);
this.size++;
return node;
}
// 1. 当前节点的元素比新元素大
// 那么新元素就会被添加到当前节点的左子树去
// 2. 当前节点的元素比新元素小
// 那么新元素就会被添加到当前节点的右子树去
// 3. 当前节点的元素比新元素相等
// 什么都不做了，因为目前不添加重复的元素
if (this.compare(node.element, newElement) > 0)
node.left = this.recursiveAdd(node.left, newElement);
else if (this.compare(node.element, newElement) < 0)
node.right = this.recursiveAdd(node.right, newElement);
else {
}
// 将复杂问题分解成多个性质相同的小问题，
// 然后求出小问题的答案，
// 最终构建出原问题的答案
return node;
}
// 获取二分搜索树中节点个数 +
getSize() {
return this.size;
}
// 返回二分搜索树是否为空的bool值 +
isEmpty() {
return this.size === 0;
}
// 新增一个比较的方法，专门用来比较新增的元素大小 -
// 第一个元素比第二个元素大 就返回 1
// 第一个元素比第二个元素小 就返回 -1
// 第一个元素比第二个元素相等 就返回 0
compare(elementA, elementB) {
if (elementA === null || elementB === null)
throw new Error("element is null. can't compare.");
// 先直接写死
if (elementA > elementB) return 1;
else if (elementA < elementB) return -1;
else return 0;
}
}小结
对于二分搜索的插入操作，上面的代码是相对比较复杂的，可以进行改进一下，让代码整体简洁一些，因为递归算法是有很多不同的写法的，而且递归的终止条件也是有不同的考量。
深入理解递归终止条件
改进添加操作，递归算法有很多不同的写法，递归的终止条件也有不同的考量。
之前的算法，向以 node 为根的二分搜索树中插入元素 e，其实将新的元素插入至 node 的左孩子或者右孩子，如果 node 的左或右孩子为空，那可以进行相应的赋值操作，如果是 node 的左右孩子都不为空的话，那就只能递归的插入到相应 node 的左或右孩子中，因为这一层节点已经满了，只能考虑下一层了，下一层符合要求并且节点没有满，就可以进行相应的赋值操作了。
但是有对根节点做出了特殊的处理，要防止根节点为空的情况发生，如果根节点为空，那么就将第一个元素赋值为根节点，但是除了根节点以外，其它节点不需要做这种特殊处理，所以导致逻辑上并不统一，并且递归的终止条件非常的臃肿。
代码示例
class MyBinarySearchTreeNode {
constructor(element, left = null, right = null) {
// 实际存储的元素
this.element = element;
// 当前节点的左子树
this.left = left;
// 当前节点的右子树
this.right = right;
}
}
class MyBinarySearchTree {
constructor() {
this.root = null;
this.size = 0;
}
// 添加元素到二分搜索树中 +
add(element) {
if (element === null) throw new Error("element is null. can't store.");
this.root = this.recursiveAdd(this.root, element);
}
// 添加元素到二分搜索树中 递归算法 -
recursiveAdd(node, newElement) {
// 解决最基本的问题 也就是递归函数调用的终止条件
if (node === null) {
this.size++;
return new MyBinarySearchTreeNode(newElement);
}
// 1. 当前节点的元素比新元素大
// 那么新元素就会被添加到当前节点的左子树去
// 2. 当前节点的元素比新元素小
// 那么新元素就会被添加到当前节点的右子树去
// 3. 当前节点的元素比新元素相等
// 什么都不做了，因为目前不添加重复的元素
if (this.compare(node.element, newElement) > 0)
node.left = this.recursiveAdd(node.left, newElement);
else if (this.compare(node.element, newElement) < 0)
node.right = this.recursiveAdd(node.right, newElement);
else {
}
// 将复杂问题分解成多个性质相同的小问题，
// 然后求出小问题的答案，
// 最终构建出原问题的答案
return node;
}
// 获取二分搜索树中节点个数 +
getSize() {
return this.size;
}
// 返回二分搜索树是否为空的bool值 +
isEmpty() {
return this.size === 0;
}
// 新增一个比较的方法，专门用来比较新增的元素大小 -
// 第一个元素比第二个元素大 就返回 1
// 第一个元素比第二个元素小 就返回 -1
// 第一个元素比第二个元素相等 就返回 0
compare(elementA, elementB) {
if (elementA === null || elementB === null)
throw new Error("element is null. can't compare.");
// 先直接写死
if (elementA > elementB) return 1;
else if (elementA < elementB) return -1;
else return 0;
}
}小结
虽然代码量更少了，但是也更难理解的了一些。首先从宏观的语意的角度去理解定义这个函数的语意后整个递归函数处理的逻辑如何成立的，其次从微观的角度上可以写一些辅助代码来帮助你一点一点的查看，从一个空的二分搜索树开始，往里添加三五个元素，看看每个元素是如何逐步的添加进去。
可以尝试一些链表这个程序插入操作的递归算法，其实这二者之间是拥有非常高的相似度的，只不过在二分搜索树中需要判断一下是需要插入到左子树还是右子树而已，对于链表来说直接插入到 next 就好了，通过二者的比较就可以更加深入的理解这个程序。
二分搜索树的查询操作
查询操作非常的容易，只需要不停的看每一个 node 里面存的元素，不会牵扯到整个二分搜索树的添加操作。
和添加元素一样需要使用递归的进行实现，在递归的过程中就需要从二分搜索树的根开始，逐渐的转移在二分搜索树的子树中缩小问题的规模，缩小查询的树的规模，直到找到这个元素 e 或者发现找不到这个元素 e。
在数组和链表中有索引这个概念，但是在二分搜索树中没有索引这个概念。
代码示例
class MyBinarySearchTreeNode {
constructor(element, left = null, right = null) {
// 实际存储的元素
this.element = element;
// 当前节点的左子树
this.left = left;
// 当前节点的右子树
this.right = right;
}
}
class MyBinarySearchTree {
constructor() {
this.root = null;
this.size = 0;
}
// 添加元素到二分搜索树中 +
add(element) {
if (element === null) throw new Error("element is null. can't store.");
this.root = this.recursiveAdd(this.root, element);
}
// 添加元素到二分搜索树中 递归算法 -
recursiveAdd(node, newElement) {
// 解决最基本的问题 也就是递归函数调用的终止条件
if (node === null) {
this.size++;
return new MyBinarySearchTreeNode(newElement);
}
// 1. 当前节点的元素比新元素大
// 那么新元素就会被添加到当前节点的左子树去
// 2. 当前节点的元素比新元素小
// 那么新元素就会被添加到当前节点的右子树去
// 3. 当前节点的元素比新元素相等
// 什么都不做了，因为目前不添加重复的元素
if (this.compare(node.element, newElement) > 0)
node.left = this.recursiveAdd(node.left, newElement);
else if (this.compare(node.element, newElement) < 0)
node.right = this.recursiveAdd(node.right, newElement);
else {
}
// 将复杂问题分解成多个性质相同的小问题，
// 然后求出小问题的答案，
// 最终构建出原问题的答案
return node;
}
// 判断二分搜索树中是否包含某个元素 +
contains(element) {
if (this.root === null) throw new Error("root is null. can't query.");
return this.recursiveContains(this.root, element);
}
// 判断二分搜索树种是否包含某个元素 递归算法 -
recursiveContains(node, element) {
if (node === null) return false;
// 当前节点元素比 要搜索的元素 大
if (this.compare(node.element, element) > 0)
return this.recursiveContains(node.left, element);
else if (this.compare(node.element, element) < 0)
// 当前元素比 要搜索的元素 小
return this.recursiveContains(node.right, element);
// 两个元素相等
else return true;
}
// 获取二分搜索树中节点个数 +
getSize() {
return this.size;
}
// 返回二分搜索树是否为空的bool值 +
isEmpty() {
return this.size === 0;
}
// 新增一个比较的方法，专门用来比较新增的元素大小 -
// 第一个元素比第二个元素大 就返回 1
// 第一个元素比第二个元素小 就返回 -1
// 第一个元素比第二个元素相等 就返回 0
compare(elementA, elementB) {
if (elementA === null || elementB === null)
throw new Error("element is null. can't compare.");
// 先直接写死
if (elementA > elementB) return 1;
else if (elementA < elementB) return -1;
else return 0;
}
}二分搜索树的遍历-前序遍历
遍历操作就是把这个数据结构中所有的元素都访问一遍，在二分搜索树中就是把所有节点都访问一遍。
访问数据结构中存储的所有元素是因为与业务相关，例如 给所有的同学加两分，给所有的员工发补贴等等，由于你的数据结构是用来存储数据的，不仅可以查询某些特定的数据，还应该有相关的方式将所有的数据都进行访问。
在线性结构下，遍历是极其容易的，无论是数组还是链表只要使用一下循环就好了，但是这件事在树结构下没有那么简单，但是也没有那么难：）。
在树结构下遍历操作并没有那么难，如果你对树结构不熟悉，那么可能就有点难，但是如果你熟悉了树结构，那么并非是那么难的操作，尤其是你在掌握递归操作之后，遍历树就更加不难了。
对于遍历操作，两个子树都要顾及，即要访问左子树中所有的节点又要访问右子树中所有的节点。下面的代码中的遍历方式也称为二叉树的前序遍历，先访问这个节点，再访问左右子树，访问这个节点放在了访问左右子树的前面所以就叫前序遍历。
要从宏观与微观的角度去理解这个代码，从宏观的角度来看，定义好了遍历的这个语意后整个逻辑是怎么组建的，从微观的角度来看，真正的有一个棵二叉树的时候，这个代码是怎样怎样一行一行去执行的。
当你熟练的掌握递归的时候，有的时候你可以不用遵守 那种先写递归终止的条件，再写递归组成的的逻辑 这样的一个过程，如写法二，虽然什么都不干，但是也是 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
class MyBinarySearchTreeNode {
constructor(element, left = null, right = null) {
// 实际存储的元素
this.element = element;
// 当前节点的左子树
this.left = left;
// 当前节点的右子树
this.right = right;
}
}
class MyBinarySearchTree {
constructor() {
this.root = null;
this.size = 0;
}
// 添加元素到二分搜索树中 +
add(element) {
if (element === null) throw new Error("element is null. can't store.");
this.root = this.recursiveAdd(this.root, element);
}
// 添加元素到二分搜索树中 递归算法 -
recursiveAdd(node, newElement) {
// 解决最基本的问题 也就是递归函数调用的终止条件
if (node === null) {
this.size++;
return new MyBinarySearchTreeNode(newElement);
}
// 1. 当前节点的元素比新元素大
// 那么新元素就会被添加到当前节点的左子树去
// 2. 当前节点的元素比新元素小
// 那么新元素就会被添加到当前节点的右子树去
// 3. 当前节点的元素比新元素相等
// 什么都不做了，因为目前不添加重复的元素
if (this.compare(node.element, newElement) > 0)
node.left = this.recursiveAdd(node.left, newElement);
else if (this.compare(node.element, newElement) < 0)
node.right = this.recursiveAdd(node.right, newElement);
else {
}
// 将复杂问题分解成多个性质相同的小问题，
// 然后求出小问题的答案，
// 最终构建出原问题的答案
return node;
}
// 判断二分搜索树中是否包含某个元素 +
contains(element) {
if (this.root === null) throw new Error("root is null. can't query.");
return this.recursiveContains(this.root, element);
}
// 判断二分搜索树种是否包含某个元素 递归算法 -
recursiveContains(node, element) {
if (node === null) return false;
// 当前节点元素比 要搜索的元素 大
if (this.compare(node.element, element) > 0)
return this.recursiveContains(node.left, element);
else if (this.compare(node.element, element) < 0)
// 当前元素比 要搜索的元素 小
return this.recursiveContains(node.right, element);
// 两个元素相等
else return true;
}
// 前序遍历 +
preOrder(operator) {
this.recursivePreOrder(this.root, operator);
}
// 前序遍历 递归算法 -
recursivePreOrder(node, operator) {
if (node === null) return;
// 调用一下操作方法
operator(node.element);
console.log(node, node.element);
// 继续递归遍历左右子树
this.recursivePreOrder(node.left, operator);
this.recursivePreOrder(node.right, operator);
}
// 获取二分搜索树中节点个数 +
getSize() {
return this.size;
}
// 返回二分搜索树是否为空的bool值 +
isEmpty() {
return this.size === 0;
}
// 新增一个比较的方法，专门用来比较新增的元素大小 -
// 第一个元素比第二个元素大 就返回 1
// 第一个元素比第二个元素小 就返回 -1
// 第一个元素比第二个元素相等 就返回 0
compare(elementA, elementB) {
if (elementA === null || elementB === null)
throw new Error("element is null. can't compare.");
// 先直接写死
if (elementA > elementB) return 1;
else if (elementA < elementB) return -1;
else return 0;
}
}Main
class Main {
constructor() {
this.alterLine('MyBinarySearchTree Area');
let myBinarySearchTree = new MyBinarySearchTree();
let nums = [5, 3, 6, 8, 4, 2];
for (var i = 0; i < nums.length; i++) {
myBinarySearchTree.add(nums[i]);
}
/////////////////
// 5 //
// / \ //
// 3 6 //
// / \ \ //
// 2 4 8 //
/////////////////
myBinarySearchTree.preOrder(this.show);
this.show(myBinarySearchTree.contains(1));
console.log(myBinarySearchTree.contains(1));
}
// 将内容显示在页面上
show(content) {
document.body.innerHTML += `${content}<br /><br />`;
}
// 展示分割线
alterLine(title) {
let line = `--------------------${title}----------------------`;
console.log(line);
document.body.innerHTML += `${line}<br /><br />`;
}
}
window.onload = function() {
// 执行主函数
new Main();
};二分搜索树的遍历调试-前序遍历
遍历输出二分搜索树,可以写一个辅助函数自动遍历所有节点生成字符串，辅助函数叫做 getBinarySearchTreeString，这个函数的作用是，生成以 node 为根节点，深度为 depth 的描述二叉树的字符串，这样一来要新增一个辅助函数，这个函数的作用是，根据递归深度生成字符串，这个辅助函数叫做 getDepthString。
代码示例
(class: MyBinarySearchTree, class: Main)
MyBinarySearchTree
class MyBinarySearchTreeNode {
constructor(element, left = null, right = null) {
// 实际存储的元素
this.element = element;
// 当前节点的左子树
this.left = left;
// 当前节点的右子树
this.right = right;
}
}
class MyBinarySearchTree {
constructor() {
this.root = null;
this.size = 0;
}
// 添加元素到二分搜索树中 +
add(element) {
if (element === null) throw new Error("element is null. can't store.");
this.root = this.recursiveAdd(this.root, element);
}
// 添加元素到二分搜索树中 递归算法 -
recursiveAdd(node, newElement) {
// 解决最基本的问题 也就是递归函数调用的终止条件
if (node === null) {
this.size++;
return new MyBinarySearchTreeNode(newElement);
}
// 1. 当前节点的元素比新元素大
// 那么新元素就会被添加到当前节点的左子树去
// 2. 当前节点的元素比新元素小
// 那么新元素就会被添加到当前节点的右子树去
// 3. 当前节点的元素比新元素相等
// 什么都不做了，因为目前不添加重复的元素
if (this.compare(node.element, newElement) > 0)
node.left = this.recursiveAdd(node.left, newElement);
else if (this.compare(node.element, newElement) < 0)
node.right = this.recursiveAdd(node.right, newElement);
else {
}
// 将复杂问题分解成多个性质相同的小问题，
// 然后求出小问题的答案，
// 最终构建出原问题的答案
return node;
}
// 判断二分搜索树中是否包含某个元素 +
contains(element) {
if (this.root === null) throw new Error("root is null. can't query.");
return this.recursiveContains(this.root, element);
}
// 判断二分搜索树种是否包含某个元素 递归算法 -
recursiveContains(node, element) {
if (node === null) return false;
// 当前节点元素比 要搜索的元素 大
if (this.compare(node.element, element) > 0)
return this.recursiveContains(node.left, element);
else if (this.compare(node.element, element) < 0)
// 当前元素比 要搜索的元素 小
return this.recursiveContains(node.right, element);
// 两个元素相等
else return true;
}
// 前序遍历 +
preOrder(operator) {
this.recursivePreOrder(this.root, operator);
}
// 前序遍历 递归算法 -
recursivePreOrder(node, operator) {
if (node === null) return;
// 调用一下操作方法
operator(node.element);
console.log(node, node.element);
// 继续递归遍历左右子树
this.recursivePreOrder(node.left, operator);
this.recursivePreOrder(node.right, operator);
}
// 获取二分搜索树中节点个数 +
getSize() {
return this.size;
}
// 返回二分搜索树是否为空的bool值 +
isEmpty() {
return this.size === 0;
}
// 新增一个比较的方法，专门用来比较新增的元素大小 -
// 第一个元素比第二个元素大 就返回 1
// 第一个元素比第二个元素小 就返回 -1
// 第一个元素比第二个元素相等 就返回 0
compare(elementA, elementB) {
if (elementA === null || elementB === null)
throw new Error("element is null. can't compare.");
// 先直接写死
if (elementA > elementB) return 1;
else if (elementA < elementB) return -1;
else return 0;
}
// 输出二分搜索树中的信息
// @Override toString 2018-11-03-jwl
toString() {
let treeInfo = '';
treeInfo += this.getBinarySearchTreeString(this.root, 0, treeInfo);
return treeInfo;
}
// 写一个辅助函数，用来生成二分搜索树信息的字符串
getBinarySearchTreeString(node, depth, treeInfo, pageContent = '') {
//以前序遍历的方式
if (node === null) {
treeInfo += this.getDepthString(depth) + 'null \r\n';
pageContent = this.getDepthString(depth) + 'null<br /><br />';
document.body.innerHTML += `${pageContent}`;
return treeInfo;
}
treeInfo += this.getDepthString(depth) + node.element + '\r\n';
pageContent =
this.getDepthString(depth) + node.element + '<br /><br />';
document.body.innerHTML += `${pageContent}`;
treeInfo = this.getBinarySearchTreeString(
node.left,
depth + 1,
treeInfo
);
treeInfo = this.getBinarySearchTreeString(
node.right,
depth + 1,
treeInfo
);
return treeInfo;
}
// 写一个辅助函数，用来生成递归深度字符串
getDepthString(depth) {
let depthString = '';
for (var i = 0; i < depth; i++) {
depthString += '-- ';
}
return depthString;
}
}Main
class Main {
constructor() {
this.alterLine('MyBinarySearchTree Area');
let myBinarySearchTree = new MyBinarySearchTree();
let nums = [5, 3, 6, 8, 4, 2];
for (var i = 0; i < nums.length; i++) {
myBinarySearchTree.add(nums[i]);
}
/////////////////
// 5 //
// / \ //
// 3 6 //
// / \ \ //
// 2 4 8 //
/////////////////
console.log(myBinarySearchTree.toString());
}
// 将内容显示在页面上
show(content) {
document.body.innerHTML += `${content}<br /><br />`;
}
// 展示分割线
alterLine(title) {
let line = `--------------------${title}----------------------`;
console.log(line);
document.body.innerHTML += `${line}<br /><br />`;
}
}
window.onload = function() {
// 执行主函数
new Main();
};二分搜索树的遍历-中序、后序遍历
前序遍历
前序遍历是最自然的一种遍历方式，同时也是最常用的一种遍历方式，如果没有特殊情况的话，在大多数情况下都会使用前序遍历。先访问这个节点，然后访问这个节点的左子树，再访问这个节点的右子树，整个过程循环往复。前序遍历的前表示先访问的这个节点。
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#、JS这样的语言都有垃圾回收机制，所以不需要你对内存管理进行手动的控制，c++ 语言中需要手动的控制内存，那么在二分搜索树内存释放这方面就需要使用后序遍历。
对于一些树结构的问题，很多时候也是需要先针对一个节点的孩子节点求解出答案，最终再由这些答案组合成针对这个节点的答案，树形问题有分治算法、回溯算法、动态规划算法等等。
二分搜索树的前中后序遍历，主要从程序的角度进行分析，很多时候对一些问题的分析，如果直接给你一个树结构，然后你能够直接看出来对于这棵树来说它的前中后序遍历的结果是怎样的，那就可以大大加快解决问题的速度，同时这样的一个问题也是和计算机相关的考试的题目，对于这样的一个问题的更加深入的理解也可以帮助你理解二分搜索树这种数据结构。
代码示例
(class: MyBinarySearchTree, class: Main)
MyBinarySearchTree
class MyBinarySearchTreeNode {
constructor(element, left = null, right = null) {
// 实际存储的元素
this.element = element;
// 当前节点的左子树
this.left = left;
// 当前节点的右子树
this.right = right;
}
}
// 自定义二分搜索树
class MyBinarySearchTree {
constructor() {
this.root = null;
this.size = 0;
}
// 添加元素到二分搜索树中 +
add(element) {
if (element === null) throw new Error("element is null. can't store.");
this.root = this.recursiveAdd(this.root, element);
}
// 添加元素到二分搜索树中 递归算法 -
recursiveAdd(node, newElement) {
// 解决最基本的问题 也就是递归函数调用的终止条件
if (node === null) {
this.size++;
return new MyBinarySearchTreeNode(newElement);
}
// 1. 当前节点的元素比新元素大
// 那么新元素就会被添加到当前节点的左子树去
// 2. 当前节点的元素比新元素小
// 那么新元素就会被添加到当前节点的右子树去
// 3. 当前节点的元素比新元素相等
// 什么都不做了，因为目前不添加重复的元素
if (this.compare(node.element, newElement) > 0)
node.left = this.recursiveAdd(node.left, newElement);
else if (this.compare(node.element, newElement) < 0)
node.right = this.recursiveAdd(node.right, newElement);
else {
}
// 将复杂问题分解成多个性质相同的小问题，
// 然后求出小问题的答案，
// 最终构建出原问题的答案
return node;
}
// 判断二分搜索树中是否包含某个元素 +
contains(element) {
if (this.root === null) throw new Error("root is null. can't query.");
return this.recursiveContains(this.root, element);
}
// 判断二分搜索树种是否包含某个元素 递归算法 -
recursiveContains(node, element) {
if (node === null) return false;
// 当前节点元素比 要搜索的元素 大
if (this.compare(node.element, element) > 0)
return this.recursiveContains(node.left, element);
else if (this.compare(node.element, element) < 0)
// 当前元素比 要搜索的元素 小
return this.recursiveContains(node.right, element);
// 两个元素相等
else return true;
}
// 前序遍历 +
preOrder(operator) {
this.recursivePreOrder(this.root, operator);
}
// 前序遍历 递归算法 -
recursivePreOrder(node, operator) {
if (node === null) return;
// 调用一下操作方法
operator(node.element);
console.log(node, node.element);
// 继续递归遍历左右子树
this.recursivePreOrder(node.left, operator);
this.recursivePreOrder(node.right, operator);
}
// 中序遍历 +
inOrder(operator) {
this.recursiveInOrder(this.root, operator);
}
// 中序遍历 递归算法 -
recursiveInOrder(node, operator) {
if (node == null) return;
this.recursiveInOrder(node.left, operator);
operator(node.element);
console.log(node.element);
this.recursiveInOrder(node.right, operator);
}
// 后序遍历 +
postOrder(operator) {
this.recursivePostOrder(this.root, operator);
}
// 后序遍历 递归算法 -
recursivePostOrder(node, operator) {
if (node == null) return;
this.recursivePostOrder(node.left, operator);
this.recursivePostOrder(node.right, operator);
operator(node.element);
console.log(node.element);
}
// 获取二分搜索树中节点个数 +
getSize() {
return this.size;
}
// 返回二分搜索树是否为空的bool值 +
isEmpty() {
return this.size === 0;
}
// 新增一个比较的方法，专门用来比较新增的元素大小 -
// 第一个元素比第二个元素大 就返回 1
// 第一个元素比第二个元素小 就返回 -1
// 第一个元素比第二个元素相等 就返回 0
compare(elementA, elementB) {
if (elementA === null || elementB === null)
throw new Error("element is null. can't compare.");
// 先直接写死
if (elementA > elementB) return 1;
else if (elementA < elementB) return -1;
else return 0;
}
// 输出二分搜索树中的信息
// @Override toString 2018-11-03-jwl
toString() {
let treeInfo = '';
treeInfo += this.getBinarySearchTreeString(this.root, 0, treeInfo);
return treeInfo;
}
// 写一个辅助函数，用来生成二分搜索树信息的字符串
getBinarySearchTreeString(node, depth, treeInfo, pageContent = '') {
//以前序遍历的方式
if (node === null) {
treeInfo += this.getDepthString(depth) + 'null \r\n';
pageContent = this.getDepthString(depth) + 'null<br /><br />';
document.body.innerHTML += `${pageContent}`;
return treeInfo;
}
treeInfo += this.getDepthString(depth) + node.element + '\r\n';
pageContent =
this.getDepthString(depth) + node.element + '<br /><br />';
document.body.innerHTML += `${pageContent}`;
treeInfo = this.getBinarySearchTreeString(
node.left,
depth + 1,
treeInfo
);
treeInfo = this.getBinarySearchTreeString(
node.right,
depth + 1,
treeInfo
);
return treeInfo;
}
// 写一个辅助函数，用来生成递归深度字符串
getDepthString(depth) {
let depthString = '';
for (var i = 0; i < depth; i++) {
depthString += '-- ';
}
return depthString;
}
}Main
// main 函数
class Main {
constructor() {
this.alterLine('MyBinarySearchTree Area');
let myBinarySearchTree = new MyBinarySearchTree();
let nums = [5, 3, 6, 8, 4, 2];
for (var i = 0; i < nums.length; i++) {
myBinarySearchTree.add(nums[i]);
}
/////////////////
// 5 //
// / \ //
// 3 6 //
// / \ \ //
// 2 4 8 //
/////////////////
this.alterLine('MyBinarySearchTree PreOrder Area');
myBinarySearchTree.preOrder(this.show);
this.alterLine('MyBinarySearchTree InOrder Area');
myBinarySearchTree.inOrder(this.show);
this.alterLine('MyBinarySearchTree PostOrder Area');
myBinarySearchTree.postOrder(this.show);
}
// 将内容显示在页面上
show(content) {
document.body.innerHTML += `${content}<br /><br />`;
}
// 展示分割线
alterLine(title) {
let line = `--------------------${title}----------------------`;
console.log(line);
document.body.innerHTML += `${line}<br /><br />`;
}
}
// 页面加载完毕
window.onload = function() {
// 执行主函数
new Main();
};本篇总结
再看二分搜索树的遍历，对每一个节点都有三次的访问机会，在遍历左子树之前会去访问一下这个节点然后才能遍历它的左子树，在遍历完左子树之后才能够回到这个节点，之后才会去遍历它的右子树，在遍历右子树之后又回到了这个节点。
这就是每一个节点使用这种递归遍历的方式其实会访问它三次，对二分搜索树前中后这三种顺序的遍历，其实就对应于这三个访问机会是在哪里进行真正的那个访问操作，在哪里输出访问的这个节点的值，是先访问这个节点后再遍历它的左右子树，还是先遍历左子树然后访问这个节点最后遍历右子树，再或者是 先遍历左右子树再访问这个节点。
function traverse(node) {
if (node === null) return;
// 1. 第一个访问的机会 前
traverse(node.left);
// 2. 第二个访问的机会 中
traverse(node.right);
// 3. 第三个访问的机会 后
}二叉树前中后序遍历访问节点的不同
前序遍历访问节点都是在第一个访问机会的位置才去访问节点。
中序遍历访问节点都是在第二个访问机会的位置才去访问节点。
后序遍历访问节点都是在第三个访问机会的位置才去访问节点。
