注意：原教学视频：JavaScript(ES6)数据结构和算法 | JavaScript数据结构与算法 (都是CoderWhy老师的教学)
原作者（笔记）链接：JavaScript 数据结构与算法 | JavaScript数据结构与算法博客目录
PS：本文仅在学习过程中，对两篇笔记进行整合及总结（包含少量补充），以作学习之用。
Part2: 集合、字典、哈希表、树、二叉树、二叉搜索树（红黑树这里不作整合，因为我也还没看懂）、图。
集合
几乎每种编程语言中，都有集合结构。集合比较常见的实现方式是哈希表，这里使用 JavaScript 的 Object 进行封装。
集合特点
集合通常是由一组无序的、不能重复的元素构成。 数学中常指的集合中的元素是可以重复的，但是计算机中集合的元素不能重复。 集合是特殊的数组： 特殊之处在于里面的元素没有顺序，也不能重复。没有顺序意味着不能通过下标值进行访问，不能重复意味着相同的对象在集合中只会存在一份。集合常见的操作
add(value)：向集合添加一个新的项；remove(value)：从集合中移除一个值；has(value)：如果值在集合中，返回true，否则返回false；clear()：移除集合中的所有项；size()：返回集合所包含元素的数量，与数组的length属性相似；values()：返回一个包含集合中所有值的数组； 还有其他的方法，用的不多这里不做封装。代码实现
实现集合类
在ES6中的Set类就是一个集合类，这里我们重新封装一个Set类，了解集合的底层实现。JavaScript中的Object类中的key就是一个集合，可以使用它来封装集合类Set。
//封装集合类function Set() {//属性this.items = {};//方法//一.has方法Set.prototype.has = (value) => {return this.items.hasOwnProperty(value);}//二.add方法Set.prototype.add = (value) => {//判断集合中是否已经包含该元素if (this.has(value)) {return false;}//将元素添加到集合中this.items[value] = value;//表示该属性键和值都为valuereturn true;//表示添加成功}//三.remove方法Set.prototype.remove = (value) => {//1.判断集合中是否包含该元素if (!this.has(value)) {return false;}//2.将元素从属性中删除delete this.items[value];return true;}//四.clear方法Set.prototype.clear = () => {//原来的对象没有引用指向，会被自动回收this.items = {};}//五.size方法Set.prototype.size = () => {return Object.keys(this.items).length;}//获取集合中所有的值//六.values方法Set.prototype.values = () => {return Object.keys(this.items);}}
代码测试
//测试集合类//1.创建Set类对象let set = new Set();//添加元素//2.测试add方法console.log(set.add('a'));//67console.log(set.add('a'));//68console.log(set.add('b'));//69console.log(set.add('c'));//70console.log(set.add('d'));//71//3.测试values方法console.log(set.values());//74//删除元素//4.测试remove方法console.log(set.remove('a'));//78console.log(set.remove('a'));//79console.log(set.values());//80//5.测试has方法console.log(set.has('b'));//83//6.测试size方法和clear方法console.log(set.size());//86set.clear();// 由于clear方法的实现原理为指向另外一个空对象，所以不影响原来的对象console.log(set.size());//89console.log(set.values());//90
测试结果
集合间的操作
集合间操作：
并集：对于给定的两个集合，返回一个包含两个集合中所有元素的新集合；交集：对于给定的两个集合，返回一个包含两个集合中共有元素的新集合；差集：对于给定的两个集合，返回一个包含所有存在于第一个集合且不存在于第二个集合的元素的新集合；子集：验证一个给定集合是否是另一个集合的子集；
并集的实现：
实现思路：创建集合C代表集合A和集合B的并集，先将集合A中的所有元素添加到集合C中，再遍历集合B，如果是集合C所没有的元素就把它添加到集合C中。
Set.prototype.union = (otherSet) => {// this:集合对象A// otherSet:集合对象B//1.创建一个新的集合let unionSet = new Set();//2.将A集合中的所有元素添加到新集合中let values = this.values();// for(let i of values){// unionSet.add(i)// }for(let i = 0;i < values.length;i++){unionSet.add(values[i]);}//3.取出B集合中的元素,判断是否需要加到新集合中values = otherSet.values();// for(let i of values){// //由于集合的add方法已经对重复的元素进行了判断,所以这里可以直接添加// unionSet.add(i)// }for(let i = 0;i < values.length;i++){unionSet.add(values[i]);}return unionSet;}
交集的实现：
实现思路：遍历集合A，当取得的元素也存在于集合B时，就把该元素添加到另一个集合C中。
Set.prototype.intersection = (otherSet) => {// this:集合A// otherSet:集合B//1.创建新的集合let intersectionSet = new Set();//2.从A中取出一个元素，判断是否同时存在于集合B中，是则放入新集合中let values = this.values();for(let i =0 ; i < values.length; i++){let item = values[i];if (otherSet.has(item)) {intersectionSet.add(item);}}return intersectionSet;}
差集的实现：
实现思路：遍历集合A，当取得的元素不存在于集合B时，就把该元素添加到另一个集合C中。
Set.prototype.diffrence = (otherSet) => {//this:集合A//otherSet:集合B//1.创建新的集合var diffrenceSet = new Set();//2.取出A集合中的每一个元素，判断是否同时存在于B中，不存在则添加到新集合中var values = this.values();for(var i = 0;i < values.length; i++){var item = values[i];if (!otherSet.has(item)) {diffrenceSet.add(item);}}return diffrenceSet;}
子集的实现：
实现思路：遍历集合A，当取得的元素中有一个不存在于集合B时，就说明集合A不是集合B的子集，返回false。
Set.prototype.subset = (otherSet) => {//this:集合A//otherSet：集合B//遍历集合A中的所有元素，如果发现，集合A中的元素，在集合B中不存在，那么放回false，如果遍历完整个集合A没有返回false，就返回truelet values = this.values();for(let i = 0; i < values.length; i++){let item = values[i];if(!otherSet.has(item)){return false;}}return true;}
使用Class的完整实现
// 集合结构的封装export default class Set {constructor() {this.items = {};}// has(value) 判断集合中是否存在 value 值，存在返回 true，否则返回 falsehas(value) {return this.items.hasOwnProperty(value);}// add(value) 往集合中添加 valueadd(value) {if (this.has(value)) return false;this.items[value] = value;return true;}// remove(value) 删除集合中指定的 valueremove(value) {// 如果集合不存在该 value，返回 falseif (!this.has(value)) return false;delete this.items[value];}// clear() 清空集合中所有 valueclear() {this.items = {};}// size() 获取集合中的 value 个数size() {return Object.keys(this.items).length;}// values() 获取集合中所有的 valuevalues() {return Object.keys(this.items);}// ------- 集合间的操作 ------- //// union() 求两个集合的并集union(otherSet) {// 1、创建一个新集合let unionSet = new Set();// 2、将当前集合（this）的所有 value，添加到新集合（unionSet）中for (let value of this.values()) {unionSet.add(value);}// 3、将 otherSet 集合的所有 value，添加到新集合（unionSet）中for (let value of otherSet.values()) {unionSet.add(value); // add() 已经有重复判断}return unionSet;}// intersection() 求两个集合的交集intersection(otherSet) {// 1、创建一个新集合let intersectionSet = new Set();// 2、从当前集合中取出每一个 value，判断是否在 otherSet 集合中存在for (let value of this.values()) {if (otherSet.has(value)) {intersectionSet.add(value);}}return intersectionSet;}// difference() 差集difference(otherSet) {// 1、创建一个新集合let differenceSet = new Set();// 2、从当前集合中取出每一个 value，判断是否在 otherSet 集合中存在，不存在的即为差集for (let value of this.values()) {if (!otherSet.has(value)) {differenceSet.add(value);}}return differenceSet;}// subset() 子集subset(otherSet) {// 从当前集合中取出每一个 value，判断是否在 otherSet 集合中存在，有不存在的返回 false// 遍历完所有的，返回 truefor (let value of this.values()) {if (!otherSet.has(value)) {return false;}}return true;}}
字典
一般会用哈希表实现，这里只作简单讲解。
字典特点
字典存储的是键值对，主要特点是一一对应。比如保存一个人的信息 数组形式：[19，‘Tom’，1.65]，可通过下标值取出信息。字典形式：{"age"：19，"name"："Tom"，"height"：165}，可以通过key取出value。 此外，在字典中 key 是不能重复且无序的，而 Value 可以重复。字典和映射的关系
有些编程语言中称这种映射关系为字典，如 Swift 中的 Dictonary，Python 中的 dict。有些编程语言中称这种映射关系为Map，比如 Java 中的 HashMap 和 TreeMap 等。字典和对象
很多编程语言（如Java）中对字典和对象区分比较明显，对象通常是一种在编译期就确定下来的结构，不可以动态的添加或者删除属性。而字典通常会使用类似于哈希表和数据结构去实现一种可以动态的添加数据的结构。但是在JavaScript中，似乎对象本身就是一种字典。所以在早期的Javascript中，没有字典这种数据类型，因为你完全可以使用对象去代替。字典常见的操作
set(key,value)向字典中添加新元素。remove(key)通过使用键值来从字典中移除键值对应的数据值。has(key)如果某个键值存在于这个字典中，则返回true，反之则返回false。get(key)通过键值查找特定的数值并返回。clear()将这个字典中的所有元素全部删除。size()返回字典所包含元素的数量。与数组的length属性类似。keys()将字典所包含的所有键名以数组形式返回。values()将字典所包含的所有数值以数组形式返回。字典封装
代码实现
//封装字典类function Dictionary(){//字典属性this.items = {}//字典操作方法//一.在字典中添加键值对Dictionary.prototype.set = function(key, value){this.items[key] = value}//二.判断字典中是否有某个keyDictionary.prototype.has = function(key){return this.items.hasOwnProperty(key)}//三.从字典中移除元素Dictionary.prototype.remove = function(key){//1.判断字典中是否有这个keyif(!this.has(key)) return false//2.从字典中删除keydelete this.items[key]return true}//四.根据key获取valueDictionary.prototype.get = function(key){return this.has(key) ? this.items[key] : undefined}//五.获取所有keysDictionary.prototype.keys = function(){return Object.keys(this.items)}//六.size方法Dictionary.prototype.keys = function(){return this.keys().length}//七.clear方法Dictionary.prototype.clear = function(){this.items = {}}}
/*使用class实现*/// 字典结构的封装export default class Map {constructor() {this.items = {};}// has(key) 判断字典中是否存在某个 keyhas(key) {return this.items.hasOwnProperty(key);}// set(key, value) 在字典中添加键值对set(key, value) {this.items[key] = value;}// remove(key) 在字典中删除指定的 keyremove(key) {// 如果集合不存在该 key，返回 falseif (!this.has(key)) return false;delete this.items[key];}// get(key) 获取指定 key 的 value，如果没有，返回 undefinedget(key) {return this.has(key) ? this.items[key] : undefined;}// 获取所有的 keykeys() {return Object.keys(this.items);}// 获取所有的 valuevalues() {return Object.values(this.items);}// size() 获取字典中的键值对个数size() {return this.keys().length;}// clear() 清空字典中所有的键值对clear() {this.items = {};}}
代码测试
const map = new Map();// set() 测试map.set("name", "XPoet");map.set("age", 18);map.set("email", "i@");console.log(map); // {items: {name: "XPoet", age: 18, email: "i@"}}// has() 测试console.log(map.has("name")); //--> trueconsole.log(map.has("address")); //--> false// remove() 测试map.remove("name");console.log(map); // {age: 18, email: "i@"}// get() 测试console.log(map.get("age")); //--> 18// keys() 测试console.log(map.keys()); //--> ["age", "email"]// values() 测试console.log(map.values()); //--> [18, "i@"]// size() 测试console.log(map.size()); //--> 2
哈希表
认识哈希表
哈希表是一种非常重要的数据结构，几乎所有的编程语言都直接或者间接应用这种数据结构。
哈希表通常是基于数组实现的，但是相对于数组，它存在更多优势：
哈希表可以提供非常快速的插入-删除-查找操作。无论多少数据，插入和删除值都只需接近常量的时间，即O(1)的时间复杂度。实际上，只需要几个机器指令即可完成。哈希表的速度比树还要快，基本可以瞬间查找到想要的元素。哈希表相对于树来说编码要简单得多。
哈希表同样存在不足之处：
哈希表中的数据是没有顺序的，所以不能以一种固定的方式（比如从小到大 ）来遍历其中的元素。通常情况下，哈希表中的 key 是不允许重复的，不能放置相同的 key，用于保存不同的元素。
哈希表是什么？
哈希表并不好理解，不像数组、链表和树等可通过图形的形式表示其结构和原理。哈希表的结构就是数组，但它神奇之处在于对下标值的一种变换，这种变换我们可以称之为哈希函数，通过哈希函数可以获取HashCode。
通过以下案例了解哈希表：
案例一：公司想要存储 1000 个人的信息，每一个工号对应一个员工的信息。若使用数组，增删数据时比较麻烦；使用链表，获取数据时比较麻烦。有没有一种数据结构，能把某一员工的姓名转换为它对应的工号，再根据工号查找该员工的完整信息呢？没错此时就可以使用哈希表的哈希函数来实现。案例二：存储联系人和对应的电话号码：当要查找张三（比如）的号码时，若使用数组：由于不知道存储张三数据对象的下标值，所以查找起来十分麻烦，使用链表时也同样麻烦。而使用哈希表就能通过哈希函数把张三这个名称转换为它对应的下标值，再通过下标值查找效率就非常高了。
也就是说：哈希表最后还是基于数据来实现的，只不过哈希表能够通过哈希函数把字符串转化为对应的下标值，建立字符串和下标值的映射关系。
认识哈希化
为了把字符串转化为对应的下标值，需要有一套编码系统，为了方便理解我们创建这样一套编码系统：比如 a 为 1，b 为 2，c 为 3，以此类推 z 为 26，空格为 27（不考虑大写情况）。
有了编码系统后，将字母转化为数字也有很多种方案：
方案一：数字相加。
例如 cats 转化为数字：3 + 1 + 20 + 19 = 43，那么就把 43 作为 cats 单词的下标值储存在数组中；
但是这种方式会存在这样的问题：很多的单词按照该方式转化为数字后都是 43，比如 was。而在数组中一个下标值只能储存一个数据，所以该方式不合理。
方案二：幂的连乘。
我们平时使用的大于 10 的数字，就是用幂的连乘来表示它的唯一性的。 比如：6543 = 6 * 10^3 + 5 * 10^2 + 4 * 10 + 3；这样单词也可以用该种方式来表示：cats = 3 * 27^3 + 1 * 27^2 + 20 * 27 + 17 = 60337。
虽然该方式可以保证字符的唯一性，但是如果是较长的字符（如 aaaaaaaaaa）所表示的数字就非常大，此时要求很大容量的数组，然而其中却有许多下标值指向的是无效的数据（比如不存在 zxcvvv 这样的单词），造成了数组空间的浪费。
两种方案总结：
第一种方案（让数字相加求和）产生的数组下标太少。第二种方案（与 27 的幂相乘求和）产生的数组下标又太多。
现在需要一种压缩方法，把幂的连乘方案系统中得到的巨大整数范围压缩到可接受的数组范围中。可以通过取余操作来实现。虽然取余操作得到的结构也有可能重复，但是可以通过其他方式解决。
现在需要一种压缩方法，把幂的连乘方案系统中得到的巨大整数范围压缩到可接受的数组范围中。可以通过取余操作来实现。虽然取余操作得到的结构也有可能重复，但是可以通过其他方式解决。
哈希表的一些概念
哈希化：将大数字转化成数组范围内下标的过程，称之为哈希化；哈希函数：我们通常会将单词转化成大数字，把大数字进行哈希化的代码实现放在一个函数中，该函数就称为哈希函数；哈希表：对最终将数据插入的数组进行整个结构的封装，得到的就是哈希表。地址的冲突
在实际中，经过哈希函数哈希化过后得到的下标值可能有重复，这种情况称为冲突，冲突是不可避免的，我们只能解决冲突。
解决冲突常见的两种方案：链地址法（拉链法）和开放地址法。
链地址法
如下图所示，我们将每一个数字都对10进行取余操作，则余数的范围0~9作为数组的下标值。并且，数组每一个下标值对应的位置存储的不再是一个数字了，而是存储由经过取余操作后得到相同余数的数字组成的数组或链表。
这样可以根据下标值获取到整个数组或链表，之后继续在数组或链表中查找就可以了。而且，产生冲突的元素一般不会太多。
总结：链地址法解决冲突的办法是每个数组单元中存储的不再是单个数据，而是一条链条，这条链条常使用的数据结构为数组或链表，两种数据结构查找的效率相当（因为链条的元素一般不会太多）。
开放地址法
开放地址法的主要工作方式是寻找空白的单元格来放置冲突的数据项。
根据探测空白单元格位置方式的不同，可分为三种方法：
线性探测二次探测再哈希法
寻找空白单元格的方式
线性探测
线性探测很好理解：线性地查找空白的单元。
当插入13时：
经过哈希化（对10取余）之后得到的下标值index=3，但是该位置已经放置了数据33。而线性探测就是从index位置+1开始向后一个一个来查找合适的位置来放置13，所谓合适的位置指的是空的位置，如上图中index=4的位置就是合适的位置。
当查询13时：
首先13经过哈希化得到index=3，如果index=3的位置存放的数据与需要查询的数据13相同，就直接返回；不相同时，则线性查找，从index+1位置开始一个一个位置地查找数据13；查询过程中不会遍历整个哈希表，只要查询到空位置，就停止，因为插入13时不会跳过空位置去插入其他位置。
当删除13时：
删除操作和上述两种情况类似，但需要注意的是，删除一个数据项时，不能将该位置下标的内容设置为null，否则会影响到之后其他的查询操作，因为一遇到为null的位置就会停止查找。通常删除一个位置的数据项时，我们可以将它进行特殊处理（比如设置为-1），这样在查找时遇到-1就知道要继续查找。
线性探测存在的问题：
线性探测存在一个比较严重的问题，就是聚集；如哈希表中还没插入任何元素时，插入23、24、25、26、27，这就意味着下标值为3、4、5、6、7的位置都放置了数据，这种一连串填充单元就称为聚集；聚集会影响哈希表的性能，无论是插入/查询/删除都会影响；比如插入13时就会发现，连续的单元3~7都不允许插入数据，并且在插入的过程中需要经历多次这种情况。二次探测法可以解决该问题。
二次探测
上文所说的线性探测存在的问题：
如果之前的数据是连续插入的，那么新插入的一个数据可能需要探测很长的距离；
二次探测是在线性探测的基础上进行了优化：
线性探测：我们可以看成是步长为1的探测，比如从下表值x开始，那么线性探测就是按照下标值：x+1、x+2、x+3等依次探测；
二次探测：对步长进行了优化，比如从下标值x开始探测：x+12、x+22、x+32。这样一次性探测比较长的距离，避免了数据聚集带来的影响。
二次探测存在的问题：
当插入数据分布性较大的一组数据时，比如：13-163-63-3-213，这种情况会造成步长不一的一种聚集（虽然这种情况出现的概率较线性探测的聚集要小），同样会影响性能。
再哈希法
在开放地址法中寻找空白单元格的最好的解决方式为再哈希化：
二次探测的步长是固定的：1，4，9，16依次类推；现在需要一种方法：产生一种依赖关键字(数据)的探测序列，而不是每个关键字探测步长都一样；这样，不同的关键字即使映射到相同的数组下标，也可以使用不同的探测序列；再哈希法的做法为：把关键字用另一个哈希函数，再做一次哈希化，用这次哈希化的结果作为该关键字的步长；
第二次哈希化需要满足以下两点：
和第一个哈希函数不同，不然哈希化后的结果仍是原来位置；不能输出为0，否则每次探测都是原地踏步的死循环；
优秀的哈希函数：
stepSize = constant - （key % constant）；其中constant是质数，且小于数组的容量；例如：stepSize = 5 - （key % 5），满足需求，并且结果不可能为0；
哈希化的效率
哈希表中执行插入和搜索操作效率是非常高的。
如果没有发生冲突，那么效率就会更高；如果发生冲突，存取时间就依赖后来的探测长度；平均探测长度以及平均存取时间，取决于填装因子，随着填装因子变大，探测长度会越来越长。
理解概念装填因子：
装填因子表示当前哈希表中已经包含的数据项和整个哈希表长度的比值；装填因子 = 总数据项 / 哈希表长度；开放地址法的装填因子最大为1，因为只有空白的单元才能放入元素；链地址法的装填因子可以大于1，因为只要愿意，拉链法可以无限延伸下去；
不同探测方式性能的比较
线性探测：推算来自于Knuth（算法分析领域的专家，现代计算机的先驱人物）。这里不再给出推导过程和公式，仅根据公式模型说明它的效率。
可以看到，随着装填因子的增大，平均探测长度呈指数形式增长，性能较差。实际情况中，最好的装填因子取决于存储效率和速度之间的平衡，随着装填因子变小，存储效率下降，而速度上升。
二次探测和再哈希化的性能：
二次探测和再哈希法性能相当，它们的性能比线性探测略好。由下图可知，随着装填因子的变大，平均探测长度呈指数形式增长，需要探测的次数也呈指数形式增长，性能不高。
链地址法的性能：
可以看到随着装填因子的增加，平均探测长度呈线性增长，较为平缓。在开发中使用链地址法较多，比如Java中的HashMap中使用的就是链地址法。
哈希函数
哈希表的优势在于它的速度，所以哈希函数不能采用消耗性能较高的复杂算法。提高速度的一个方法是在哈希函数中尽量减少乘法和除法。
性能高的哈希函数应具备以下两个优点：
快速的计算；均匀的分布。
快速计算
霍纳法则：在中国霍纳法则也叫做秦九韶算法，具体算法为：
求多项式的值时，首先计算最内层括号内一次多项式的值，然后由内向外逐层计算一次多项式的值。这种算法把求 n 次多项式 f(x)的值就转化为求 n 个一次多项式的值。
例如我们在前面计算哈希值时候使用的方式：
cats = 3 * 27^3 + 1 * 27^2 + 20 * 27 + 17 = 60037
将这个表达式抽象成一个多项式，则此时问题就变成了该多项式的乘法和加法的次数：
变换之前： 乘法次数：n(n+1)/2 次；加法次数：n 次； 变换之后： 乘法次数：n 次；加法次数：n 次；
如果使用大 O 表示时间复杂度的话，直接从变换前的 O(N^2)降到了 O(N)。
均匀分布
在设计哈希表时，我们已经有办法处理映射到相同下标值的情况：链地址法或者开放地址法。
但是，为了提供效率，最好的情况还是让数据在哈希表中均匀分布。因此，我们需要在使用常量的地方，尽量使用质数。比如：哈希表的长度、N 次幂的底数等。（至于为什么最好取质数，数学问题这里不作原因讲解，可以自行了解）
Java 中的 HashMap 采用的是链地址法，哈希化采用的是公式为：index = HashCode(key) & (Length-1)
即将数据化为二进制进行与运算，而不是取余运算。这样计算机直接运算二进制数据，效率更高。但是 JavaScript 在进行较大数据的与运算时会出现问题，所以我们使用 JavaScript 实现哈希化时采用取余运算。
封装哈希表
哈希表常见操作
put(key, value)插入或修改操作。get(key)获取哈希表中特定位置的元素。remove(key)删除哈希表中特定位置的元素。isEmpty()如果哈希表中不包含任何元素，返回 trun，如果哈希表长度大于 0 则返回 false。size()返回哈希表包含的元素个数。resize(value)对哈希表进行扩容操作。哈希函数的简单实现
首先使用霍纳法则计算 hashCode 的值，通过取余操作实现哈希化，此处先简单地指定数组的大小。
function hashFunc(string, size = 7) {//参数二为长度，默认为7// 自己采用的一个质数（无强制要求，质数即可），这里采用常用的37const PRIME = 37;// 1、定义存储 hashCode 的变量let hashCode = 0;// 2、使用霍纳法则（秦九韶算法），计算 hashCode 的值for (let i = 0; i < string.length; i++) {hashCode = PRIME * hashCode + String.charCodeAt(i);//charCodeAt():返回字符串指定位置字符的Unicode编码}// 3、对 hashCode 取余，并返回return hashCode % size;}
哈希函数测试
console.log(hashFunc("123")); //--> 4console.log(hashFunc("nba")); //--> 5console.log(hashFunc("abcd")); //--> 3
哈希表的实现
这里只放出使用function实现的代码，使用class实现见后面完整代码。
0. 创建哈希表类
这里使用链地址法实现哈希表。
封装哈希表的数组结构模型:
首先创建哈希表类HashTable，并添加必要的属性和上面实现的哈希函数：
//封装哈希表类function HashTable() {//属性this.storage = [];this.count = 0;//计算已经存储的元素个数//装填因子：loadFactor > 0.75时需要扩容；loadFactor < 0.25时需要减少容量this.limit = 7;//初始长度//方法//哈希函数HashTable.prototype.hashFunc = function(str, size=7){// 自己采用的一个质数（无强制要求，质数即可），这里采用常用的37const PRIME = 37;// 1、定义存储 hashCode 的变量let hashCode = 0;// 2、使用霍纳法则（秦九韶算法），计算 hashCode 的值for (let i = 0; i < string.length; i++) {hashCode = PRIME * hashCode + String.charCodeAt(i);//charCodeAt():返回字符串指定位置字符的Unicode编码}// 3、对 hashCode 取余，并返回return hashCode % size;}
1. put(key,value)
哈希表的插入和修改操作是同一个函数：因为，当使用者传入一个<key，value>时，如果原来不存在该key，那么就是插入操作，如果原来已经存在该key，那么就是修改操作。
实现思路：
首先，根据key获取索引值index，目的为将数据插入到storage的对应位置；然后，根据索引值取出bucket，如果bucket不存在，先创建bucket，随后放置在该索引值的位置；接着，判断新增还是修改原来的值。如果已经有值了，就修改该值；如果没有，就执行后续操作。最后，进行新增数据操作。
代码实现：
//插入&修改操作HashTable.prototype.put = function (key, value){//1.根据key获取对应的indexlet index = this.hashFunc(key, this.limit);//2.根据index取出对应的bucketlet bucket = this.storage[index];//3.判断该bucket是否为nullif (bucket == null) {bucket = [];this.storage[index] = bucket;}//4.判断是否是修改数据for (let i = 0; i < bucket.length; i++) {let tuple = bucket[i]; //此时tuple为[key,value]的数组if (tuple[0] == key) {tuple[1] = value;return//不用返回值}}//5.进行添加操作bucket.push([key, value]);this.count += 1;}
测试代码：
//测试哈希表//1.创建哈希表let ht = new HashTable();//2.插入数据ht.put('class1','Tom');ht.put('class2','Mary');ht.put('class3','Gogo');ht.put('class4','Tony');ht.put('class4', 'Vibi');console.log(ht);
测试结果：
2. get(key)
实现思路：
首先，根据key通过哈希函数获取它在storage中对应的索引值index；然后，根据索引值获取对应的bucket；接着，判断获取到的bucket是否为null，如果为null，直接返回null；随后，线性遍历bucket中每一个key是否等于传入的key。如果等于，直接返回对应的value；最后，遍历完bucket后，仍然没有找到对应的key，直接return null即可。
//获取操作HashTable.prototype.get = function(key){//1.根据key获取对应的indexlet index = this.hashFunc(key, this.limit);//2.根据index获取对应的bucketlet bucket = this.storage[index];//3.判断bucket是否等于nullif (bucket == null) {return null;}//4.有bucket，那么就进行线性查找for (let i = 0; i < bucket.length; i++) {let tuple = bucket[i];if (tuple[0] == key) {//tuple[0]存储key，tuple[1]存储valuereturn tuple[1];}}//5.依然没有找到，那么返回nullreturn null;}
测试代码：
//测试哈希表//1.创建哈希表let ht = new HashTable();//2.插入数据ht.put('class1','Tom')ht.put('class2','Mary')ht.put('class3','Gogo')ht.put('class4','Tony')//3.获取数据console.log(ht.get('class3'));console.log(ht.get('class2'));console.log(ht.get('class1'));
测试结果：
3. remove(key)
实现思路：
首先，根据key通过哈希函数获取它在storage中对应的索引值index；然后，根据索引值获取对应的bucket；接着，判断获取到的bucket是否为null，如果为null，直接返回null；随后，线性查找bucket，寻找对应的数据，并且删除；最后，依然没有找到，返回null；
代码实现：
//删除操作HashTable.prototype.remove = function(key){//1.根据key获取对应的indexlet index = this.hashFunc(key, this.limit);//2.根据index获取对应的bucketlet bucket = this.storage[index];//3.判断bucket是否为nullif (bucket == null) {return null;}//4.有bucket,那么就进行线性查找并删除for (let i = 0; i < bucket.length; i++) {let tuple = bucket[i];if (tuple[0] == key) {bucket.splice(i,1); //splice()会改变原数组this.count -= 1;return tuple[1];}}//5.依然没有找到，返回nullreturn null;}
测试代码：
//测试哈希表//1.创建哈希表let ht = new HashTable();//2.插入数据ht.put('class1','Tom');ht.put('class2','Mary');ht.put('class3','Gogo');ht.put('class4','Tony');//3.删除数据console.log( ht.remove('class2'));console.log(ht.get('class2'));
测试结果：
4. 其他方法
其他方法包括：isEmpty()、size()：
代码实现：
//判断哈希表是否为nullHashTable.prototype.isEmpty = function(){return this.count == 0;}//获取哈希表中元素的个数HashTable.prototype.size = function(){return this.count;}
哈希表的扩容与压缩
为什么需要扩容？
前面我们在哈希表中使用的是长度为7的数组，由于使用的是**链地址法，装填因子(loadFactor)**可以大于1，所以这个哈希表可以无限制地插入新数据。但是，随着数据量的增多，storage中每一个index对应的bucket数组（链表）就会越来越长，这就会造成哈希表效率的降低
装填因子= 哈希表中数据 / 哈希表长度，即 loadFactor = count / HashTable.length。
什么情况下需要扩容？
常见的情况是loadFactor > 0.75的时候进行扩容；
如何进行扩容？
简单的扩容可以直接扩大两倍（关于质数，之后讨论）；扩容之后所有的数据项都要进行同步修改；
实现思路:
首先，定义一个变量，比如oldStorage指向原来的storage；然后，创建一个新的容量更大的数组，让this.storage指向它；最后，将oldStorage中的每一个bucket中的每一个数据取出来依次添加到this.storage指向的新数组中；
代码实现：
//哈希表扩容HashTable.prototype.resize = function(newLimit){//1.保存旧的storage数组内容let oldStorage = this.storage;//2.重置所有的属性this.storage = [];this.count = 0;this.limit = newLimit;//3.遍历oldStorage中所有的bucketfor (let i = 0; i < oldStorage.length; i++) {//3.1.取出对应的bucketconst bucket = oldStorage[i];//3.2.判断bucket是否为nullif (bucket == null) {continue}//3.3.bucket中有数据，就取出数据重新插入for (let j = 0; j < bucket.length; j++) {const tuple = bucket[j];this.put(tuple[0], tuple[1]);//插入数据的key和value}}}
上述定义的哈希表的resize方法，既可以实现哈希表的扩容，也可以实现哈希表容量的压缩。
通常情况下当装填因子laodFactor > 0.75时，对哈希表进行扩容。在哈希表中的添加方法（push方法）中添加如下代码，判断是否需要调用扩容函数进行扩容：
//判断是否需要扩容操作if(this.count > this.limit * 0.75){this.resize(this.limit * 2);}
当装填因子laodFactor < 0.25时，对哈希表容量进行压缩。在哈希表中的删除方法（remove方法）中添加如下代码，判断是否需要调用扩容函数进行压缩：
//缩小容量if (this.limit > 7 && this.count < this.limit * 0.25) {this.resize(Math.floor(this.limit / 2));}
选择质数作为哈希表容量
判断质数的方法：
方法一：针对质数的特点：只能被1和num整除，不能被2 ~ (num-1)整除。遍历2 ~ (num-1) 。注意1不是质数
function isPrime(num){if(num <= 1 ){return false;} for(let i = 2; i <= num - 1; i++){if(num % i ==0){return false;}}return true;}
这种方法虽然能实现质数的判断，但是效率不高。
方法二：只需要遍历2 ~ num的平方根即可。(原因这里不作讲解，可以参考视频)
function isPrime(num){if (num <= 1) {return false}//1.获取num的平方根:Math.sqrt(num)//2.循环判断for(let i = 2; i<= Math.sqrt(num); i++ ){if(num % i == 0){return false;}}return true;}
实现扩容后的哈希表容量为质数
实现思路：
2倍扩容之后，通过循环调用isPrime判断得到的容量是否为质数，不是则+1，直到是为止。比如原长度：7，2倍扩容后长度为14，14不是质数，14 + 1 = 15不是质数，15 + 1 = 16不是质数，16 + 1 = 17是质数，停止循环，由此得到质数17。
代码实现：
**第一步：**首先需要为HashTable类添加判断质数的isPrime方法和获取质数的getPrime方法：
//判断传入的num是否质数HashTable.prototype.isPrime = function(num){if (num <= 1) {return false;}//1.获取num的平方根:Math.sqrt(num)//2.循环判断for(let i = 2; i<= Math.sqrt(num); i++ ){if(num % i == 0){return false;}}return true;}//获取质数的方法HashTable.prototype.getPrime = function(num){//7*2=14,+1=15,+1=16,+1=17(质数)while (!this.isPrime(num)) {num++;}return num;}
**第二步：**修改添加元素的put方法和删除元素的remove方法中关于数组扩容的相关操作：
在put方法中添加如下代码：
//判断是否需要扩容操作if(this.count > this.limit * 0.75){let newSize = this.limit * 2;let newPrime = this.getPrime(newSize);this.resize(newPrime);}
在remove方法中添加如下代码：
//缩小容量if (this.limit > 7 && this.count < this.limit * 0.25) {let newSize = Math.floor(this.limit / 2);let newPrime = this.getPrime(newSize);this.resize(newPrime);}
测试代码：
let ht = new HashTable();ht.put('class1','Tom');ht.put('class2','Mary');ht.put('class3','Gogo');ht.put('class4','Tony');ht.put('class5','5');ht.put('class6','6');ht.put('class7','7');ht.put('class8','8');ht.put('class9','9');ht.put('class10','10');console.log(ht.size());//10console.log(ht.limit);//17
测试结果：
哈希表的完整实现
/*使用构造函数实现*///封装哈希表类function HashTable() {//属性this.storage = []this.count = 0//计算已经存储的元素个数//装填因子：loadFactor > 0.75时需要扩容；loadFactor < 0.25时需要减少容量this.limit = 7//初始长度//方法//哈希函数HashTable.prototype.hashFunc = function(str, size=7){//1.定义hashCode变量let hashCode = 0;//2.霍纳法则，计算hashCode的值//cats -> Unicode编码for(let i = 0 ;i < str.length; i++){// str.charCodeAt(i)//获取某个字符对应的unicode编码hashCode = 37 * hashCode + str.charCodeAt(i);}//3.取余操作let index = hashCode % size;return index;}//一.插入&修改操作HashTable.prototype.put = function (key, value){//1.根据key获取对应的indexlet index = this.hashFunc(key, this.limit);//2.根据index取出对应的bucketlet bucket = this.storage[index];//3.判断该bucket是否为nullif (bucket == null) {bucket = [];this.storage[index] = bucket;}//4.判断是否是修改数据for (let i = 0; i < bucket.length; i++) {let tuple = bucket[i];if (tuple[0] == key) {tuple[1] = value;return//不用返回值}}//5.进行添加操作bucket.push([key, value]);this.count += 1;//6.判断是否需要扩容操作if(this.count > this.limit * 0.75){let newSize = this.limit * 2;let newPrime = this.getPrime(newSize);this.resize(newPrime);}}//二.获取操作HashTable.prototype.get = function(key){//1.根据key获取对应的indexlet index = this.hashFunc(key, this.limit);//2.根据index获取对应的bucketlet bucket = this.storage[index];//3.判断bucket是否等于nullif (bucket == null) {return null;}//4.有bucket，那么就进行线性查找for (let i = 0; i < bucket.length; i++) {let tuple = bucket[i];if (tuple[0] == key); {//tuple[0]存储key，tuple[1]存储valuereturn tuple[1];}}//5.依然没有找到，那么返回nullreturn null;}//三.删除操作HashTable.prototype.remove = function(key){//1.根据key获取对应的indexlet index = this.hashFunc(key, this.limit);//2.根据index获取对应的bucketlet bucket = this.storage[index];//3.判断bucket是否为nullif (bucket == null) {return null;}//4.有bucket,那么就进行线性查找并删除for (let i = 0; i < bucket.length; i++) {let tuple = bucket[i];if (tuple[0] == key) {bucket.splice(i,1);this.count -= 1 ;return tuple[1];//6.缩小容量if (this.limit > 7 && this.count < this.limit * 0.25) {let newSize = Math.floor(this.limit / 2);let newPrime = this.getPrime(newSize);this.resize(newPrime);}}}//5.依然没有找到，返回nullreturn null;}/*------------------其他方法--------------------*///判断哈希表是否为nullHashTable.prototype.isEmpty = function(){return this.count == 0;}//获取哈希表中元素的个数HashTable.prototype.size = function(){return this.count;}//哈希表扩容HashTable.prototype.resize = function(newLimit){//1.保存旧的storage数组内容let oldStorage = this.storage;//2.重置所有的属性this.storage = [];this.count = 0;this.limit = newLimit;//3.遍历oldStorage中所有的bucketfor (let i = 0; i < oldStorage.length; i++) {//3.1.取出对应的bucketconst bucket = oldStorage[i];//3.2.判断bucket是否为nullif (bucket == null) {continue}//3.3.bucket中有数据，就取出数据重新插入for (let j = 0; j < bucket.length; j++) {const tuple = bucket[j];this.put(tuple[0], tuple[1]);//插入数据的key和value}}}//判断传入的num是否质数HashTable.prototype.isPrime = function(num){if (num <= 1) {return false;}//1.获取num的平方根:Math.sqrt(num)//2.循环判断for(var i = 2; i<= Math.sqrt(num); i++ ){if(num % i == 0){return false;}}return true;}//获取质数的方法HashTable.prototype.getPrime = function(num){//7*2=14,+1=15,+1=16,+1=17(质数)while (!this.isPrime(num)) {num++;}return num;}}
/*使用class实现*/class HashTable {constructor() {this.storage = []; // 哈希表存储数据的变量this.count = 0; // 当前存放的元素个数this.limit = 7; // 哈希表长度（初始设为质数 7）// 装填因子(已有个数/总个数)this.loadFactor = 0.75;this.minLoadFactor = 0.25;}// getPrime(number) 根据传入的 number 获取最临近的质数getPrime(number) {while (!isPrime(number)) {number++;}return number;}// put(key, value) 往哈希表里添加数据put(key, value) {// 1、根据 key 获取要映射到 storage 里面的 index（通过哈希函数获取）const index = hashFn(key, this.limit);// 2、根据 index 取出对应的 bucketlet bucket = this.storage[index];// 3、判断是否存在 bucketif (bucket === undefined) {bucket = []; // 不存在则创建this.storage[index] = bucket;}// 4、判断是插入数据操作还是修改数据操作for (let i = 0; i < bucket.length; i++) {let tuple = bucket[i]; // tuple 的格式：[key, value]if (tuple[0] === key) {// 如果 key 相等，则修改数据tuple[1] = value;return; // 修改完 tuple 里数据，return 终止，不再往下执行。}}// 5、bucket 新增数据bucket.push([key, value]); // bucket 存储元组 tuple，格式为 [key, value]this.count++;// 判断哈希表是否要扩容，若装填因子 > 0.75，则扩容if (this.count / this.limit > this.loadFactor) {this.resize(this.getPrime(this.limit * 2));}}// 根据 get(key) 获取 valueget(key) {const index = hashFn(key, this.limit);const bucket = this.storage[index];if (bucket === undefined) {return null;}for (const tuple of bucket) {if (tuple[0] === key) {return tuple[1];}}return null;}// remove(key) 删除指定 key 的数据remove(key) {const index = hashFn(key, this.limit);const bucket = this.storage[index];if (bucket === undefined) {return null;}// 遍历 bucket，找到对应位置的 tuple，将其删除for (let i = 0, len = bucket.length; i < len; i++) {const tuple = bucket[i];if (tuple[0] === key) {bucket.splice(i, 1); // 删除对应位置的数组项this.count--;// 根据装填因子的大小，判断是否要进行哈希表压缩if (this.limit > 7 && this.count / this.limit < this.minLoadFactor) {this.resize(this.getPrime(Math.floor(this.limit / 2)));}return tuple;}}}isEmpty() {return this.count === 0;}size() {return this.count;}// 重新调整哈希表大小，扩容或压缩resize(newLimit) {// 1、保存旧的 storage 数组内容const oldStorage = this.storage;// 2、重置所有属性this.storage = [];this.count = 0;this.limit = newLimit;// 3、遍历 oldStorage，取出所有数据，重新 put 到 this.storagefor (const bucket of oldStorage) {if (bucket) {for (const b of bucket) {this.put(b[0], b[1]);}}}}}
树
树结构简介
什么是树？
真实的树：
树的特点：
树一般都有一个根，连接着根的是树干；树干会发生分叉，形成许多树枝，树枝会继续分化成更小的树枝；树枝的最后是叶子；
现实生活中很多结构都是树的抽象，模拟的树结构相当于旋转180°的树。
树结构对比于数组/链表/哈希表有哪些优势呢：
数组：
优点：可以通过下标值访问，效率高；缺点：查找数据时需要先对数据进行排序，生成有序数组，才能提高查找效率；并且在插入和删除元素时，需要大量的位移操作；
链表：
优点：数据的插入和删除操作效率都很高；缺点：查找效率低，需要从头开始依次查找，直到找到目标数据为止；当需要在链表中间位置插入或删除数据时，插入或删除的效率都不高。
哈希表：
优点：哈希表的插入/查询/删除效率都非常高；缺点：空间利用率不高，底层使用的数组中很多单元没有被利用；并且哈希表中的元素是无序的，不能按照固定顺序遍历哈希表中的元素；而且不能快速找出哈希表中最大值或最小值这些特殊值。
树结构：
优点：树结构综合了上述三种结构的优点，同时也弥补了它们存在的缺点（虽然效率不一定都比它们高），比如树结构中数据都是有序的，查找效率高；空间利用率高；并且可以快速获取最大值和最小值等。
总的来说：每种数据结构都有自己特定的应用场景。
树结构
树（Tree）:由 n（n ≥ 0）个节点构成的有限集合。当 n = 0 时，称为空树。对于任一棵非空树（n > 0），它具备以下性质：
数中有一个称为**根（Root）**的特殊节点，用 **r **表示；其余节点可分为 m（m > 0）个互不相交的有限集合 T1，T2，…，Tm，其中每个集合本身又是一棵树，称为原来树的子树（SubTree）。
树的常用术语
节点的度（Degree）：节点的子树个数，比如节点B的度为2；树的度：树的所有节点中最大的度数，如上图树的度为2；叶节点（Leaf）：度为0的节点（也称为叶子节点），如上图的H，I等；父节点（Parent）：度不为0的节点称为父节点，如上图节点B是节点D和E的父节点；子节点（Child）：若B是D的父节点，那么D就是B的子节点；兄弟节点（Sibling）：具有同一父节点的各节点彼此是兄弟节点，比如上图的B和C，D和E互为兄弟节点；路径和路径长度：路径指的是一个节点到另一节点的通道，路径所包含边的个数称为路径长度，比如A->H的路径长度为3；节点的层次（Level）：规定根节点在1层，其他任一节点的层数是其父节点的层数加1。如B和C节点的层次为2；树的深度（Depth）：树种所有节点中的最大层次是这棵树的深度，如上图树的深度为4；树结构的表示
最普通的表示方法：如图，树结构的组成方式类似于链表，都是由一个个节点连接构成。不过，根据每个父节点子节点数量的不同，每一个父节点需要的引用数量也不同。比如节点A需要3个引用，分别指向子节点B，C，D；B节点需要2个引用，分别指向子节点E和F；K节点由于没有子节点，所以不需要引用。
这种方法缺点在于我们无法确定某一结点的引用数。
儿子-兄弟表示法：
这种表示方法可以完整地记录每个节点的数据，比如：
//节点ANode{//存储数据this.data = data;//统一只记录左边的子节点this.leftChild = B;//统一只记录右边的第一个兄弟节点this.rightSibling = null;}//节点BNode{this.data = data;this.leftChild = E;this.rightSibling = C;}//节点FNode{this.data = data;this.leftChild = null;this.rightSibling = null;}
这种表示法的优点在于每一个节点中引用的数量都是确定的。
儿子-兄弟表示法旋转
将儿子-兄弟表示法组成的树结构顺时针旋转45°之后：
这样就成为了一棵二叉树，由此我们可以得出结论：任何树都可以通过二叉树进行模拟。但是这样父节点不是变了吗？其实，父节点的设置只是为了方便指向子节点，在代码实现中谁是父节点并没有关系，只要能正确找到对应节点即可。
因为任何树都可以通过二叉树进行模拟，所以我们这里不再讨论一般的树，而是直接学习二叉树。
二叉树
二叉树简介
二叉树的概念：如果树中的每一个节点最多只能有两个子节点（左子节点和右子节点），这样的树就称为二叉树。
二叉树十分重要，不仅仅是因为简单，更是因为几乎所有的树都可以表示成二叉树形式。
二叉树的组成：
二叉树可以为空，也就是没有节点；若二叉树不为空，则它由根节点和称为其左子树TL和右子树TR的两个不相交的二叉树组成。
二叉树的五种形态：
上图分别表示：空的二叉树、只有一个节点的二叉树、只有左子树TL的二叉树、只有右子树TR的二叉树和有左右两个子树的二叉树。
二叉树的特性：
一个二叉树的第 i 层的最大节点树为：2(i-1)，i >= 1；
深度为k的二叉树的最大节点总数为：2k - 1 ，k >= 1；
对任何非空二叉树，若 n0 表示叶子节点的个数，n2表示度为2的非叶子节点个数，那么两者满足关系：n0 = n2+ 1。
如下图所示：H，E，I，J，G为叶子节点，总数为5；A，B，C，F为度为2的非叶子节点，总数为4；满足n0 = n2 + 1的规律。
特殊的二叉树
完美二叉树
完美二叉树（Perfect Binary Tree）也成为满二叉树（Full Binary Tree），在二叉树中，除了最下一层的叶子节点外，每层节点都有2个子节点，这就构成了完美二叉树。
完全二叉树
完全二叉树（Complete Binary Tree）:
除了二叉树最后一层外，其他各层的节点数都达到了最大值；并且，最后一层的叶子节点从左向右是连续存在，只缺失右侧若干叶子节点；完美二叉树是特殊的完全二叉树。
二叉树的存储
常见的二叉树存储方式为数组和链表：
使用数组：
完全二叉树：按从上到下，从左到右的方式存储数据。
使用数组存储时，取数据的时候也十分方便：左子节点的序号等于父节点序号 * 2，右子节点的序号等于父节点序号 * 2 + 1 。
非完全二叉树：非完全二叉树需要转换成完全二叉树才能按照上面的方案存储，这样会浪费很大的存储空间。
使用链表
二叉树最常见的存储方式为链表：每一个节点封装成一个Node，Node中包含存储的数据、左节点的引用和右节点的引用。
二叉搜索树
认识二叉搜索树
二叉搜索树（BST，Binary Search Tree），也称为二叉排序树和二叉查找树。
二叉搜索树是一棵二叉树，可以为空；
如果不为空，则满足以下性质：
条件1：非空左子树的所有键值小于其根节点的键值。比如三中节点6的所有非空左子树的键值都小于6；条件2：非空右子树的所有键值大于其根节点的键值；比如三中节点6的所有非空右子树的键值都大于6；条件3：左、右子树本身也都是二叉搜索树（即左右子树也包含上述性质）。
如上图所示，树二和树三符合3个条件属于二叉树，树一不满足条件3所以不是二叉树。
总结：二叉搜索树的特点主要是较小的值总是保存在左节点上，相对较大的值总是保存在右节点上。这种特点使得二叉搜索树的查询效率非常高，这也就是二叉搜索树中"搜索"的来源。
二叉搜索树应用举例
下面是一个二叉搜索树：
若想在其中查找数据10，只需要查找4次，查找效率非常高。
第1次：将10与根节点9进行比较，由于10 > 9，所以10下一步与根节点9的右子节点13比较；第2次：由于10 < 13，所以10下一步与父节点13的左子节点11比较；第3次：由于10 < 11，所以10下一步与父节点11的左子节点10比较；第4次：由于10 = 10，最终查找到数据10 。
同样是15个数据，在排序好的数组中查询数据10，需要查询10次：
其实：如果是排序好的数组，可以通过二分查找：第一次找9，第二次找13，第三次找15…。我们发现如果把每次二分的数据拿出来以树的形式表示的话就是二叉搜索树。这就是数组二分法查找效率之所以高的原因。
二叉搜索树的封装
二叉树搜索树的基本属性
如图所示：二叉搜索树有四个最基本的属性：指向节点的根（root），节点中的键（key）、左指针（right）、右指针（right）。
所以，二叉搜索树中除了定义root属性外，还应定义一个节点内部类，里面包含每个节点中的left、right和key三个属性：
//封装二叉搜索树function BinarySearchTree(){//节点内部类function Node(key){this.key = key;this.left = null;this.right = null;}//属性this.root = null;}
二叉搜索树的常见操作
insert(key)：向树中插入一个新的键；search(key)：在树中查找一个键，如果节点存在，则返回true；如果不存在，则返回false；inOrderTraverse：通过中序遍历方式遍历所有节点；preOrderTraverse：通过先序遍历方式遍历所有节点；postOrderTraverse：通过后序遍历方式遍历所有节点；min：返回树中最小的值/键；max：返回树中最大的值/键；remove(key)：从树中移除某个键；二叉搜索树方法实现
1. 插入数据
实现思路：
首先根据传入的key创建节点对象；然后判断根节点是否存在，不存在时通过：this.root = newNode，直接把新节点作为二叉搜索树的根节点。若存在根节点则重新定义一个内部方法insertNode()用于查找插入点。
//insert方法:对外向用户暴露的方法BinarySearchTree.prototype.insert = function(key){//1.根据key创建节点let newNode = new Node(key);//2.判断根节点是否存在if (this.root == null) {this.root = newNode;//根节点存在时}else {this.insertNode(this.root, newNode);}}
内部方法insertNode()的实现思路:
根据比较传入的两个节点，一直查找新节点适合插入的位置，直到成功插入新节点为止。
当newNode.key < node.key向左查找:
情况1：当node无左子节点时，直接插入：情况2：当node有左子节点时，递归调用insertNode(),直到遇到无左子节点成功插入newNode后，不再符合该情况，也就不再调用insertNode()，递归停止。
当newNode.key >= node.key向右查找，与向左查找类似：
情况1：当node无右子节点时，直接插入：情况2：当node有右子节点时，依然递归调用insertNode(),直到遇到传入insertNode方法的node无右子节点成功插入newNode为止：
insertNode()代码实现：
//内部使用的insertNode方法:用于比较节点从左边插入还是右边插入BinarySearchTree.prototype.insertNode = function(node, newNode){//当newNode.key < node.key向左查找if(newNode.key < node.key){//情况1：node无左子节点，直接插入if (node.left == null) {node.left = newNode;//情况2：node有左子节点，递归调用insertNode(),直到遇到无左子节点成功插入newNode后，不再符合该情况，也就不再调用insertNode()，递归停止。}else{this.insertNode(node.left, newNode);}//当newNode.key >= node.key向右查找}else{//情况1：node无右子节点，直接插入if(node.right == null){node.right == newNode;//情况2：node有右子节点，依然递归调用insertNode(),直到遇到无右子节点成功插入newNode为止}else{this.insertNode(node.right, newNode);}}}
测试代码：
//测试代码//1.创建BinarySearchTreelet bst = new BinarySearchTree();//2.插入数据bst.insert(11);bst.insert(7);bst.insert(15);bst.insert(5);bst.insert(9);console.log(bst);
应得到下图所示的二叉搜索树：
测试结果:
2. 数据遍历
这里所说的树的遍历不仅仅针对二叉搜索树，而是适用于所有的二叉树。由于树结构不是线性结构，所以遍历方式有多种选择，常见的三种二叉树遍历方式为：
先序遍历；中序遍历；后序遍历。
还有层序遍历，使用较少。
2.1.先序遍历
先序遍历的过程为：
首先，遍历根节点；然后，遍历其左子树；最后，遍历其右子树。
如上图所示，二叉树的节点遍历顺序为：A -> B -> D -> H -> I -> E -> C -> F -> G。
代码实现：
//先序遍历//掺入一个handler函数方便之后对得到的key进行处理BinarySearchTree.prototype.preOrderTraversal = function(handler){this.preOrderTraversalNode(this.root, handler);}//封装内部方法，对某个节点进行遍历BinarySearchTree.prototype.preOrderTraversalNode = function(node,handler){if (node != null) {//1.处理经过的节点handler(node.key);/*-------递归1---------*///2.遍历左子树中的节点this.preOrderTraversalNode(node.left, handler);/*--------递归2-------*///3.遍历右子树中的节点this.preOrderTraversalNode(node.right, handler);}}
过程详解：
以遍历以下二叉搜索树为例：
首先调用preOrderTraversal方法，在方法里再调用preOrderTraversalNode方法用于遍历二叉搜索树。在preOrderTraversalNode方法中，递归1负责遍历左子节点，递归2负责遍历右子节点。先执行递归1，执行过程如下图所示：
记：preOrderTraversalNode() 为 A()
可以看到一共递归调用了4次方法A，分别传入11、7、5、3，最后遇到null不满足 node != null 条件结束递归1；注意此时只是执行完最开始的递归1，并没有执行递归2，并且递归1执行到null停止后要一层层地往上返回，按顺序将调用的函数压出函数调用栈。
关于函数调用栈：之前的四次递归共把4个函数压入了函数调用栈，现在递归执行完了一层层地把函数压出栈。
值得注意的是：每一层函数都只是执行完了递归1，当返回到该层函数时，比如A（3）要继续执行递归2遍历二叉搜索树中的右子节点；
在执行递归2的过程中会不断调用方法A，并依次执行递归1和递归2，以此类推直到遇到null不满足 node != null 条件为止，才停止递归并一层层返回，如此循环。同理A（5）层、A（7）层、A（11）层都要经历上述循环，直到将二叉搜索树中的节点全部遍历完为止。
具体过程如下图所示：
测试代码：
//测试代码//1.创建BinarySearchTreelet bst = new BinarySearchTree()//2.插入数据bst.insert(11);bst.insert(7);bst.insert(15);bst.insert(5);bst.insert(3);bst.insert(9);bst.insert(8);bst.insert(10);bst.insert(13);bst.insert(12);bst.insert(14);bst.insert(20);bst.insert(18);bst.insert(25);bst.insert(6);//3.测试遍历let resultString = "";//掺入处理节点值的处理函数bst.preOrderTraversal(function(key){resultString += key + "->";})alert(resultString);
应输出这样的顺序：11 -> 7 -> 5 -> 3 -> 6 -> 9 -> 8 -> 10 -> 15 -> 13 ->12 -> 14 -> 20 -> 18 -> 25 。
测试结果：
2.2.中序遍历
实现思路：与先序遍历原理相同，只不过是遍历的顺序不一样了。
首先，遍历其左子树；然后，遍历根（父）节点；最后，遍历其右子树。
代码实现：
//中序遍历BinarySearchTree.prototype.midOrderTraversal = function(handler){this.midOrderTraversalNode(this.root, handler);}BinarySearchTree.prototype.midOrderTraversalNode = function(node, handler){if (node != null) {//1.遍历左子树中的节点this.midOrderTraversalNode(node.left, handler);//2.处理节点handler(node.key);//3.遍历右子树中的节点this.midOrderTraversalNode(node.right, handler);}}
过程详解：
遍历的顺序应如下图所示：
原作者这里画的有点错误，看到了吗？
首先调用midOrderTraversal方法，在方法里再调用midOrderTraversalNode方法用于遍历二叉搜索树。先使用递归1遍历左子树中的节点；然后，处理父节点；最后，遍历右子树中的节点。
测试代码：
//测试代码//1.创建BinarySearchTreelet bst = new BinarySearchTree();//2.插入数据bst.insert(11);bst.insert(7);bst.insert(15);bst.insert(5);bst.insert(3);bst.insert(9);bst.insert(8);bst.insert(10);bst.insert(13);bst.insert(12);bst.insert(14);bst.insert(20);bst.insert(18);bst.insert(25);bst.insert(6);//3.测试中序遍历let resultString2 ="";bst.midOrderTraversal(function(key){resultString2 += key + "->";})alert(resultString2);
输出节点的顺序应为：3 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 13 -> 14 -> 15 -> 18 -> 20 -> 25 。
测试结果：
2.3.后序遍历
实现思路：与先序遍历原理相同，只不过是遍历的顺序不一样了。
首先，遍历其左子树；然后，遍历其右子树；最后，遍历根（父）节点；
代码实现：
//后序遍历BinarySearchTree.prototype.postOrderTraversal = function(handler){this.postOrderTraversalNode(this.root, handler);}BinarySearchTree.prototype.postOrderTraversalNode = function(node, handler){if (node != null) {//1.遍历左子树中的节点this.postOrderTraversalNode(node.left, handler);//2.遍历右子树中的节点this.postOrderTraversalNode(node.right, handler);//3.处理节点handler(node.key);}}
过程详解：
遍历的顺序应如下图所示：
首先调用postOrderTraversal方法，在方法里再调用postOrderTraversalNode方法用于遍历二叉搜索树。先使用递归1遍历左子树中的节点；然后，遍历右子树中的节点；最后，处理父节点。
测试代码：
//测试代码//1.创建BinarySearchTreelet bst = new BinarySearchTree();//2.插入数据bst.insert(11);bst.insert(7);bst.insert(15);bst.insert(5);bst.insert(3);bst.insert(9);bst.insert(8);bst.insert(10);bst.insert(13);bst.insert(12);bst.insert(14);bst.insert(20);bst.insert(18);bst.insert(25);bst.insert(6);//3.测试后序遍历let resultString3 ="";bst.postOrderTraversal(function(key){resultString3 += key + "->";})alert(resultString3);
输出节点的顺序应为：3 -> 6 -> 5 -> 8 -> 10 -> 9 -> 7 -> 12 -> 14 -> 13 -> 18 -> 25 -> 20 -> 15 -> 11 。
测试结果：
**总结：**以遍历根（父）节点的顺序来区分三种遍历方式。比如：先序遍历先遍历根节点、中序遍历第二遍历根节点、后续遍历最后遍历根节点。
3. 查找数据
3.1.查找最大值&最小值
在二叉搜索树中查找最值非常简单，最小值在二叉搜索树的最左边，最大值在二叉搜索树的最右边。只需要一直向左/右查找就能得到最值，如下图所示：
代码实现：
//寻找最大值BinarySearchTree.prototype.max = function () {//1.获取根节点let node = this.root;//2.定义key保存节点值let key = null;//3.依次向右不断查找，直到节点为nullwhile (node != null) {key = node.key;node = node.right;}return key;}//寻找最小值BinarySearchTree.prototype.min = function(){//1.获取根节点let node = this.root;//2.定义key保存节点值let key = null;//3.依次向左不断查找，直到节点为nullwhile (node != null) {key = node.key;node = node.left;}return key;}
测试代码：
//测试代码//1.创建BinarySearchTreelet bst = new BinarySearchTree();//2.插入数据bst.insert(11);bst.insert(7);bst.insert(15);bst.insert(5);bst.insert(3);bst.insert(9);bst.insert(8);bst.insert(10);bst.insert(13);bst.insert(12);bst.insert(14);bst.insert(20);bst.insert(18);bst.insert(25);bst.insert(6);//4.测试最值console.log(bst.max());console.log(bst.min());
测试结果：
3.2.查找特定值
查找二叉搜索树当中的特定值效率也非常高。只需要从根节点开始将需要查找节点的key值与之比较，若node.key < root则向左查找，若node.key > root就向右查找，直到找到或查找到null为止。这里可以使用递归实现，也可以采用循环来实现。
实现代码：
//查找特定的keyBinarySearchTree.prototype.search = function(key){//1.获取根节点let node = this.root;//2.循环搜索keywhile(node != null){if (key < node.key) {//小于根(父)节点就往左边找node = node.left;//大于根(父)节点就往右边找}else if(key > node.key){node = node.right;}else{return true;}} return false;}
测试代码：
//测试代码//1.创建BinarySearchTreelet bst = new BinarySearchTree();//2.插入数据bst.insert(11);bst.insert(7);bst.insert(15);bst.insert(5);bst.insert(3);bst.insert(9);bst.insert(8);bst.insert(10);bst.insert(13);bst.insert(12);bst.insert(14);bst.insert(20);bst.insert(18);bst.insert(25);bst.insert(6);//3.测试搜索方法console.log(bst.search(24));//falseconsole.log(bst.search(13));//trueconsole.log(bst.search(2));//false
测试结果：
4. 删除数据
实现思路：
**第一步：**先找到需要删除的节点，若没找到，则不需要删除；
首先定义变量current用于保存需要删除的节点、变量parent用于保存它的父节点、变量isLeftChild保存current是否为parent的左节点，这样方便之后删除节点时改变相关节点的指向。
实现代码：
//1.1.定义变量let current = this.root;let parent = null;let isLeftChild = true;//1.2.开始寻找删除的节点while (current.key != key) {parent = current;// 小于则往左查找if (key < current.key) {isLeftChild = true;current = current.left;} else{//大于则往右查找isLeftChild = false;current = current.rigth;}//找到最后依然没有找到相等的节点if (current == null) {return false;}}//结束while循环后：current.key = key
**第二步：**删除找到的指定节点，后分3种情况：
删除叶子节点；删除只有一个子节点的节点；删除有两个子节点的节点。
4.1.情况1：没有子节点
没有子节点时也有两种情况：
当该叶子节点为根节点时，如下图所示，此时current == this.root，直接通过：this.root = null，删除根节点。
当该叶子节点不为根节点时也有两种情况，如下图所示：
若current = 8，可以通过：parent.left = null，删除节点8；
若current = 10，可以通过：parent.right = null，删除节点10。
代码实现：
//情况1：删除的是叶子节点(没有子节点)if (current.left == null && current.right ==null) {if (current == this.root) {this.root = null;}else if(isLeftChild){parent.left = null;}else {parent.right =null;}}
4.2.情况2：有一个子节点
有六种情况分别是：
当current存在左子节点时（current.right == null）：
情况1：current为根节点（current == this.root），如节点11，此时通过：this.root = current.left，删除根节点11；情况2：current为父节点parent的左子节点（isLeftChild == true），如节点5，此时通过：parent.left = current.left，删除节点5；情况3：current为父节点parent的右子节点（isLeftChild == false），如节点9，此时通过：parent.right = current.left，删除节点9；
当current存在右子节点时（current.left = null）：
情况4：current为根节点（current == this.root），如节点11，此时通过：this.root = current.right，删除根节点11。情况5：current为父节点parent的左子节点（isLeftChild == true），如节点5，此时通过：parent.left = current.right，删除节点5；情况6：current为父节点parent的右子节点（isLeftChild == false），如节点9，此时通过：parent.right = current.right，删除节点9；
实现代码：
//情况2：删除的节点有一个子节点//当current存在左子节点时else if(current.right == null){if (current == this.root) {this.root = current.left;} else if(isLeftChild) {parent.left = current.left;} else{parent.right = current.left;}//当current存在右子节点时} else if(current.left == null){if (current == this.root) {this.root = current.right;} else if(isLeftChild) {parent.left = current.right;} else{parent.right = current.right;} }
4.3.情况3：有两个子节点
这种情况十分复杂，首先依据以下二叉搜索树，讨论这样的问题：
删除节点9
在保证删除节点9后原二叉树仍为二叉搜索树的前提下，有两种方式：
方式1：从节点9的左子树中选择一合适的节点替代节点9，可知节点8符合要求；方式2：从节点9的右子树中选择一合适的节点替代节点9，可知节点10符合要求；
删除节点7
在保证删除节点7后原二叉树仍为二叉搜索树的前提下，也有两种方式：
方式1：从节点7的左子树中选择一合适的节点替代节点7，可知节点5符合要求；方式2：从节点7的右子树中选择一合适的节点替代节点7，可知节点8符合要求；
删除节点15
在保证删除节点15后原树二叉树仍为二叉搜索树的前提下，同样有两种方式：
方式1：从节点15的左子树中选择一合适的节点替代节点15，可知节点14符合要求；方式2：从节点15的右子树中选择一合适的节点替代节点15，可知节点18符合要求；
相信你已经发现其中的规律了！
规律总结：如果要删除的节点有两个子节点，甚至子节点还有子节点，这种情况下需要从要删除节点下面的子节点中找到一个合适的节点，来替换当前的节点。
若用current表示需要删除的节点，则合适的节点指的是：
current左子树中比current小一点点的节点，即current左子树中的最大值；current右子树中比current大一点点的节点，即current右子树中的最小值。
前驱&后继
在二叉搜索树中，这两个特殊的节点有特殊的名字：
比current小一点点的节点，称为current节点的前驱。比如下图中的节点5就是节点7的前驱；比current大一点点的节点，称为current节点的后继。比如下图中的节点8就是节点7的后继；
代码实现：
查找需要被删除的节点current的后继时，需要在current的右子树中查找最小值，即在current的右子树中一直向左遍历查找；查找前驱时，则需要在current的左子树中查找最大值，即在current的左子树中一直向右遍历查找。
下面只讨论查找current后继的情况，查找前驱的原理相同，这里暂不讨论。
4.4.完整实现
//删除节点BinarySearchTree.prototype.remove = function(key){/*------------------------------1.寻找要删除的节点---------------------------------*///1.1.定义变量current保存删除的节点，parent保存它的父节点。isLeftChild保存current是否为parent的左节点let current = this.root;let parent = null;let isLeftChild = true;//1.2.开始寻找删除的节点while (current.key != key) {parent = current;// 小于则往左查找if (key < current.key) {isLeftChild = true;current = current.left;} else{isLeftChild = false;current = current.right;}//找到最后依然没有找到相等的节点if (current == null) {return false;}}//结束while循环后：current.key = key/*------------------------------2.根据对应情况删除节点------------------------------*///情况1：删除的是叶子节点(没有子节点)if (current.left == null && current.right ==null) {if (current == this.root) {this.root = null;}else if(isLeftChild){parent.left = null;}else {parent.right =null;}}//情况2：删除的节点有一个子节点//当current存在左子节点时else if(current.right == null){if (current == this.root) {this.root = current.left;} else if(isLeftChild) {parent.left = current.left;} else{parent.right = current.left;}//当current存在右子节点时} else if(current.left == null){if (current == this.root) {this.root = current.right;} else if(isLeftChild) {parent.left = current.right;} else{parent.right = current.right} }//情况3：删除的节点有两个子节点else{//1.获取后继节点let successor = this.getSuccessor(current);//2.判断是否根节点if (current == this.root) {this.root = successor;}else if (isLeftChild){parent.left = successor;}else{parent.right = successor;}//3.将后继的左子节点改为被删除节点的左子节点successor.left = current.left;}}//封装查找后继的方法BinarySearchTree.prototype.getSuccessor = function(delNode){//1.定义变量,保存找到的后继let successor = delNode;let current = delNode.right;let successorParent = delNode;//2.循环查找current的右子树节点while(current != null){successorParent = successorsuccessor = current;current = current.left;}//3.判断寻找到的后继节点是否直接就是删除节点的right节点if(successor != delNode.right){successorParent.left = successor.right;successor.right = delNode.right ;}return successor;}
测试代码：
//测试代码//1.创建BinarySearchTreelet bst = new BinarySearchTree();//2.插入数据bst.insert(11);bst.insert(7);bst.insert(15);bst.insert(5);bst.insert(3);bst.insert(9);bst.insert(8);bst.insert(10);bst.insert(13);bst.insert(12);bst.insert(14);bst.insert(20);bst.insert(18);bst.insert(25);bst.insert(6);bst.insert(19);//3.测试删除代码//删除没有子节点的节点bst.remove(3);bst.remove(8);bst.remove(10);//删除有一个子节点的节点bst.remove(5);bst.remove(19);//删除有两个子节点的节点bst.remove(9);bst.remove(7);bst.remove(15);//遍历二叉搜索树并输出let resultString = "";bst.midOrderTraversal(function(key){resultString += key + "->";})alert(resultString);
测试结果：
可见三种情况的节点都被成功删除了。
完整封装
1） 使用function实现
/*使用构造函数实现*/ //封装二叉搜索树function BinarySearchTree(){//节点内部类function Node(key){this.key = keythis.left = nullthis.right = null}//属性this.root = null//方法//一.插入数据：insert方法:对外向用户暴露的方法BinarySearchTree.prototype.insert = function(key){//1.根据key创建节点let newNode = new Node(key)//2.判断根节点是否存在if (this.root == null) {this.root = newNode//根节点存在时}else {this.insertNode(this.root, newNode)}}//内部使用的insertNode方法:用于比较节点从左边插入还是右边插入BinarySearchTree.prototype.insertNode = function(node, newNode){//当newNode.key < node.key向左查找if(newNode.key < node.key){//情况1：node无左子节点，直接插入if (node.left == null) {node.left = newNode//情况2：node有左子节点，递归调用insertNode(),直到遇到无左子节点成功插入newNode后，不再符合该情况，也就不再调用insertNode()，递归停止。}else{this.insertNode(node.left, newNode)}//当newNode.key >= node.key向右查找}else{//情况1：node无右子节点，直接插入if(node.right == null){node.right = newNode//情况2：node有右子节点，依然递归调用insertNode(),直到遇到无右子节点成功插入newNode为止}else{this.insertNode(node.right, newNode)}}}//二.树的遍历//1.先序遍历//掺入一个handler函数对得到的key进行处理BinarySearchTree.prototype.preOrderTraversal = function(handler){this.preOrderTraversalNode(this.root, handler)}//封装内部方法，对某个节点进行遍历BinarySearchTree.prototype.preOrderTraversalNode = function(node,handler){if (node != null) {//1.处理经过的节点handler(node.key)//2.遍历经过节点的左子节点this.preOrderTraversalNode(node.left, handler)//3.遍历经过节点的右子节点this.preOrderTraversalNode(node.right, handler)}}//2.中序遍历BinarySearchTree.prototype.midOrderTraversal = function(handler){this.midOrderTraversalNode(this.root, handler)}BinarySearchTree.prototype.midOrderTraversalNode = function(node, handler){if (node != null) {//1.遍历左子树中的节点this.midOrderTraversalNode(node.left, handler)//2.处理节点handler(node.key)//3.遍历右子树中的节点this.midOrderTraversalNode(node.right, handler)}}//3.后序遍历BinarySearchTree.prototype.postOrderTraversal = function(handler){this.postOrderTraversalNode(this.root, handler)}BinarySearchTree.prototype.postOrderTraversalNode = function(node, handler){if (node != null) {//1.遍历左子树中的节点this.postOrderTraversalNode(node.left, handler)//2.遍历右子树中的节点this.postOrderTraversalNode(node.right, handler)//3.处理节点handler(node.key)}}//三.寻找最值//寻找最大值BinarySearchTree.prototype.max = function () {//1.获取根节点let node = this.root//2.定义key保存节点值let key = null//3.依次向右不断查找，直到节点为nullwhile (node != null) {key = node.keynode = node.right}return key}//寻找最小值BinarySearchTree.prototype.min = function(){//1.获取根节点let node = this.root//2.定义key保存节点值let key = null//3.依次向左不断查找，直到节点为nullwhile (node != null) {key = node.keynode = node.left}return key}//查找特定的keyBinarySearchTree.prototype.search = function(key){//1.获取根节点let node = this.root//2.循环搜索keywhile(node != null){if (key < node.key) {//小于根(父)节点就往左边找node = node.left//大于根(父)节点就往右边找}else if(key > node.key){node = node.right}else{return true}} return false}//四.删除节点BinarySearchTree.prototype.remove = function(key){/*------------------------------1.寻找要删除的节点---------------------------------*///1.1.定义变量current保存删除的节点，parent保存它的父节点。isLeftChild保存current是否为parent的左节点let current = this.rootlet parent = nulllet isLeftChild = true//1.2.开始寻找删除的节点while (current.key != key) {parent = current// 小于则往左查找if (key < current.key) {isLeftChild = truecurrent = current.left} else{isLeftChild = falsecurrent = current.right}//找到最后依然没有找到相等的节点if (current == null) {return false}}//结束while循环后：current.key = key/*------------------------------2.根据对应情况删除节点------------------------------*///情况1：删除的是叶子节点(没有子节点)if (current.left == null && current.right ==null) {if (current == this.root) {this.root = null}else if(isLeftChild){parent.left = null}else {parent.right =null}}//情况2：删除的节点有一个子节点//当current存在左子节点时else if(current.right == null){if (current == this.root) {this.root = current.left} else if(isLeftChild) {parent.left = current.left} else{parent.right = current.left}//当current存在右子节点时} else if(current.left == null){if (current == this.root) {this.root = current.right} else if(isLeftChild) {parent.left = current.right} else{parent.right = current.right} }//情况3：删除的节点有两个子节点else{//1.获取后继节点let successor = this.getSuccessor(current)//2.判断是否根节点if (current == this.root) {this.root = successor}else if (isLeftChild){parent.left = successor}else{parent.right = successor}//3.将后继的左子节点改为被删除节点的左子节点successor.left = current.left}}//封装查找后继的方法BinarySearchTree.prototype.getSuccessor = function(delNode){//1.定义变量,保存找到的后继let successor = delNodelet current = delNode.rightlet successorParent = delNode//2.循环查找current的右子树节点while(current != null){successorParent = successorsuccessor = currentcurrent = current.left}//3.判断寻找到的后继节点是否直接就是删除节点的right节点if(successor != delNode.right){successorParent.left = successor.rightsuccessor.right = delNode.right }return successor}}
2）使用class实现
// 删除节点remove(key) {let currentNode = this.root;let parentNode = null;let isLeftChild = true;// 循环查找到要删除的节点 currentNode，以及它的 parentNode、isLeftChildwhile (currentNode.key !== key) {parentNode = currentNode;// 小于，往左查找if (key < currentNode.key) {isLeftChild = true;currentNode = currentNode.left;} else {// 否则往右查找isLeftChild = false;currentNode = currentNode.right;}// 找到最后都没找到相等的节点，返回 falseif (currentNode === null) {return false;}}// 1、删除的是叶子节点的情况if (currentNode.left === null && currentNode.right === null) {if (currentNode === this.root) {this.root = null;} else if (isLeftChild) {parentNode.left = null;} else {parentNode.right = null;}// 2、删除的是只有一个子节点的节点} else if (currentNode.right === null) {// currentNode 只存在左节点//-- 2.1、currentNode 只存在<左节点>的情况//---- 2.1.1、currentNode 等于 root//---- 2.1.2、parentNode.left 等于 currentNode//---- 2.1.3、parentNode.right 等于 currentNodeif (currentNode === this.root) {this.root = currentNode.left;} else if (isLeftChild) {parentNode.left = currentNode.left;} else {parentNode.right = currentNode.left;}} else if (currentNode.left === null) {// currentNode 只存在右节点//-- 2.2、currentNode 只存在<右节点>的情况//---- 2.1.1 currentNode 等于 root//---- 2.1.1 parentNode.left 等于 currentNode//---- 2.1.1 parentNode.right 等于 currentNodeif (currentNode === this.root) {this.root = currentNode.right;} else if (isLeftChild) {parentNode.left = currentNode.right;} else {parentNode.right = currentNode.right;}// 3、删除的是有两个子节点的节点} else {// 1、找到后续节点let successor = this.getSuccessor(currentNode);// 2、判断是否为根节点if (currentNode === this.root) {this.root = successor;} else if (isLeftChild) {parentNode.left = successor;} else {parentNode.right = successor;}// 3、将后续的左节点改为被删除的左节点successor.left = currentNode.left;}}// 获取后续节点，即从要删除的节点的右边开始查找最小的值getSuccessor(delNode) {// 定义变量，保存要找到的后续let successor = delNode;let current = delNode.right;let successorParent = delNode;// 循环查找 current 的右子树节点while (current !== null) {successorParent = successor;successor = current;current = current.left;}// 判断寻找到的后续节点是否直接就是要删除节点的 rightif (successor !== delNode.right) {successorParent.left = successor.right;successor.right = delNode.right;}return successor;}
平衡树
二叉搜索树的缺陷：
当插入的数据是有序的数据，就会造成二叉搜索树的深度过大。比如原二叉搜索树右 11 7 15 组成，如下图所示：
当插入一组有序数据：6 5 4 3 2就会变成深度过大的搜索二叉树，会严重影响二叉搜索树的性能。
非平衡树
比较好的二叉搜索树，它的数据应该是左右均匀分布的；但是插入连续数据后，二叉搜索树中的数据分布就变得不均匀了，我们称这种树为非平衡树；对于一棵平衡二叉树来说，插入/查找等操作的效率是O（logN）；而对于一棵非平衡二叉树来说，相当于编写了一个链表，查找效率变成了O（N）;
树的平衡性
为了能以较快的时间O（logN）来操作一棵树，我们需要保证树总是平衡的：
起码大部分是平衡的，此时的时间复杂度也是接近O（logN）的；这就要求树中每个节点左边的子孙节点的个数，应该尽可能地等于右边的子孙节点的个数；
常见的平衡树
AVL树：是最早的一种平衡树，它通过在每个节点多存储一个额外的数据来保持树的平衡。由于AVL树是平衡树，所以它的时间复杂度也是O（logN）。但是它的整体效率不如红黑树，开发中比较少用。红黑树：同样通过一些特性来保持树的平衡，时间复杂度也是O（logN）。进行插入/删除等操作时，性能优于AVL树，所以平衡树的应用基本都是红黑树。
这里有一份平衡二叉树的JS实现代码的链接，原地址：JS实现平衡二叉树。
图
这里只作较简单的说明和代码封装，感兴趣的请自行深入了解。
图的简介
什么是图？
图结构是一种与树结构有些相似的数据结构；图论是数学的一个分支，并且，在数学中，树是图的一种；图论以图为研究对象，研究顶点和边组成的图形的数学理论和方法；主要的研究目的为：事物之间的联系，顶点代表事物，边代表两个事物间的关系；
图的特点：
一组顶点：通常用V（Vertex）表示顶点的集合；一组边：通常用 E（Edge）表示边的集合； 边是顶点和顶点之间的连线；边可以是有向的，也可以是无向的。比如A----B表示无向，A —> B 表示有向；
图的常用术语：
顶点：表示图中的一个节点；边：表示顶点和顶点给之间的连线；相邻顶点：由一条边连接在一起的顶点称为相邻顶点；度：一个顶点的度是相邻顶点的数量；路径：**简单路径：**简单路径要求不包含重复的顶点；回路：第一个顶点和最后一个顶点相同的路径称为回路；无向图：图中的所有边都是没有方向的；有向图：图中的所有边都是有方向的；**无权图：**无权图中的边没有任何权重意义；**带权图：**带权图中的边有一定的权重含义；
图的表示
邻接矩阵
表示图的常用方式为：邻接矩阵。
可以使用二维数组来表示邻接矩阵；邻接矩阵让每个节点和一个整数相关联，该整数作为数组的下标值；使用一个二维数组来表示顶点之间的连接。
如上图所示：
二维数组中的0表示没有连线，1表示有连线；如：A[ 0 ] [ 3 ] = 1，表示 A 和 C 之间有连接；邻接矩阵的对角线上的值都为0，表示A - A ，B - B，等自回路都没有连接（自己与自己之间没有连接）；若为无向图，则邻接矩阵应为对角线上元素全为0的对称矩阵；
邻接矩阵的问题：
如果图是一个稀疏图，那么邻接矩阵中将存在大量的 0，造成存储空间的浪费。
邻接表
另外一种表示图的常用方式为：邻接表。
邻接表由图中每个顶点以及和顶点相邻的顶点列表组成；这个列表可用多种方式存储，比如：**数组/链表/字典（哈希表）**等都可以；
如上图所示：
图中可清楚看到A与B、C、D相邻，假如要表示这些与A顶点相邻的顶点（边），可以通过将它们作为A的值（value）存入到对应的数组/链表/字典中。之后，通过键（key）A可以十分方便地取出对应的数据；
邻接表的问题：
邻接表可以简单地得出出度，即某一顶点指向其他顶点的个数；但是，邻接表计算入度（指向某一顶点的其他顶点的个数称为该顶点的入度）十分困难。此时需要构造逆邻接表才能有效计算入度；
封装图结构
在实现过程中采用邻接表的方式来表示边，使用字典类来存储邻接表。
添加字典类和队列类
首先需要引入之前实现的，之后会用到的字典类和队列类:
//封装字典类function Dictionary(){//字典属性this.items = {}//字典操作方法//一.在字典中添加键值对Dictionary.prototype.set = function(key, value){this.items[key] = value}//二.判断字典中是否有某个keyDictionary.prototype.has = function(key){return this.items.hasOwnProperty(key)}//三.从字典中移除元素Dictionary.prototype.remove = function(key){//1.判断字典中是否有这个keyif(!this.has(key)) return false//2.从字典中删除keydelete this.items[key]return true}//四.根据key获取valueDictionary.prototype.get = function(key){return this.has(key) ? this.items[key] : undefined}//五.获取所有keysDictionary.prototype.keys = function(){return Object.keys(this.items)}//六.size方法Dictionary.prototype.keys = function(){return this.keys().length}//七.clear方法Dictionary.prototype.clear = function(){this.items = {}}}// 基于数组封装队列类function Queue() {// 属性this.items = []// 方法// 1.将元素加入到队列中Queue.prototype.enqueue = element => {this.items.push(element)}// 2.从队列中删除前端元素Queue.prototype.dequeue = () => {return this.items.shift()}// 3.查看前端的元素Queue.prototype.front = () => {return this.items[0]}// 4.查看队列是否为空Queue.prototype.isEmpty = () => {return this.items.length == 0;}// 5.查看队列中元素的个数Queue.prototype.size = () => {return this.items.length}// 6.toString方法Queue.prototype.toString = () => {let resultString = ''for (let i of this.items){resultString += i + ' '}return resultString}}
0. 创建图类
先创建图类Graph，并添加基本属性，再实现图类的常用方法：
//封装图类function Graph (){//属性：顶点(数组)/边(字典)this.vertexes = []; //顶点this.edges = new Dictionary(); //边}
1. 添加顶点与边
如图所示：
创建一个数组对象vertexes存储图的顶点；创建一个字典对象edges存储图的边，其中key为顶点，value为存储key顶点相邻顶点的数组。
代码实现：
//添加方法//一.添加顶点Graph.prototype.addVertex = function(v){this.vertexes.push(v);this.edges.set(v, []); //将边添加到字典中，新增的顶点作为键，对应的值为一个存储边的空数组}//二.添加边Graph.prototype.addEdge = function(v1, v2){//传入两个顶点为它们添加边this.edges.get(v1).push(v2);//取出字典对象edges中存储边的数组，并添加关联顶点this.edges.get(v2).push(v1);//表示的是无向表，故要添加互相指向的两条边}
2. 转换为字符串输出
为图类Graph添加toString方法，实现以邻接表的形式输出图中各顶点。
代码实现：
//三.实现toString方法:转换为邻接表形式Graph.prototype.toString = function (){//1.定义字符串，保存最终结果let resultString = "";//2.遍历所有的顶点以及顶点对应的边for (let i = 0; i < this.vertexes.length; i++) {//遍历所有顶点resultString += this.vertexes[i] + '-->';let vEdges = this.edges.get(this.vertexes[i]);for (let j = 0; j < vEdges.length; j++) {//遍历字典中每个顶点对应的数组resultString += vEdges[j] + ' ';}resultString += '\n';}return resultString;}
测试代码：
//测试代码//1.创建图结构let graph = new Graph();//2.添加顶点let myVertexes = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'];for (let i = 0; i < myVertexes.length; i++) {graph.addVertex(myVertexes[i]);}//3.添加边graph.addEdge('A', 'B');graph.addEdge('A', 'C');graph.addEdge('A', 'D');graph.addEdge('C', 'D');graph.addEdge('C', 'G');graph.addEdge('D', 'G');graph.addEdge('D', 'H');graph.addEdge('B', 'E');graph.addEdge('B', 'F');graph.addEdge('E', 'I');//4.输出结果console.log(graph.toString());
测试结果：
3. 图的遍历
图的遍历思想：
图的遍历思想与树的遍历思想一样，意味着需要将图中所有的顶点都访问一遍，并且不能有重复的访问（上面的toString方法会重复访问）；
遍历图的两种算法：
广度优先搜索（Breadth - First Search，简称BFS）;深度优先搜索（Depth - First Search，简称DFS）;两种遍历算法都需要指定第一个被访问的顶点；
为了记录顶点是否被访问过，使用三种颜色来表示它们的状态
白色：表示该顶点还没有被访问过；灰色：表示该顶点被访问过，但其相邻顶点并未完全被访问过；黑色：表示该顶点被访问过，且其所有相邻顶点都被访问过；
首先封装initializeColor方法将图中的所有顶点初始化为白色，代码实现如下：
//四.初始化状态颜色Graph.prototype.initializeColor = function(){let colors = [];for (let i = 0; i < this.vertexes.length; i++) {colors[this.vertexes[i]] = 'white';}return colors;}
广度优先搜索
广度优先搜索算法的思路：
广度优先搜索算法会从指定的第一个顶点开始遍历图，先访问其所有的相邻顶点，就像一次访问图的一层；也可以说是先宽后深地遍历图中的各个顶点；
实现思路：
基于队列可以简单地实现广度优先搜索算法：
首先创建一个队列Q（尾部进，首部出）；调用封装的initializeColor方法将所有顶点初始化为白色；指定第一个顶点A，将A标注为灰色（被访问过的节点），并将A放入队列Q中；循环遍历队列中的元素，只要队列Q非空，就执行以下操作： 先将灰色的A从Q的首部取出；取出A后，将A的所有未被访问过（白色）的相邻顶点依次从队列Q的尾部加入队列，并变为灰色。以此保证，灰色的相邻顶点不重复加入队列；A的全部相邻节点加入Q后，A变为黑色，在下一次循环中被移除Q外。
代码实现：
//五.实现广度搜索(BFS)//传入指定的第一个顶点和处理结果的函数Graph.prototype.bfs = function(initV, handler){//1.初始化颜色let colors = this.initializeColor();//2.创建队列let que = new Queue();//3.将顶点加入到队列中que.enqueue(initV);//4.循环从队列中取出元素，队列为空才停止while(!que.isEmpty()){//4.1.从队列首部取出一个顶点let v = que.dequeue();//4.2.从字典对象edges中获取和该顶点相邻的其他顶点组成的数组let vNeighbours = this.edges.get(v);//4.3.将v的颜色变为灰色colors[v] = 'gray';//4.4.遍历v所有相邻的顶点vNeighbours,并且加入队列中for (let i = 0; i < vNeighbours.length; i++) {const a = vNeighbours[i];//判断相邻顶点是否被探测过，被探测过则不加入队列中；并且加入队列后变为灰色，表示被探测过if (colors[a] == 'white') {colors[a] = 'gray';que.enqueue(a);}}//4.5.处理顶点vhandler(v);//4.6.顶点v所有白色的相邻顶点都加入队列后，将顶点v设置为黑色。此时黑色顶点v位于队列最前面，进入下一次while循环时会被取出colors[v] = 'black';}}
过程详解：
下为指定的第一个顶点为A时的遍历过程：
如 a 图所示，将在字典edges中取出的与A相邻的且未被访问过的白色顶点B、C、D放入队列que中并变为灰色，随后将A变为黑色并移出队列；接着，如图 b 所示，将在字典edges中取出的与B相邻的且未被访问过的白色顶点E、F放入队列que中并变为灰色，随后将B变为黑色并移出队列； 如 c 图所示，将在字典edges中取出的与C相邻的且未被访问过的白色顶点G（A，D也相邻不过已变为灰色，所以不加入队列）放入队列que中并变为灰色，随后将C变为黑色并移出队列；接着，如图 d 所示，将在字典edges中取出的与D相邻的且未被访问过的白色顶点H放入队列que中并变为灰色，随后将D变为黑色并移出队列。
如此循环直到队列中元素为0，即所有顶点都变黑并移出队列后才停止，此时图中顶点已被全部遍历。
测试代码：
//测试代码//1.创建图结构let graph = new Graph();//2.添加顶点let myVertexes = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'];for (let i = 0; i < myVertexes.length; i++) {graph.addVertex(myVertexes[i]);}//3.添加边graph.addEdge('A', 'B');graph.addEdge('A', 'C');graph.addEdge('A', 'D');graph.addEdge('C', 'D');graph.addEdge('C', 'G');graph.addEdge('D', 'G');graph.addEdge('D', 'H');graph.addEdge('B', 'E');graph.addEdge('B', 'F');graph.addEdge('E', 'I');//4.测试bfs遍历方法let result = ""graph.bfs(graph.vertexes[0], function(v){result += v + "-";})console.log(result);
测试结果：
深度优先搜索
广度优先算法的思路：
深度优先搜索算法将会从指定的第一个顶点开始遍历图，沿着一条路径遍历直到该路径的最后一个顶点都被访问过为止；接着沿原来路径回退并探索下一条路径，即先深后宽地遍历图中的各个顶点。
实现思路：
可以使用栈结构来实现深度优先搜索算法；深度优先搜索算法的遍历顺序与二叉搜索树中的先序遍历较为相似，同样可以使用递归来实现（递归的本质就是函数栈的调用）。
基于递归实现深度优先搜索算法：定义dfs方法用于调用递归方法dfsVisit，定义dfsVisit方法用于递归访问图中的各个顶点。
在dfs方法中：
首先，调用initializeColor方法将所有顶点初始化为白色；然后，调用dfsVisit方法遍历图的顶点；
在dfsVisit方法中：
首先，将传入的指定节点v标注为灰色；接着，处理顶点v；然后，访问v的相邻顶点；最后，将顶点v标注为黑色。
代码实现：
//六.实现深度搜索(DFS)Graph.prototype.dfs = function(initV, handler){//1.初始化顶点颜色let colors = this.initializeColor();//2.从某个顶点开始依次递归访问this.dfsVisit(initV, colors, handler);}//为了方便递归调用，封装访问顶点的函数，传入三个参数分别表示：指定的第一个顶点、颜色、处理函数Graph.prototype.dfsVisit = function(v, colors, handler){//1.将颜色设置为灰色colors[v] = 'gray';//2.处理v顶点handler(v);//3.访问V的相邻顶点let vNeighbours = this.edges.get(v);for (let i = 0; i < vNeighbours.length; i++) {let a = vNeighbours[i];//判断相邻顶点是否为白色，若为白色，递归调用函数继续访问if (colors[a] == 'white') {this.dfsVisit(a, colors, handler);}}//4.将v设置为黑色colors[v] = 'black';}
过程详解：
这里主要解释一下代码中的第3步操作：访问指定顶点的相邻顶点。
以指定顶点A为例，先从储存顶点及其对应相邻顶点的字典对象edges中取出由顶点A的相邻顶点组成的数组：第一步：A顶点变为灰色，随后进入第一个for循环，遍历A白色的相邻顶点：B、C、D；在该for循环的第1次循环中（执行B），B顶点满足：colors == “white”，触发递归，重新调用该方法；第二步：B顶点变为灰色，随后进入第二个for循环，遍历B白色的相邻顶点：E、F；在该for循环的第1次循环中（执行E），E顶点满足：colors == “white”，触发递归，重新调用该方法；第三步：E顶点变为灰色，随后进入第三个for循环，遍历E白色的相邻顶点：I；在该for循环的第1次循环中（执行I），I顶点满足：colors == “white”，触发递归，重新调用该方法；第四步：I顶点变为灰色，随后进入第四个for循环，由于顶点I的相邻顶点E不满足：colors == “white”，停止递归调用。过程如下图所示：第五步：递归结束后一路向上返回，首先回到第三个for循环中继续执行其中的第2、3…次循环，每次循环的执行过程与上面的同理，直到递归再次结束后，再返回到第二个for循环中继续执行其中的第2、3…次循环…以此类推直到将图的所有顶点访问完为止。
下图为遍历图中各顶点的完整过程：
发现表示访问了该顶点，状态变为灰色；探索表示既访问了该顶点，也访问了该顶点的全部相邻顶点，状态变为黑色；由于在顶点变为灰色后就调用了处理函数handler，所以handler方法的输出顺序为发现顶点的顺序即：A、B、E、I、F、C、D、G、H 。
测试代码：
//测试代码//1.创建图结构let graph = new Graph();//2.添加顶点let myVertexes = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'];for (let i = 0; i < myVertexes.length; i++) {graph.addVertex(myVertexes[i]);}//3.添加边graph.addEdge('A', 'B');graph.addEdge('A', 'C');graph.addEdge('A', 'D');graph.addEdge('C', 'D');graph.addEdge('C', 'G');graph.addEdge('D', 'G');graph.addEdge('D', 'H');graph.addEdge('B', 'E');graph.addEdge('B', 'F');graph.addEdge('E', 'I');//4.测试dfs遍历顶点let result = "";graph.dfs(graph.vertexes[0], function(v){result += v + "-";})console.log(result);
测试结果：
完整实现
//封装图结构function Graph (){//属性：顶点(数组)/边(字典)this.vertexes = []; //顶点this.edges = new Dictionary(); //边//方法//添加方法//一.添加顶点Graph.prototype.addVertex = function(v){this.vertexes.push(v);this.edges.set(v, []); //将边添加到字典中，新增的顶点作为键，对应的值为一个存储边的空数组}//二.添加边Graph.prototype.addEdge = function(v1, v2){//传入两个顶点为它们添加边this.edges.get(v1).push(v2);//取出字典对象edges中存储边的数组，并添加关联顶点this.edges.get(v2).push(v1);//表示的是无向表，故要添加互相指向的两条边}//三.实现toString方法:转换为邻接表形式Graph.prototype.toString = function (){//1.定义字符串，保存最终结果let resultString = "";//2.遍历所有的顶点以及顶点对应的边for (let i = 0; i < this.vertexes.length; i++) {//遍历所有顶点resultString += this.vertexes[i] + '-->';let vEdges = this.edges.get(this.vertexes[i]);for (let j = 0; j < vEdges.length; j++) {//遍历字典中每个顶点对应的数组resultString += vEdges[j] + ' ';}resultString += '\n';}return resultString;}//四.初始化状态颜色Graph.prototype.initializeColor = function(){let colors = [];for (let i = 0; i < this.vertexes.length; i++) {colors[this.vertexes[i]] = 'white';}return colors;}//五.实现广度搜索(BFS)//传入指定的第一个顶点和处理结果的函数Graph.prototype.bfs = function(initV, handler){//1.初始化颜色let colors = this.initializeColor();//2.创建队列let que = new Queue();//3.将顶点加入到队列中que.enqueue(initV);//4.循环从队列中取出元素while(!que.isEmpty()){//4.1.从队列中取出一个顶点let v = que.dequeue();//4.2.获取和顶点相相邻的其他顶点let vNeighbours = this.edges.get(v);//4.3.将v的颜色变为灰色colors[v] = 'gray';//4.4.遍历v所有相邻的顶点vNeighbours,并且加入队列中for (let i = 0; i < vNeighbours.length; i++) {const a = vNeighbours[i];//判断相邻顶点是否被探测过，被探测过则不加入队列中；并且加入队列后变为灰色，表示被探测过if (colors[a] == 'white') {colors[a] = 'gray';que.enqueue(a);}}//4.5.处理顶点vhandler(v);//4.6.顶点v所有白色的相邻顶点都加入队列后，将顶点v设置为黑色。此时黑色顶点v位于队列最前面，进入下一次while循环时会被取出colors[v] = 'black';}}//六.实现深度搜索(DFS)Graph.prototype.dfs = function(initV, handler){//1.初始化顶点颜色let colors = this.initializeColor();//2.从某个顶点开始依次递归访问this.dfsVisit(initV, colors, handler);}//为了方便递归调用，封装访问顶点的函数，传入三个参数分别表示：指定的第一个顶点、颜色、处理函数Graph.prototype.dfsVisit = function(v, colors, handler){//1.将颜色设置为灰色colors[v] = 'gray';//2.处理v顶点handler(v);//3.访问v相连的其他顶点let vNeighbours = this.edges.get(v)for (let i = 0; i < vNeighbours.length; i++) {let a = vNeighbours[i];//判断相邻顶点是否为白色，若为白色，递归调用函数继续访问if (colors[a] == 'white') {this.dfsVisit(a, colors, handler);}}//4.将v设置为黑色colors[v] = 'black';}}
