共计 6989 个字符，预计需要花费 18 分钟才能阅读完成。
汇合
成一个既没有反复元素，也没有程序概念的数组。用对象 {} 示意。
function Set(){var items={};
// 向汇合增加一个新的项。true，示意增加了这个值。如果汇合中曾经有这个值，就返回 false，示意没有增加它。this.add=function(value){if(!this.has(value)){items[value]=value;
return true;
}
return false;
}
// 从汇合移除一个值。this.remove=function(value){if(items[value]){delete items[value];
return true;
}
return false;
}
// 如果值在汇合中，返回 true，否则返回 false。this.has=function(value){return return items.hasOwnProperty(value);
}
// 移除汇合中的所有项。this.clear=function(){items={};
}
// 返回汇合所蕴含元素的数量。与数组的 length 属性相似。this.size=function(){return Object.keys(items).length;
}
// 返回一个蕴含汇合中所有值的数组。this.values=function(){return Object.keys(items);
}
}并集
对于给定的两个汇合，返回一个蕴含两个汇合中所有元素的新汇合。Object.assign(),2 个都要;
并集的数学概念，汇合 A 和B的并集，示意为 A∪B，定义如下：A∪B = {x | x ∈ A∨x ∈ B}
意思是 x（元素）存在于A 中，或 x 存在于 B 中。
当初来实现 Set 类的 union 办法：
this.union = function(otherSet){var unionSet = new Set();
var values = this.values();
for (var i=0; i<values.length; i++){unionSet.add(values[i]);
}
values = otherSet.values();
for (var i=0; i<values.length; i++){unionSet.add(values[i]);
}
return unionSet;
}; 测试一下下面的代码：
var setA = new Set();
setA.add(1);
setA.add(2);
setA.add(3);
var setB = new Set();
setB.add(3);
setB.add(4);
setB.add(5);
setB.add(6);
var unionAB = setA.union(setB);
console.log(unionAB.values());输入为 ["1", "2", "3", "4", "5", "6"]。留神元素3 同时存在于 A 和B中，它在后果的汇合中只呈现一次。
交加
对于给定的两个汇合，返回一个蕴含两个汇合中共有元素的新汇合。只有同时领有的。
交加的数学概念，汇合 A 和B的交加，示意为 A∩B，定义如下：A∩B = {x | x ∈ A∧x ∈ B}
意思是 x（元素）存在于A 中，且 x 存在于 B 中。
当初来实现 Set 类的 intersection 办法：
this.intersection = function(otherSet){var intersectionSet = new Set(); // 同时都蕴含的
var values = this.values();
for (var i=0; i<values.length; i++){if (otherSet.has(values[i])){intersectionSet.add(values[i]);
}
}
return intersectionSet;
} 差集
对于给定的两个汇合，返回一个蕴含所有存在于第一个汇合且不存在于第二个集
合的元素的新汇合。只有跟其它不雷同的。
差集的数学概念，汇合 A 和B的差集，示意为 A-B，定义如下：A-B = {x | x ∈ A ∧ x B}
意思是 x（元素）存在于A 中，且 x 不存在于 B 中。
当初来实现 Set 类的 difference 办法：
this.difference = function(otherSet){var differenceSet = new Set();// 存在 A 不存在 B, 同样数据 a.length>b.length 才会有值，[1,2,3,4]-[1,2,3]=4;
var values = this.values();
for (var i=0; i<values.length; i++){if (!otherSet.has(values[i])){differenceSet.add(values[i]);
}
}
return differenceSet;
};子集
验证一个给定汇合是否是另一汇合的子集。判断子集中肯定都是父集中的。
子集的数学概念，汇合 A 是B的子集（或汇合 B 蕴含
了A），示意为 A⊆B，定义如下：∀x {x ∈ A → x ∈ B}
意思是汇合 A 中的每一个 x（元素），也须要存在于B 中。
当初来实现 Set 类的 subset 办法：
this.subset = function(otherSet){if (this.size() > otherSet.size()){return false;} else {var values = this.values();
for (var i=0; i<values.length; i++){if (!otherSet.has(values[i])){return false;}
}
return true;
}
}; 字典
汇合、字典和散列表能够存储不反复的值。在字典中，存储的是 [键，值]
对，其中键名是用来查问特定元素的。字典也称作映射。
function Dictionary(){var items={};
this.set=function(key,value){items[key]=value;
}
this.remove=function(key){if(this.has(key)){delete items[key];
return true;
}
return false;
}
this.has=function(key){return key in items;}
this.get=function(key){return this.has(key)?items[key]:undefined;
}
this.clear=function(){items={};
}
this.size=function(){return Object.keys(items).length;
}
this.keys=function(){return Object.keys(items);
}
this.values=function(){let values=[];
for(let key in items){if(this.has(key)){values.push(items[key])
}
}
return values;
}
this.getItems = function() {return items;}
}散列表
HashTable类，也叫 HashMap 类，是 Dictionary 类的一种散列表实
现形式。应用数组形式。
散列算法的作用是尽可能快地在数据结构中找到一个值。道如果
要在数据结构中取得一个值（应用 get 办法），须要遍历整个数据结构来找到它。如果应用散列
函数，就晓得值的具体位置，因而可能疾速检索到该值。散列函数的作用是给定一个键值，而后返回值在表中的地址。
先实现一个散列函数是 HashTable 类的公有办法，取得将每个键值中的每个字母的 ASCII 值和一个数字。
let loseloseHashCode=function(key){
let hash=5381;
for(let i=0;i<key.length;i++){hase=hash*33+key.charCodeAt(i);
}
return hash%1013;//1013 是任意的质数, 让值不要那么大
}`function HashTable(){
let table=[];
this.put=function(key,value){let position=loseloseHashCode(key);
table[position]=value;
}
this.remove=function(key){table[loseloseHashCode(key)]=undefined;
}
this.get=function(key){return table[loseloseHashCode(key)]
}}`
树
非程序数据结构——树，它对于存储须要疾速查找的数据十分有用。
一个树结构蕴含一系列存在父子关系的节点。每个节点都有一个父节点（除了顶部的第一个
节点）以及零个或多个子节点：
位于树顶部的节点叫作根节点（11）。它没有父节点。树中的每个元素都叫作节点，节点分
为外部节点和内部节点。至多有一个子节点的节点称为外部节点（7、5、9、15、13 和 20 是外部
节点）。没有子元素的节点称为内部节点或叶节点（3、6、8、10、12、14、18 和 25 是叶节点）。
一个节点能够有先人和后辈。一个节点（除了根节点）的先人包含父节点、祖父节点、曾祖
父节点等。一个节点的后辈包含子节点、孙子节点、曾孙节点等。例如，节点 5 的先人有节点 7
和节点 11，后辈有节点 3 和节点 6
二叉树
二叉树中的节点最多只能有两个子节点：一个是左侧子节点，另一个是右侧子节点。这些定
义有助于咱们写出更高效的向 / 从树中插入、查找和删除节点的算法。二叉树在计算机科学中的
利用十分宽泛。
二叉搜寻树（BST）是二叉树的一种，然而它只容许你在左侧节点存储（比父节点）小的值，
在右侧节点存储（比父节点）大（或者等于）的值。;
let insertNode=function(node,newNode){
// 小了就在右边上级有了就找下上级，左边同理
if(newNode.key<node.key){if(node.left===null){node.left=newNode;}else{insertNode(node.left,newNode)
}
}else{if(node.right===null){node.right=newNode;}else{insertNode(node.right,newNode);
}
}
}function BinarySearchTree(){let Node=function(key){
this.key=key;
this.left=null;
this.right=null;
}
let root=null;
this.insert=function(key){let newNode=new Node(key);
if(root===null){root=newNode;}else{insertNode(root,newNode);
}
}
this.search=function(key){ }
this.inOrderTraverse=function(callback){}
this.preOrderTraverse=function(){}
this.postOrderTraverse=function(){}
this.min=function(){}
this.max=function(){}
this.remove=function(key){}}中序遍历
中序遍历是一种以上行程序拜访 BST 所有节点的遍历形式，也就是以从最小到最大的程序访
问所有节点。中序遍历的一种利用就是对树进行排序操作。
首先要查看以参数模式传入的节点是否为 null（这就
是进行递归继续执行的判断条件——递归算法的根本条件）。
而后，递归调用雷同的函数来拜访左侧子节点。接着对这个节点进行一些操作
（callback），而后再拜访右侧子节点
this.inOrderTraverse=function(callback){inOrderTraverse(root,callback);
}let inOrderTraverseNode=function(node,callback){if(node!==null){inOrderTraverseNode(node.left,callback);
callback(node.key);
inOrderTraverseNode(node.right,callback);
}
}inOrderTraverse办法的拜访门路：
先序遍历
先序遍历是以优先于后辈节点的程序拜访每个节点的。先序遍历的一种利用是打印一个构造
化的文档。
先序遍历和中序遍历的不同点是，先序遍历会先拜访节点自身，而后再拜访它的
左侧子节点，最初是右侧子节点。
this.preOrderTraverse=function(callback){preOrderTraverseNode(root,callback)
}let preOrderTraverseNode=function(node,callback){if(node!==null){callback(node.key);
preOrderTraverseNode(node.left,callback);
preOrderTraverseNode(node.right,callbak);
}
}preOrderTraverse办法的拜访门路：
后序遍历
后序遍历则是先拜访节点的后辈节点，再拜访节点自身。后序遍历的一种利用是计算一个目
录和它的子目录中所有文件所占空间的大小。
后序遍历会先拜访左侧子节点，而后是右侧子节点，最初
是父节点自身
this.postOrderTraverse=function(callback){postOrderTraverseNode(root,callback);
}let postOrderTraverseNode=function(node,callback){if(node!==null){postOrderTraverseNode(node.left,callback);
postOrderTraverseNode(node.right,callback);
callback(node.key);
}
}postOrderTraverse办法的拜访门路：
搜寻最大最小值
小的在右边，大的在左边
this.min=function(){return minNode(root);
}
let minNode=function(node){if(node){while(node&&node.left!==null){node=node.left;}
return node.key;
}
return null;
}this.max=function(){return maxNode(root);
}
let maxNode=function(node){if(node){while(node&&node.right!==null){node=node.right;}
return node.key;
}
return null;
}搜寻特定值
返回 boolean;
this.search=function(key){return searchNode(root,key);
}
let searchNode=function(node,key){if(node===null){return false;}
if(key<node.key){return searchNode(node.left,key);
}else if(key>node.key){return searchNode(node.right,key);
}else{return true;}
}移除一个节点
this.remove=function(key){root=removeNode(root,key);
}
let removeNode=function(node,key){if(node===null){return null;}
if(key<node.key){node.left=removeNode(node.left,key);
}else if(key>node.key){node.right=removeNode(node.right,key);
return node;
}else{// 键 =node.key
// 第一种状况，一个叶节点
if(node.left===null&&node.right===null){
node=null;
return node;
}
// 第二种状况，一个只有一个子节点的节点
if(node.left==null){
node=node.right;
return node;
}else if(node.right===null){
node=node.left;
return node;
}
// 第三种状况，一个有 2 个子节点的节点
let aux=findMinNode(node.right);
node.key=aux.key;
node.right=removeNode(node.right,aux.key);
return node;
}
}
