blog
blog copied to clipboard
creeperyang
JavaScript与简单算法
请相信，题目着重简单，没有撒谎，这篇博文的所有算法相关的内容都是简单的。
作为一个早把《数据结构》还给老师的非专业选手，博主也正在努力学习算法。这篇文章以题目为组织形式，算是一个学习笔记吧。
排序（sort）
所谓排序，就是使一组记录按关键字递增(或递减)次序排列起来。
排序按策略可以分为五类：
-
插入排序(Insertion Sort)：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止。包括直接插入排序和希尔排序。
-
选择排序(Selection Sort)：每一趟从待排序的记录中选出关键字最小的记录，顺序放在已排好序的序列的最后，直到全部记录排序完毕。有直接选择排序和堆排序。
-
交换排序：两两比较待排序记录的关键字，发现两个记录的次序相反时即进行交换，直到没有反序的记录为止。有冒泡排序和快速排序。
-
归并排序(Merge Sort)：利用"归并"技术来进行排序。归并是指将若干个已排序的子文件合并成一个有序的文件。
-
分配排序：排序过程无须比较关键字，而是通过"分配"和"收集"过程来实现排序.它们的时间复杂度可达到线性阶：O(n)。
冒泡排序
冒泡排序是一种简单排序算法。它重复访问数组（最多n-1趟），每次比较相邻两个元素，顺序错误则交换，如果某趟没有任何交换，则证明数组已经有序。
冒泡排序时间复杂度：o(n^2)。 最好情况下，数组已经有序，只需要遍历一遍，o(n)；最坏情况下，需要o(n^2)。冒泡排序是 稳定 的。
function bubbleSort(array) {
var i, j, tmp, complete;
var len = array.length;
for (i = 0; i < len; i++) {
complete = true;
for (j = 1; j < len - i; j++) {
if (array[j - 1] > array[j]) {
tmp = array[j];
array[j] = array[j - 1];
array[j - 1] = tmp;
complete = false;
}
}
if (complete) break;
}
return array;
}
console.log(bubbleSort([4,3,2,1])); // [ 1, 2, 3, 4 ]
console.log(bubbleSort([10,5,6,8,7,9,4,3,1,2])); // [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
（直接）插入排序
插入排序把数组分为有序（开始为空）和无序两部分，遍历无序数组的每个元素，插入到有序数组的合适位置（也需要遍历有序数组）。
插入排序时间复杂度：o(n^2)。
function insertSort(array) {
var len = array.length;
var item, i, j, index;
for (i = 1; i < len; i++) {
for (j = 0; j < i; j++) {
if (array[j] > array[i]) {
item = array[i];
index = i;
while (index > j) {
array[index] = array[index - 1];
index--;
}
array[j] = item;
break;
}
}
}
return array;
}
选择排序
选择排序是简单排序算法。把数组分为有序（开始为空）和无序两部分，遍历无序数组选择最小值，插入到有序数组尾部。
选择排序时间复杂度：o(n^2)。 选择排序是 不稳定 的，如 [2, 2, 1] 的排序
function selectSort(array) {
var len = array.length;
var sortedLen = 0;
var minIndex, min, i;
while (sortedLen < array.length) {
min = array[sortedLen];
minIndex = sortedLen;
for (i = sortedLen + 1; i < len; i++) {
if (array[i] < min) {
min = array[i];
minIndex = i;
}
}
array[minIndex] = array[sortedLen];
array[sortedLen] = min;
sortedLen++;
}
return array;
}
归并排序
归并排序基于分治法（divide and conquer ）。归并排序首先把数组对半分，直到分成多个长度为1的原子数组（长度为1，必然有序），再把这些数组向上合并，保证每次合并后的数组都是有序的。
归并排序时间复杂度：o(n log n)。
function mergeSort(array) {
var len = array.length;
if (len === 1) return array;
var mid = ~~(len / 2);
var left = array.slice(0, mid);
var right = array.slice(mid);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right) {
var merged = [];
while (left.length && right.length) {
if (left[0] < right[0]) {
merged.push(left.shift());
} else {
merged.push(right.shift());
}
}
return left.length ? merged.concat(left) : merged.concat(right);
}
快速排序
快速排序是 C.R.A.Hoare 于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。
快速排序的步骤分为三步：
- 在数据集之中，选择一个元素作为 基准（pivot）。
- 所有小于 基准 的元素，都移到 基准 的左边；所有大于 基准 的元素，都移到 基准 的右边。这个操作称为分区 (partition) 操作，分区操作结束后，基准元素所处的位置就是最终排序后它的位置。
- 对 基准 左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。
快速排序时间复杂度是 O(nlgn)。 快速排序是 不稳定 的。
function quickSort(arr) {
if (!Array.isArray(arr)) {
throw new Error('arg should be array')
}
var len = arr.length
if (len <= 1) return arr
var pivot = arr[0]
var left = []
var right = []
for (var i = 1; i < len; i++) {
if (arr[i] < pivot) {
left.push(arr[i])
} else {
right.push(arr[i])
}
}
return quickSort(left).concat(pivot).concat(quickSort(right))
}
3. 数据结构
首先补一些概念：
-
数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成。
Data_Structure=(D,R)，其中D是数据元素的集合，R是该集合中所有元素之间的关系的有限集合。
数据结构具体指同一类数据元素中，各元素之间的相互关系，包括三个组成成分，数据的逻辑结构，数据的存储结构和数据运算结构。
-
数据的逻辑结构：指反映数据元素之间的逻辑关系的数据结构，其中的逻辑关系是指数据元素之间的前后件关系，与存储位置无关。
逻辑结构包括：
- 集合，数据结构中的元素之间除了“同属一个集合” 的相互关系外，别无其他关系
- 线性结构，数据结构中的元素存在一对一的相互关系
- 树形结构，数据结构中的元素存在一对多的相互关系
- 图形结构，数据结构中的元素存在多对多的相互关系
-
数据的物理结构：指数据的逻辑结构在计算机存储空间的存放形式。
数据的物理结构是数据结构在计算机中的表示（又称映像），它包括数据元素的机内表示和关系的机内表示。由于具体实现的方法有顺序、链接、索引、散列等多种，所以，一种数据结构可表示成一种或多种存储结构。
数据元素的机内表示（映像方法）： 用二进制位（bit）的位串表示数据元素。通常称这种位串为节点（node）。当数据元素有若干个数据项组成时，位串中与个数据项对应的子位串称为数据域（data field）。因此，节点是数据元素的机内表示（或机内映像）。
关系的机内表示（映像方法）：数据元素之间的关系的机内表示可以分为顺序映像和非顺序映像，常用两种存储结构：顺序存储结构和链式存储结构。顺序映像借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。非顺序映像借助指示元素存储位置的指针（pointer）来表示数据元素之间的逻辑关系。
3.1 栈
栈是只能在某一端插入和删除的特殊线性表。遵从后进先出（LIFO，Last In First Out）的原则。一般有以下方法：
- push(element): 添加元素到栈顶
- pop(): 移除并返回栈顶元素
- peek(): 返回栈顶元素
- isEmpty(): 检查栈是否为空，为空则返回true
- clear(): 移除栈中所有元素
- size(): 返回栈中元素个数
JavaScript实现
class Stack {
constructor(array) {
this.items = Array.isArray(array) ? array : []
}
push(el) {
this.items.push(el)
}
pop() {
return this.items.pop()
}
peek() {
return this.items[this.items.length - 1]
}
size() {
return this.items.length
}
clear() {
this.items = []
}
isEmpty() {
return this.items.length === 0
}
toString(connector) {
return this.items.join(connector == null ? ',' : connector)
}
}
事实上JS中数组具有pop/push等方法，已经可以完全表达栈的形式，以上代码也只是基于数组对封装。
应用
如何得到数字的二进制形式？(num.toString(2))
正整数转换成二进制就是不断除二取余，然后倒序排列，高位补零。
function convertDecimalToBinary(dec) {
dec = Number(dec)
if (Number.isNaN(dec)) return ''
const stack = new Stack()
let n
while(dec >= 2) {
n = dec % 2
stack.push(n)
dec = Math.floor(dec / 2)
}
stack.push(dec)
let binStr = ''
while (!stack.isEmpty()) {
binStr += stack.pop()
}
return binStr
}
console.log(convertDecimalToBinary(9)) // 1001
3.2 队列
一种特殊的线性表，它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列是按照“先进先出”或“后进后出”的原则组织数据的。
Array的push/shift方法对应队列的入队和出对，其实也不用有所谓的JS队列实现（还是贴在下面了）：
class Queue {
constructor() {
this.items = []
}
enqueue(el) {
this.items.push(el)
}
dequeue() {
return this.items.shift()
}
front() {
return this.items[0]
}
}
链表是一种物理存储单元上非连续、非顺序的存储结构，它既可以表示线性结构，也可以用于表示非线性结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。
3.3 链表
3.3.1 单向链表
链表的最简单形式是单向链表，它的每个节点包含2部分：数据＋指向下一节点的指针。最后一个节点指向NULL。
JavaScript实现
class Node {
constructor(element) {
this.element = element
this.next = null
}
}
class LinkedList {
constructor() {
this.head = null
this.length = 0
}
append(el) {
const node = new Node(el)
if (!this.head) {
this.head = node
} else {
let current = this.head
while (current.next) {
current = current.next
}
current.next = node
}
this.length++
}
insert(position, el) {
if (position < 0 || position >= this.length) {
return false
}
const node = new Node(el)
if (position === 0) {
node.next = this.head
this.head = node
} else {
let current = this.head
while (--position) {
current = current.next
}
node.next = current.next
current.next = node
}
this.length++
return true
}
indexOf(el) {
let current = this.head
let index = 0
while (current) {
if (el === current.element) return index
index++
current = current.next
}
return -1
}
remove(el) {
return this.removeAt(this.indexOf(el))
}
removeAt(position) {
if (position < 0 || position >= this.length) return false
let current = this.head
if (position === 0) {
this.head = current.next
} else {
let index = 0
let previous
while (index++ < position) {
previous = current
current = current.next
}
previous.next = current.next
}
current.next = null
this.length--
return true
}
getHead() {
return this.head
}
size() {
return this.length
}
isEmpty() {
return this.length === 0
}
toString() {
let res = ''
let current = this.head
while (current) {
res += current.element
current = current.next
}
return res
}
}
3.3.2 双向链表
双向链表相比单项链表，每个节点多一个指针指向前一节点。
JavaScript实现
class Node {
constructor(element) {
this.element = element
this.previous = null
this.next = null
}
}
class DoublyLinkedList {
constructor() {
this.head = null
this.tail = null
this.length = 0
}
append(el) {
const node = new Node(el)
if (this.head == null) {
this.tail = this.head = node
} else {
this.tail.next = node
node.previous = this.tail
this.tail = node
}
this.length++
}
insert(index, el) {
const node = this.getNode(index)
if (!node) return false
const newNode = new Node(el)
const previous = node.previous
if (previous) {
previous.next = newNode
newNode.previous = previous
} else {
this.head = newNode
}
newNode.next = node
node.previous = newNode
this.length++
return true
}
remove(el) {
return this.removeAt(this.indexOf(el))
}
removeAt(index) {
const node = this.getNode(index)
if (!node) return false
const previous = node.previous
if (previous) {
previous.next = node.next
} else {
this.head = node.next
}
node.previous = node.next = null
this.length--
return true
}
indexOf(el) {
let index = 0
let current = this.head
while (index < this.length) {
if (current.element === el) {
return index
}
current = current.next
index++
}
return -1
}
getNode(index) {
if (index < 0 || index >= this.length) {
return null
} else if (index === 0) {
return this.head
} else if (index === this.length - 1) {
return this.tail
} else {
let current = this.head.next
let start = 1
while (start++ < index) {
current = current.next
}
return current
}
}
size() {
return this.length
}
toString(connector = ',') {
let res = ''
let current = this.head
while (current) {
res += current.element + connector
current = current.next
}
return res.slice(0, -1)
}
}
3.5 集合
由一个或多个元素所构成的叫做集合(Set)。若x是集合A的元素，则记作x∈A。集合中的元素有三个特征：1.确定性（集合中的元素必须是确定的） 2.互异性（集合中的元素互不相同。例如：集合A={1，a}，则a不能等于1） 3.无序性（集合中的元素没有先后之分。）
ES6已经有Set了，想了解的可以参考ECMAScript 6 入门：Set
但基于理解Set特性，这里仍旧给出Set的一个实现：
const getName = Symbol('getName')
class Set {
constructor(array) {
this.map = {}
if (Array.isArray(array)) {
array.forEach(v => this.map[this[getName](v)] = v)
}
}
[getName](value) {
return Object.prototype.toString.call(value) + value
}
has(value, name) {
return this.map.hasOwnProperty(name || this[getName](value))
}
add(value) {
const name = this[getName](value)
if (this.has(value, name)) {
return false
}
this.map[name] = value
return true
}
delete(value) {
const name = this[getName](value)
if (this.has(value, name)) {
delete this.map[name]
return true
}
return false
}
values() {
return Object.keys(this.map).map(key => this.map[key])[Symbol.iterator]()
}
entries() {
return Object.keys(this.map).map(key => [this.map[key], this.map[key]])[Symbol.iterator]()
}
size() {
return Object.keys(this.map).length
}
clear() {
this.map = {}
}
}
Set.prototype[Symbol.iterator] = Set.prototype.keys = Set.prototype.values
// 并集
Set.union = function(set1, set2) {
if (Array.isArray(set1)) set1 = new Set(set1)
if (Array.isArray(set2)) set2 = new Set(set2)
const res = new Set()
if (set1 instanceof Set && set2 instanceof Set) {
for (let item of set1) {
res.add(item)
}
for (let item of set2) {
res.add(item)
}
}
return res
}
// 交集
Set.intersect = function(set1, set2) {
if (Array.isArray(set1)) set1 = new Set(set1)
if (Array.isArray(set2)) set2 = new Set(set2)
const res = new Set()
if (set1 instanceof Set && set2 instanceof Set) {
for (let item of set1) {
if (set2.has(item)) {
res.add(item)
}
}
}
return res
}
// 差集
Set.diff = function(set1, set2) {
if (Array.isArray(set1)) set1 = new Set(set1)
if (Array.isArray(set2)) set2 = new Set(set2)
const res = new Set()
if (set1 instanceof Set && set2 instanceof Set) {
const intersection = Set.intersect(set1, set2)
for (let item of set1) {
if (!intersection.has(item)) {
res.add(item)
}
}
for (let item of set2) {
if (!intersection.has(item)) {
res.add(item)
}
}
}
return res
}
3.6 树
树(Tree）是n（n>=0)个结点的有限集。n=0时称为空树。在任意一棵非空树中：
- 有且仅有一个特定的称为根（root）的结点。
- 当n>1时，其余结点可分为m（m>0)个互不相交的有限集T1,T2,....,Tm, 其中每一个集合本身又是一棵树，并且称为根的子树（SubTree)。
若将树中每个结点的各子树看成是从左到右有次序的(即不能互换)，则称该树为有序树(OrderedTree)；否则称为无序树(UnorderedTree)。注意：若不特别指明，一般讨论的树都是有序树。
术语：
- 节点的度：一个节点含有的子树的个数称为该节点的度；
- 叶节点或终端节点：度为0的节点称为叶节点；
- 非终端节点或分支节点：度不为0的节点；
- 双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；
- 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；
- 兄弟节点：具有相同父节点的节点互称为兄弟节点；
- 树的度：一棵树中，最大的节点的度称为树的度；
- 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
- 树的高度或深度：树中节点的最大层次；
- 堂兄弟节点：双亲在同一层的节点互为堂兄弟；
- 节点的祖先：从根到该节点所经分支上的所有节点；
- 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。
- 森林：由m（m>=0）棵互不相交的树的集合称为森林；
3.7 二叉树
1. 二叉树的定义：二叉树的每个节点至多只有二棵子树(不存在度大于2的节点)，二叉树的子树有左右之分，次序不能颠倒。
二叉树的第i层至多有2^(i-1)个节点；深度为k的二叉树至多有2^k-1个节点；对任何一棵二叉树T，如果其终端节点数为n0，度为2的节点数为n2，则n0=n2+1。
二叉树的存储结构
-
顺序存储结构
用一组连续的存储单元依次自上而下，自左至右存储完全二叉树上的结点元素，即将二叉树上编号为i的结点元素存储在加上定义的一维数组中下标为i-1的分量中。“0”表示不存在此结点。这种顺序存储结构仅适用于完全二叉树。因为，在最坏情况下，一个深度为k且只有k个结点的单支树（树中不存在度为2的结点）却需要长度为2的n次方-1的一维数组。
顺序：
[1, 2, 3, 4, 5, , 6, , , 7] -
链式存储结构
二叉树的结点由一个数据元素和分别指向其左右子树的两个分支构成，则表示二叉树的链表中的结点至少包含三个域：数据域和左右指针域。有时，为了便于找到结点的双亲，还可在结点结构中增加一个指向其双亲结点的指针域。利用这两种结构所得的二叉树的存储结构分别称之为二叉链表和三叉链表。 在含有n个结点的二叉链表中有n+1个空链域，我们可以利用这些空链域存储其他有用信息，从而得到另一种链式存储结构---线索链表。
链式：
{ data, left, right}
2. 满二叉树：除最后一层无任何子节点外，每一层上的所有结点都有两个子结点。也可以这样理解，除叶子结点外的所有结点均有两个子结点。节点数达到最大值，所有叶子结点必须在同一层上。
满二叉树的性质：
- 一颗树深度为h，最大层数为k，深度与最大层数相同，k=h;
- 叶子数为2^h;
- 第k层的结点数是：2^(k-1);
- 总结点数是：2^(k-1)，且总节点数一定是奇数。
3. 完全二叉树：若设二叉树的深度为h，除第 h 层外，其它各层 (1～(h-1)层) 的结点数都达到最大个数，第h层所有的结点都连续集中在最左边，这就是完全二叉树。
4. 二叉查找树
二叉查找树（英语：Binary Search Tree），也称二叉搜索树、有序二叉树（英语：ordered binary tree），排序二叉树（英语：sorted binary tree），是指一棵空树或者具有下列性质的二叉树：
- 任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
- 任意节点的左、右子树也分别为二叉查找树；
- 没有键值相等的节点。
二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低。为 O(log n) 。二叉查找树是基础性数据结构，用于构建更为抽象的数据结构，如集合、multiset、关联数组等。
上面一段基本是在介绍树相关的概念，接下来配合概念用JS代码实现树的相关操作。
参考：
- http://www.html-js.com/article/2761
- https://github.com/HelloLeeChan/CS-in-JavaScript-by-nzakes/blob/master/%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91,%20Part1.md
- http://xdimh.github.io/2014/09/14/Data-Structure-BST-with-javascript/
3.6.1 二叉树与先序/中序/后序遍历
遍历二叉树(Traversing Binary Tree)：是指按指定的规律对二叉树中的每个结点访问一次且仅访问一次。 二叉树的遍历主要分三种：
- 先（根）序遍历：根左右
- 中（根）序遍历：左根右
- 后（根）序遍历：左右根
class BinaryTree {
static from(array) {
const root = new BinaryTree()
if (array == null || !Array.isArray(array)) {
root.level = 1
root.data = array
return root
}
preOrderTraverse(root, 0, function (node, value, level) {
node.data = value
node.level = level
}, 1)
return root
function preOrderTraverse(node, index, visit, level) {
visit(node, array[index], level)
if (array[2 * index + 1] != null) {
preOrderTraverse(node.left = new BinaryTree(), 2 * index + 1, visit, node.level + 1)
}
if (array[2 * index + 2] != null) {
preOrderTraverse(node.right = new BinaryTree(), 2 * index + 2, visit, node.level + 1)
}
}
}
constructor(data, left, right) {
this.data = data
this.left = left
this.right = right
}
toString() {
return this.toLevelArray().join()
}
toLevelArray() {
const array = []
this.preOrderTraverse((v, level) => {
array[level - 1] ? array[level - 1].push(v) : (array[level - 1] = [v])
})
return array
}
getDepth() {
let level = 0
this.preOrderTraverse((v, l) => {
if (l > level) {
level = l
}
})
return level
}
/**
* 链式存储结构的递归先序遍历 (根左右)
*
* 若二叉树为空，则遍历结束；否则
* ⑴ 访问根结点；
* ⑵ 先序遍历左子树(递归调用本算法)；
* ⑶ 先序遍历右子树(递归调用本算法)。
*/
preOrderTraverse(visit) {
visit(this.data, this.level, this)
if (this.left) this.left.preOrderTraverse(visit)
if (this.right) this.right.preOrderTraverse(visit)
}
/**
* 链式存储结构的 **非递归** 先序遍历
*/
preOrderTraverseNR(visit) {
const stack = []
stack.push(this)
while (stack[0]) {
let p
// 向左走到尽头
while ((p = stack[stack.length - 1])) {
(p.data != null) && visit(p.data, p.level, p)
stack.push(p.left)
}
// 删掉空节点
stack.pop()
// 删掉根节点，进栈右节点
if (stack[0]) {
p = stack.pop()
stack.push(p.right)
}
}
}
/**
* 递归中序遍历 (左根右)
*
* 若二叉树为空，则遍历结束；否则
* ⑴ 中序遍历左子树(递归调用本算法)；
* ⑵ 访问根结点；
* ⑶ 中序遍历右子树(递归调用本算法)。
*/
inOrderTraverse(visit) {
if (this.left) this.left.inOrderTraverse(visit)
visit(this.data, this.level, this)
if (this.right) this.right.inOrderTraverse(visit)
}
/**
* **非递归** 中序遍历
*/
inOrderTraverseNR(visit) {
const stack = []
stack.push(this)
while (stack[0]) {
let p
// 向左走到尽头
while ((p = stack[stack.length - 1])) {
stack.push(p.left)
}
// 删除空节点
stack.pop()
// 删掉根节点，进栈右节点
if (stack[0]) {
p = stack.pop()
;(p.data != null) && visit(p.data, p.level, p)
stack.push(p.right)
}
}
}
/**
* 递归后序遍历 (左右根)
*
* 若二叉树为空，则遍历结束；否则
* ⑴ 后序遍历左子树(递归调用本算法)；
* ⑵ 后序遍历右子树(递归调用本算法) ；
* ⑶ 访问根结点 。
*/
postOrderTraverse(visit) {
if (this.left) this.left.postOrderTraverse(visit)
if (this.right) this.right.postOrderTraverse(visit)
visit(this.data, this.level, this)
}
/**
* 非递归后序遍历
*
* (1) 根结点入栈，且mark = 0;
* (2) 若栈不为空，出栈到node；
* (3) 若node的mark = 0，修改当前node的mark为1，左子树入栈；
* (4) 若node的mark = 1，修改当前node的mark为2，右子树入栈；
* (5) 若node的mark = 2，访问当前node结点的值；
* (6) 直到栈为空结束。
*/
postOrderTraverseNR(visit) {
const stack = []
stack.push([this, 0])
while (stack[0]) {
let p = stack.pop()
let node = p[0]
switch (p[1]) {
case 0:
stack.push([node, 1])
if (node.left) {
stack.push([node.left, 0])
}
break
case 1:
stack.push([node, 2])
if (node.right) {
stack.push([node.right, 0])
}
break
case 2:
(node.data != null) && visit(node.data, node.level, node)
break
default:
break
}
}
}
}
// const tree = BinaryTree.from([0, 1, 2, 3, 4, 5, 6, null, 8, 9])
// tree.preOrderTraverse(v => console.log(v))
3.6.2二叉搜索树
class BinarySearchTree extends BinaryTree {
static from(array) {
const root = new BinarySearchTree()
root.level = 1
if (Array.isArray(array)) {
array.forEach(key => root.insert(key))
} else {
root.data = array
}
return root
}
constructor(data, left, right) {
super(data, left, right)
}
search(key) {
if (this.data == null) return null
if (key === this.data) {
return this
} else if (key < this.data) {
return this.left ? this.left.search(key) : null
} else {
return this.right ? this.right.search(key) : null
}
}
/**
* 在BST树中插入一个新结点x时，若BST树为空，则令新结点x为插入后BST树的根结点；
* 否则，将结点x的关键字与根结点T的关键字进行比较：
* ① 若相等：不需要插入；
* ② 若x.data < T.data：结点x插入到T的左子树中；
* ③ 若x.data > T.data：结点x插入到T的右子树中。
*/
insert(key) {
if (this.data == null) {
this.data = key
this.level = 1
return
} else if (key === this.data) {
return
}
const node = new BinarySearchTree(key)
if (key < this.data) {
if (!this.left) {
this.left = node
node.level = this.level + 1
} else {
this.left.insert(key)
}
} else {
if (!this.right) {
this.right = node
node.level = this.level + 1
} else {
this.right.insert(key)
}
}
}
/**
* 使用递归的方法删除与关键字符合的结点
* @param {*} key 需要查找的关键字
* @param {BSTNode} parent 父节点，内部调用需要用到
* @returns {Boolean}
*/
remove(key, parent) {
// 空结点的情况
if (this.data == null) return false
// 找到关键字
if (this.data === key) return deleteNode(this, parent)
// 查找左子树，如果有的话
else if (key < this.data) {
if (this.left) return this.left.remove(key, this)
}
// 查找右子树，如果有的话
else {
if (this.right) return this.right.remove(key, this)
}
// 未找到
return false
}
}
/**
* 从BST树上删除一个结点，仍然要保证删除后满足BST的性质。设被删除结点为p，其父结点为f，删除情况如下：
* ① 若p是叶子结点： 直接删除p。
* ② 若p只有一棵子树(左子树或右子树)：直接用p的左子树(或右子树)取代p的位置而成为f的一棵子树。
* 即原来p是f的左子树，则p的子树成为f的左子树；原来p是f的右子树，则p的子树成为f的右子树。
* ③ 若p既有左子树又有右子树 ：处理方法有以下两种，可以任选其中一种。
* ◆ 用p的直接前驱结点代替p。即从p的左子树中选择值最大的结点s放在p的位置(用结点s的内容替换结点p内容)，然后删除结点s。
* s是p的左子树中的最右边的结点且没有右子树，对s的删除同②。
* ◆ 用p的直接后继结点代替p。即从p的右子树中选择值最小的结点s放在p的位置(用结点s的内容替换结点p内容)，然后删除结点s。
* s是p的右子树中的最左边的结点且没有左子树，对s的删除同②。
*/
function deleteNode(p, parent) {
// 叶子结点或只有一个结点
if (!p.left && !p.right) {
// 当前结点是其父结点的左子树还是右子树
let pos = parent && parent.left === p ? 'left' : 'right'
if (parent) parent[pos] = null
// 只有一个结点的情况
else {
p.data = null
}
}
// 只有左子树
else if (!p.right) {
p.data = p.left.data
p.left = p.left.left
p.left && p.left.preOrderTraverse((v, l, node) => {
node.level--
})
}
// 只有右子树
else if (!p.left) {
p.data = p.right.data
p.right = p.right.right
p.right && p.right.preOrderTraverse((v, l, node) => {
node.level--
})
}
// 左右子树都有
else {
let sub = p.left
// q为父结点
let sup = p
// 找到左子树的最大右子树，即仅小于左子树的值的结点
while (sub.right) {
sup = sub
sub = sub.right
}
// 复制左子树最大节点sub的值到p
p.data = sub.data
// 删除左子树最大节点sub
if (sup != p) {
sup.right = sub.left // sub可能有左子树
}
else {
sup.left = sub.left
}
sub.left && sub.left.preOrderTraverse((v, l, node) => {
node.level--
})
}
return true
}
const bst = BinarySearchTree.from([5, 2, 6, 1, 3, 4, 8, 7, 9])
console.log(bst.toLevelArray())
bst.remove(5)
console.log(bst.toLevelArray())
bst.remove(9)
console.log(bst.toLevelArray())
bst.insert(5)
console.log(bst.toLevelArray())
console.log(bst.search(5))
我看了你今天在知乎发的招聘信息，你看看我能去不？工资随便开。不给也可以，实在不想一个人脱产自学啦，想尽早加入一个团队，找到组织。那些新技术、新框架rxjs，http2，typescript，react native，ionic等等都想学啊。先稍微自我介绍一下，92年，自动化专业，15年毕业，热爱google，电脑基础常识还是必须有的，今年五月份才开始学前端的，基本上会的东西都在github里。 --ps：https://www.cform.io/ 这个单页应用也很复杂
大神，选择排序是不稳定的，是什么意思？
选择排序时间复杂度：o(n^2)。 选择排序是 不稳定 的，如 [2, 2, 1] 的排序
我运行了一下：
selectSort([2, 2, 1, 3, 3, 1]) // => [1, 1, 2, 2, 3, 3]
效果上看是正确的啊
@caiyongmin 按一般的实现方式，直接在数组里交换的话，选择排序是不稳定的。
如下：
假设 [A, B, C] ---> [2, 2, 1] ，即 （A=B=2, C=1）;
第一趟比较完成后：
[C, B, A] ---> [1, 2, 2]
所以说不稳定。