数据结构与算法
数据结构和算法有什么关系？
可以容纳数据的结构被称为数据结构 算法是用来对数据结构进行处理的方法 数据结构是静态的。 算法是动态的
一维数据结构：
(线性数据结构：数组、链表)
线性的数据结构强调存储与顺序
数组：
数组特性：
1.存储在物理空间上是连续的。
2. 底层的数据长度是不可变的。
数组优点： 查询性能好。指定查询某个位置
数组a = {1, 2, 3, 4, 5, 6, 7 ,8}
a[1], a[2], a[3] 方括号表示存储地址的偏移
操作系统小知识： 通过偏移查询数据性能最好。
数组缺点：
因为空间必须是连续的，所以如果数组比较大，当系统的空间碎片较多的时候，容易存不下
因为数组的长度是固定的，所以数组的内容难以被添加和删除。
链表
我想传递一个链表，我必须传递链表的根节点
每一个节点，都认为自己是根节点
链表的特点：
空间上不上连续的。 每存放一个值，都要多开销一个引用空间
优点：
只要内存足够大，就能存的下，不用担心空间碎片的问题
链表的添加和删除非常的容易
缺点：
查询速度慢（指的查询某个位置）
链表每一个节点都需要创建一个指向next的引用，浪费一些空间
线性数据结构的遍历
遍历： 将一个集合中每一个元素进行获取并查看
// 数组遍历 var arr = [1, 2, 3, 4, 5, 6, 7] function bianArr(arr) { // 算法必须有严谨性判断，否则没分 if (arr == null) return; for (var i = 0; i < arr.length; i++) { console.log(arr[i]) } } // bianArr(arr)
// 链表遍历 function Node(value) { this.value = value this.next = null } var node1 = new Node(1) var node2 = new Node(2) var node3 = new Node(3) var node4 = new Node(4) var node5 = new Node(5)
node1.next = node2 node2.next = node3 node3.next = node4 node4.next = node5 function bianLink(root) { var temp = root while (true) { if (temp != null) { console.log(temp.value) } else { break; } temp = temp.next } } bianLink(node1)
线性数据结构的递归遍历
// 数组递归遍历 var arr = [1, 2, 3, 4, 5, 6, 7] function bianArr(arr, i) { // 算法必须有严谨性判断，否则没分 if (arr == null || arr.length <= i) return; console.log(arr[i]) bianArr(arr, i + 1) } bianArr(arr, 0)
// 链表递归遍历 function Node(value) { this.value = value this.next = null } var node1 = new Node(1) var node2 = new Node(2) var node3 = new Node(3) var node4 = new Node(4) var node5 = new Node(5) node1.next = node2 node2.next = node3 node3.next = node4 node4.next = node5 // 递归遍历，先找出口，就是return值，后递归 function bianLink(root) { // 找出口 if (root == null) return; console.log(root.value) //递归 bianLink(root.next) } bianLink(node1)
链表的逆置
function Node(value) { this.value = value this.next = null } var node1 = new Node(1) var node2 = new Node(2) var node3 = new Node(3) var node4 = new Node(4) var node5 = new Node(5) node1.next = node2 node2.next = node3 node3.next = node4 node4.next = node5 // 链表的逆置 关键点找到最后一个元素 function nizhi(root) { // 出口,找到最后一个节点为null if (root.next.next == null) { //代表当前节点是倒数第二个节点 root.next.next = root //让最后一个节点指向自己（倒数第二个节点） return root.next } else { // 递归 let result = nizhi(root.next) root.next.next = root // 把第一个节点指向null root.next = null return result } } let newRoot = nizhi(node1) function bianLink(root) { if (root == null) return; console.log(root.value) bianLink(root.next) } bianLink(newRoot)
经典算法
冒泡排序
var arr = [4, 1, 5, 8, 3, 2, 6, 7]; function buddleSort(arr) { if (arr == null || arr.length == 0) return; for (let i = 0; i < arr.length; i++) { for (let j = 0; j < arr.length - 1 - i; j++) { if (compare(arr[j], arr[j + 1])) { swap(arr, j, j + 1) } } } } buddleSort(arr) console.log(arr) //[ 1, 2, 3, 4, 5, 6, 7, 8 ] function compare(a, b) { if (a > b) return true//大于正序 小于降序 else false } function swap(arr, a, b) { let temp = arr[a] arr[a] = arr[b] arr[b] = temp }var arr = [4, 1, 5, 8, 3, 2, 6, 7]; function buddleSort(arr) { if (arr == null || arr.length == 0) return; for (let i = 0; i < arr.length; i++) { for (let j = 0; j < arr.length - 1 - i; j++) { if (compare(arr[j], arr[j + 1])) { swap(arr, j, j + 1) } } } } buddleSort(arr) console.log(arr) //[ 1, 2, 3, 4, 5, 6, 7, 8 ] function compare(a, b) { if (a > b) return true//大于正序 小于降序 else false } function swap(arr, a, b) { let temp = arr[a] arr[a] = arr[b] arr[b] = temp }
选择排序
var arr = [4, 1, 5, 8, 3, 2, 6, 7]; function selectSort(arr) { if (arr == null || arr.length == 0) return; for (let i = 0; i < arr.length - 1; i++) { let minIndex = i for (let j = i; j < arr.length; j++) { if (compare(arr[j], arr[minIndex])) { minIndex = j } } swap(arr, i, minIndex) } } selectSort(arr) console.log(arr)//[ 1, 2, 3, 4, 5, 6, 7, 8 ] function compare(a, b) { if (a < b) return true else false } function swap(arr, a, b) { let temp = arr[a] arr[a] = arr[b] arr[b] = temp }
任何一种排序算法，都没有优劣之分，只有是否适合的场景
数据量大（越混乱）的最适于快速排序
越有序适于冒泡排序
简单快速排序
// 简单快排 使用数组 var arr = [4, 1, 5, 8, 3, 2, 6, 7]; function simplyQuickSort(arr) { if (arr == null || arr.length == 0) return []; var leader = arr[0]; // 如果传入很大的数组，性能就差了 var left = []; var right = []; for (var i = 1; i < arr.length; i++) { if (arr[i] < leader) left.push(arr[i]); else right.push(arr[i]); } left = simplyQuickSort(left) right = simplyQuickSort(right) return left.concat(leader, right) } console.log(simplyQuickSort(arr)) //[ 1, 2, 3, 4, 5, 6, 7, 8 ]
标准快排
通过指针判断，不使用数组
// 标准快排 var arr = [2, 4, 1, 5, 8, 3, 2, 6, 7]; function quick(arr, begin, end) { if (begin >= end - 1) return; let left = begin let right = end do { do left++; while (left < right && arr[left] < arr[begin]) do right--; while (right > left && arr[right] > arr[begin]) // arr[left]是左边第一个比leader（arr[begin]）大 // arr[right]是右边第一个比leader（arr[begin]）小 if (left < right) swap(arr, left, right) } while (left < right) // 找到左右两指针，中间点如下4 let swapPoint = right == left ? right - 1 : right; swap(arr, begin, swapPoint) quick(arr, begin, swapPoint) quick(arr, swapPoint + 1, end) return arr } function swap(arr, a, b) { let temp = arr[a] arr[a] = arr[b] arr[b] = temp } function quickSort(arr) { if (!arr || arr.length < 2) return; return quick(arr, 0, arr.length) } console.log(quickSort(arr)) //[ 1, 2, 2, 3, 4, 5, 6, 7, 8 ]
栈
栈结构： 先入后出，类比成一个箱子，先放进去的，就被压到下面
类比变量声明，全局变量在下面，局部变量在上面
function Stack() { this.arr = [] this.push = function(value) { this.arr.push(value) } this.pop = function() { return this.arr.pop() } } let s = new Stack() s.push(1) s.push(2) s.push(3) console.log(s.arr) //[ 1, 2, 3 ] s.pop() console.log(s.arr) //[ 1, 2 ]
队列
队列结构：先入先出，类比成一个管道
function Queue() { this.arr = [] this.enqueue = function(value) { this.arr.push(value) } this.dequeue = function() { return this.arr.shift() } } let q = new Queue() q.enqueue(4) q.enqueue(5) q.enqueue(6) q.enqueue(7) console.log(q.arr) //[ 4, 5, 6, 7 ] q.dequeue() console.log(q.arr) //[ 5, 6, 7 ]
双向链表
优点：无论给出哪一个节点，都能对整个链表进行遍历
缺点： 多耗费一个引用的空间，而且构建双向链表比较复杂
function Node(value) { this.value = value this.next = null this.prev = null } let node1 = new Node(1) let node2 = new Node(2) let node3 = new Node(3) let node4 = new Node(4) let node5 = new Node(5) node1.next = node2 node2.prev = node1 node2.next = node3 node3.prev = node2 node3.next = node4 node4.prev = node3 node4.next = node5 node5.prev = node4 function bianli(root) { if (root == null) return console.log(root.value) bianli(root.next) // bianli(root.prev) } bianli(node1)
二维数据结构
类比文件夹排列方式
var arr = new Array(4) for (var i = 0; i < arr.length; i++) { arr[i] = new Array(8) } console.log(arr)//创建4行8列的数组
二维数据结构是一维数据结构进化
二维拓扑结构(图) 是 链表进化
树形结构（文件夹排列）
—— 有向无环图 —— 树是图的一种
树形结构有一个跟节点（比如C盘）
树形结构没有回路(闭合路径)
根节点： A
叶子节点：下边没有其他节点了的节点
节点：既不是根节点，又不是叶子节点的普通节点
树的度： 这颗树有最多叉的节点有多少个叉，就有多少个度，如图为3
树的深度： 树最深有几层，树的深度就为几，如图为3
二叉树
树的度最多为2的树形结构
二叉树的根节点A 子节点：某个节点下面的节点 父节点： 上级节点 叶子节点： CDE 节点： B
满二叉树
(1) 所有的叶子节点都在最底层
(2) 每个非叶子节点都有两个子节点（必须有两个子节点）
完全二叉树
国内定义：
叶子节点都在最后一层或倒数第二层 叶子节点都向左聚拢
国际定义：
叶子节点都在最后一层或倒数第二层 如果有叶子节点，就必然有两个叶子节点
子树
在二叉树中，每个节点都认为自己是根节点
子树： 二叉树中，每一个节点(包括树的根节点)或叶子节点，都是一颗子树的根节点
左子树 和 右子树：
对于A来说
二叉树遍历
遍历: 将一个集合中每一个元素进行获取并查看
传递二叉树(链表)要传根节点
前序遍历：(先根次序遍历)
先打印当前的，再打印左边的，再打印右边的
中序遍历：(中根次序遍历)
先打印左边的，再打印当前的，再打印右边的
后序遍历：(后根次序遍历)
先打印左边的，再打印右边的，再打印当前的
先打印左边的，再打印右边的，再打印当前的
前序遍历
// 前序遍历 function Node(value) { this.value = value this.left = null this.right = null } var a = new Node("A") var b = new Node("B") var c = new Node("C") var d = new Node("D") var e = new Node("E") var f = new Node("F") var g = new Node("G") a.left = c a.right = b c.left = f c.right = g b.left = d b.right = e // 先根次序遍历 function forwards(root) { if (root == null) return; console.log(root.value) forwards(root.left) forwards(root.right) } forwards(a)//传入根节点 输出 ACFGBDE
中序遍历
(次序的投影)
// 中序遍历 function Node(value) { this.value = value this.left = null this.right = null } var a = new Node("A") var b = new Node("B") var c = new Node("C") var d = new Node("D") var e = new Node("E") var f = new Node("F") var g = new Node("G") a.left = c a.right = b c.left = f c.right = g b.left = d b.right = e // 中根次序遍历 function median(root) { if (root == null) return; median(root.left) console.log(root.value) median(root.right) } median(a) //传入根节点 输出 FCGADBE
后序遍历
// 后序遍历 function Node(value) { this.value = value this.left = null this.right = null } var a = new Node("A") var b = new Node("B") var c = new Node("C") var d = new Node("D") var e = new Node("E") var f = new Node("F") var g = new Node("G") a.left = c a.right = b c.left = f c.right = g b.left = d b.right = e // 后根次序遍历 function backwards(root) { if (root == null) return; backwards(root.left) backwards(root.right) console.log(root.value) } backwards(a) //传入根节点 输出 FGCDEBA
给出前序中序还原二叉树(必须有中序，否则还原不了)，并写出后序遍历
前序遍历：A(根节点) CFG(左子树) BDE(右子树)
中序遍历：(左子树)FCG A(根节点) DBE(右子树)
如下图所示：
故后序遍历： FGCDEBA
给出后序中序还原二叉树(必须有中序，否则还原不了)，并写出前序遍历
后序遍历： (左子树)FGC DEB(左子树) A(根节点)
中序遍历：(左子树)FCG A(根节点) DBE(左子树)
如下图所示：
故前序遍历： ACFGBDE
代码实现前序中序还原二叉树
// 代码实现前序中序还原二叉树 var pre = ['A', 'C', 'F', 'G', 'B', 'D', 'E'] var mid = ['F', 'C', 'G', 'A', 'D', 'B', 'E'] function Node(value) { this.value = value this.left = null this.right = null } function preMid(pre, mid) { if (pre == null || mid == null || pre.length == 0 || mid.length == 0 || pre.length != mid.length) return; // 获取根节点 var root = new Node(pre[0]) // 获取根节点在中序的索引位置 var index = mid.indexOf(root.value) // 获取前序左子树 var preLeft = pre.slice(1, index + 1) // 获取前序右子树 var preRight = pre.slice(index + 1) // 获取中序的左子树 var midLeft = mid.slice(0, index) // 获取中序右子树 var midRight = mid.slice(index + 1) // 根据左子树的前序和中序还原左子树并赋值给root.left root.left = preMid(preLeft, midLeft) // 根据右子树的前序和中序还原右子树并赋值给root.right root.right = preMid(preRight, midRight) return root } console.log(preMid(pre, mid))
代码实现后序中序还原二叉树
// 代码实现后序中序还原二叉树 var after = ['F', 'G', 'C', 'D', 'E', 'B', 'A'] var mid = ['F', 'C', 'G', 'A', 'D', 'B', 'E'] function Node(value) { this.value = value this.left = null this.right = null } function afterMid(after, mid) { if (after == null || mid == null || after.length == 0 || mid.length == 0 || after.length != mid.length) return; // 获取根节点 var root = new Node(after[after.length - 1]) // 获取根节点在中序的位置 var index = mid.indexOf(root.value) // 获取后序左子树 var afterLeft = after.slice(0, index) // 获取后序右子树 var afterRight = after.slice(index, after.length - 1) // 获取中序左子树 var midLeft = mid.slice(0, index) // 获取中序右子树 var midRight = mid.slice(index + 1) // 根据左子树的后序和中序还原左子树并赋值给root.left root.left = afterMid(afterLeft, midLeft) // 根据右子树的后序和中序还原右子树并赋值给root.right root.right = afterMid(afterRight, midRight) return root } console.log(afterMid(after, mid))
二叉树的深搜和广搜
二叉树的搜索
树的搜索，图的搜索，爬虫的逻辑，搜索引擎的爬虫算法
深度优先搜索：更适合探索未知
广度优先搜索：更适合探索局域
代码实现二叉树的深度优先搜索(DFS)
function Node(value) { this.value = value this.left = null this.right = null } var a = new Node('A') var b = new Node('B') var c = new Node('C') var d = new Node('D') var e = new Node('E') var f = new Node('F') var g = new Node('G') a.left = c a.right = b c.left = f c.right = g b.left = d b.right = e // 代码实现二叉树的深度优先搜索 // 对于二叉树来说，深度优先搜索和前序遍历的顺序是一样的 function DFS(root, target) { if (root == null) return false if (root.value == target) return true var left = DFS(root.left, target) var right = DFS(root.right, target) return left || right } console.log(DFS(a, 'E')) //true
代码实现二叉树的广度优先搜索(BFS)
function Node(value) { this.value = value this.left = null this.right = null } var a = new Node('A') var b = new Node('B') var c = new Node('C') var d = new Node('D') var e = new Node('E') var f = new Node('F') var g = new Node('G') a.left = c a.right = b c.left = f c.right = g b.left = d b.right = e // 代码实现二叉树的广度优先搜索(BFS) function BFS(rootList, target) { if (rootList == null || rootList.length == 0) return false var childList = [] for (var i = 0; i < rootList.length; i++) { // 为防止数组里面出现null而报错 if (rootList[i] == null) return false if (rootList[i] != null && rootList[i].value == target) { return true } else { childList.push(rootList[i].left) childList.push(rootList[i].right) } } return BFS(childList, target) } console.log(BFS([a], 'g')) //true
二叉树的比较
遇到二叉树比较的问题时，必须要确定，左右两颗子树如果交换位置，既左右互换算不算同一颗二叉树
如果是笔试的话，没有特殊的说明左右互换还是同一颗树，那么默认互换后不是同一棵树
如果是面试。尽量问一下。
function Node(value) { this.value = value this.left = null this.right = null } var a1 = new Node('A') var b1 = new Node('B') var c1 = new Node('C') var d1 = new Node('D') var e1 = new Node('E') var f1 = new Node('F') var g1 = new Node('G') a1.left = c1 a1.right = b1 c1.left = f1 c1.right = g1 b1.left = d1 b1.right = e1 var a2 = new Node('A') var b2 = new Node('B') var c2 = new Node('C') var d2 = new Node('D') var e2 = new Node('E') var f2 = new Node('F') var g2 = new Node('G') a2.left = c2 a2.right = b2 c2.left = f2 c2.right = g2 b2.left = d2 b2.right = e2 // 二叉树的比较 // 强调左右不能互换 function compareTree(root1, root2) { // 判断是同一颗树 if (root1 == root2) return true if (root1 == null && root2 != null || root2 == null && root1 != null) return false // 相同位置是否相等 if (root1.value != root2.value) return false // 左子树与右子树皆为true才证明同一颗树 return compareTree(root1.left, root2.left) && compareTree(root1.right, root2.right) } console.log(compareTree(a1, a2)) //true
二叉树左右子树互换后的比较
function Node(value) { this.value = value this.left = null this.right = null } var a1 = new Node('A') var b1 = new Node('B') var c1 = new Node('C') var d1 = new Node('D') var e1 = new Node('E') var f1 = new Node('F') var g1 = new Node('G') a1.left = c1 a1.right = b1 c1.left = f1 c1.right = g1 b1.left = d1 b1.right = e1 var a2 = new Node('A') var b2 = new Node('B') var c2 = new Node('C') var d2 = new Node('D') var e2 = new Node('E') var f2 = new Node('F') var g2 = new Node('G') // 交换位置 a2.right = c2 a2.left = b2 c2.left = f2 c2.right = g2 b2.left = d2 b2.right = e2 // 二叉树的比较 // 强调左右互换,也可以左右互换 function compareTree(root1, root2) { // 判断是同一颗树 if (root1 == root2) return true if (root1 == null && root2 != null || root2 == null && root1 != null) return false // 相同位置是否相等 if (root1.value != root2.value) return false return compareTree(root1.left, root2.left) && compareTree(root1.right, root2.right) || compareTree(root1.left, root2.right) && compareTree(root1.right, root2.left) } console.log(compareTree(a1, a2)) //true
二叉树diff算法
function Node(value) { this.value = value this.left = null this.right = null } var a1 = new Node('A') var b1 = new Node('B') var c1 = new Node('C') var d1 = new Node('D') var e1 = new Node('E') var f1 = new Node('F') var g1 = new Node('G') a1.left = c1 a1.right = b1 c1.left = f1 c1.right = g1 b1.left = d1 b1.right = e1 var a2 = new Node('A') var b2 = new Node('B') var c2 = new Node('C') var d2 = new Node('D') var e2 = new Node('E') var f2 = new Node('F') var g2 = new Node('G') a2.right = b2 a2.left = c2 c2.left = f2 // 删除 // c2.right = g2 b2.left = d2 b2.right = e2 // 新增 f2.right = g2 // 二叉树的diff 比较DOM // 新增了什么，修改了什么，删除了什么 // {type:'新增', origin: null, now: c2} // {type:'修改', origin: c1, now: c2} // {type:'删除', origin: c2, now: null} function diffTree(root1, root2, diffList) { // 两个节点一样返回diffList 递归出口 if (root1 == root2) return diffList // 新增了什么 if (root1 == null && root2 != null) { diffList.push({ type: '新增', origin: null, now: root2 }) } // 删除了什么 else if (root1 != null && root2 == null) { diffList.push({ type: '删除', origin: root1, now: null }) } // 修改了什么 else if (root1.value != root2.value) { diffList.push({ type: '修改', origin: root1, now: root2 }) } else { diffTree(root1.left, root2.left, diffList) diffTree(root1.right, root2.right, diffList) } } var diffList = [] diffTree(a1, a2, diffList) console.log(diffList) 输出： [ { type: '新增', origin: null, now: Node { value: 'G', left: null, right: null } }, { type: '删除', origin: Node { value: 'G', left: null, right: null }, now: null } ]
图的最小生成树问题
树： 有向无环图
普利姆算法(Prime)(加点法)
克鲁斯卡尔算法(Kruskal)(加边法)
普利姆算法(Prime)(加点法)
任选一个点作为起点
找到以当前选中的点为起点路径最短的边
如果这个边的另一端没有被连通进来，那么就连结
如果这个边的的另一端也早就被连通进来了，则看倒数第二短的边
重复2-4直到将所有的点都连通为止
克鲁斯卡尔算法(Kruskal)(加边法)
选择最短的边进行连接
要保证边连接的两端至少有一个点是最新的点
或者这个边是将两个部落进行连接的
重复1-3直到将所有的点都连接到一起
代码实现普利姆(Prime)算法(加点法)
表示一个图，可以使用点集合和边集合
点集合：[a, b, c, d, e]
// 普利姆(Prime)算法(加点法) var MAX = 65535 // 点集合 var pointSet = [] // 相邻矩阵(距离) var distance = [ [0, 4, 7, MAX, MAX], [4, 0, 8, 6, MAX], [7, 8, 0, 5, MAX], [MAX, 6, 5, 0, 7], [MAX, MAX, MAX, 7, 0] ] function Node(value) { this.value = value this.neighbor = [] } var a = new Node('A') var b = new Node('B') var c = new Node('C') var d = new Node('D') var e = new Node('E') pointSet.push(a) pointSet.push(b) pointSet.push(c) pointSet.push(d) pointSet.push(e) function getIndex(str) { for (var i = 0; i < pointSet.length; i++) { if (str == pointSet[i].value) return i } return -1 } // 需要传入点的集合，边的集合，当前已经连接进入的集合 // 此方法，根据当前已经有的节点，来进行判断，获取到距离最短的点 function getMinDisNode(pointSet, distance, nowPointSet) { // 线段的起点 var fromNode = null // 线段的终点 var minDisNode = null var minDis = MAX //线段默认距离MAX // 根据当前已有的这些 点为起点，依次判断连接其他的点的距离是多少 for (var i = 0; i < nowPointSet.length; i++) { var nowPointIndex = getIndex(nowPointSet[i].value) for (var j = 0; j < distance[nowPointIndex].length; j++) { // thisNode表示distance中的点，但是这个点不是对象 var thisNode = pointSet[j] // 首先这个点不能是已经接入的点，且点之间的距离得是目前的最短距离 if (nowPointSet.indexOf(thisNode) < 0 && distance[nowPointIndex][j] < minDis) { fromNode = nowPointSet[i] minDisNode = thisNode minDis = distance[nowPointIndex][j] } } } console.log(minDis) // 将起点和终点相连 fromNode.neighbor.push(minDisNode) minDisNode.neighbor.push(fromNode) return minDisNode } function prime(pointSet, distance, startPiont) { var nowPointSet = [] nowPointSet.push(startPiont) // 获取最小代价的边 while (true) { var minDisNode = getMinDisNode(pointSet, distance, nowPointSet) nowPointSet.push(minDisNode) // 把所有的点连接起来终止 if (nowPointSet.length == pointSet.length) { break; } } } prime(pointSet, distance, pointSet[2]) console.log(pointSet) 输出： 5 //CD 6 //BD 4 //AB 7 //DE [ Node { value: 'A', neighbor: [ [Node] ] }, Node { value: 'B', neighbor: [ [Node], [Node] ] }, Node { value: 'C', neighbor: [ [Node] ] }, Node { value: 'D', neighbor: [ [Node], [Node], [Node] ] }, Node { value: 'E', neighbor: [ [Node] ] } ]
代码实现克鲁斯卡尔(Kruskal)算法(加边法)
// 克鲁斯卡尔(Kruskal)算法(加边法) var MAX = 65535 // 点集合 var pointSet = [] // 相邻矩阵(距离) var distance = [ [0, 4, 7, MAX, MAX], [4, 0, 8, 6, MAX], [7, 8, 0, 5, MAX], [MAX, 6, 5, 0, 7], [MAX, MAX, MAX, 7, 0] ] function Node(value) { this.value = value this.neighbor = [] } var a = new Node('A') var b = new Node('B') var c = new Node('C') var d = new Node('D') var e = new Node('E') pointSet.push(a) pointSet.push(b) pointSet.push(c) pointSet.push(d) pointSet.push(e) function canLink(resultList, tempBegin, tempEnd) { var beginIn = null var endIn = null for (var i = 0; i < resultList.length; i++) { // 判断起点，终点是否在这个部落里 if (resultList[i].indexOf(tempBegin) > -1) { beginIn = resultList[i] } if (resultList[i].indexOf(tempEnd) > -1) { endIn = resultList[i] } } // begin和end在同一个部落 => 不可以连接 if (beginIn != null && endIn != null && beginIn == endIn) { return false } // 两个点都是新的点(都不在任何部落里) => 可以连接，产生新的部落 // begin在A部落，end没有部落， => A部落扩张一个村庄 // end在A部落，begin没有部落， => A部落扩张一个村庄 // begin在A部落，end在B部落， => 将AB两个部落合并 return true } function link(resultList, tempBegin, tempEnd) { var beginIn = null var endIn = null for (var i = 0; i < resultList.length; i++) { // 判断起点，终点是否在这个部落里 if (resultList[i].indexOf(tempBegin) > -1) { beginIn = resultList[i] } if (resultList[i].indexOf(tempEnd) > -1) { endIn = resultList[i] } } // 两个点都是新的点(都不在任何部落里) => 可以连接，产生新的部落 if (beginIn == null && endIn == null) { let newArr = [] newArr.push(tempBegin) newArr.push(tempEnd) resultList.push(newArr) } // begin在A部落，end没有部落， => A部落扩张一个村庄 else if (beginIn != null && endIn == null) { beginIn.push(tempEnd) } // end在A部落，begin没有部落， => A部落扩张一个村庄 else if (beginIn == null && endIn != null) { endIn.push(tempBegin) } // begin在A部落，end在B部落， => 将AB两个部落合并 else if (beginIn != null && endIn != null && beginIn != endIn) { var allIn = beginIn.concat(endIn) var needRemove = resultList.indexOf(endIn) resultList.splice(needRemove, 1) needRemove = resultList.indexOf(beginIn) resultList.splice(needRemove, 1) resultList.push(allIn) } tempBegin.neighbor.push(tempEnd) tempEnd.neighbor.push(tempBegin) } function Kruskal(pointSet, distance) { var resultList = [] //这里是二维数组，此数组代表的是有多少个‘部落’ while (true) { var minDis = MAX var begin = null var end = null for (var i = 0; i < distance.length; i++) { for (var j = 0; j < distance[i].length; j++) { var tempBegin = pointSet[i] var tempEnd = pointSet[j] if (i != j //去掉自己到自己的距离，因为都为0 && distance[i][j] < minDis //小于目前的最短距离 && canLink(resultList, tempBegin, tempEnd) //判断能否连接 ) { minDis = distance[i][j] begin = tempBegin end = tempEnd } } } console.log(minDis) link(resultList, begin, end) // 只存在一个部落，且这个部落里的村庄数和所有的村庄总和是相等的 if (resultList.length == 1 && resultList[0].length == pointSet.length) { break; } } } Kruskal(pointSet, distance) console.log(pointSet) 输出： 4 //AB 5 //CD 6 //BD 7 //DE [ Node { value: 'A', neighbor: [ [Node] ] }, Node { value: 'B', neighbor: [ [Node], [Node] ] }, Node { value: 'C', neighbor: [ [Node] ] }, Node { value: 'D', neighbor: [ [Node], [Node], [Node] ] }, Node { value: 'E', neighbor: [ [Node] ] } ]
二叉搜索树
有一万个数据，写一个方法，进行查找，查找给定的数，返回存在还是不存在，要求：尽可能的性能好。 var arr = [] for (var i = 0; i < 10000; i++) { arr[i] = Math.floor(Math.random() * 10000) } var num = 0 function search(arr, target) { for (var i = 0; i < arr.length; i++) { num += 1 if (arr[i] == target) return true } return false } console.log(search(arr, 1000), num)
二叉搜索树(二叉排序树)
首先这是一颗二叉树
其次有排序的效果，左子树的节点都比当前节点小，右子树的节点都比当前节点大
构建二叉搜索树
var arr = [] for (var i = 0; i < 10000; i++) { arr[i] = Math.floor(Math.random() * 10000) } var num = 0 // 传统的方法搜索 function search(arr, target) { for (var i = 0; i < arr.length; i++) { num += 1 if (arr[i] == target) return true } return false } console.log(search(arr, 1000), num) //true 6488 // 二叉树 function Node(value) { this.value = value this.left = null this.right = null } function addNode(root, num) { //num表示当前节点 if (root == null) return; if (root.value == num) return; // 目标值比当前节点大 if (root.value < num) { // 如果右侧为空，则创建节点 if (root.right == null) root.right = new Node(num) // 如果右侧有值，就形成递归 else addNode(root.right, num) } // 目标值比当前节点小 else { if (root.left == null) root.left = new Node(num) else addNode(root.left, num) } } function buildSearchTree(arr) { if (arr == null || arr.length == 0) return null var root = new Node(arr[0]) for (var i = 1; i < arr.length; i++) { addNode(root, arr[i]) } return root }
// 二叉树搜索,类似前序遍历 var num2 = 0 function searchByTree(root, target) { if (root == null) return false; num2 += 1 if (root.value == target) return true if (root.value > target) return searchByTree(root.left, target) else return searchByTree(root.right, target) } var root = buildSearchTree(arr) console.log(searchByTree(root, 1000), num2) //true 16
由测试得出，使用二叉树搜索树比传统方法性能好上近50倍以上，当我们希望二叉搜索树变为二叉平衡搜索树，性能优化
平衡二叉树
根节点的左子树与右子树的高度差不能超过1
这颗二叉树的每个子树都符合第一条规则
用代码判断平衡二叉树
function Node(value) { this.value = value this.left = null this.right = null } var a = new Node('A') var b = new Node('B') var c = new Node('C') var d = new Node('D') var e = new Node('E') var f = new Node('F') var g = new Node('G') var h = new Node('H') var y = new Node('Y') a.left = b a.right = c c.left = f c.right = g b.left = d b.right = e d.right = h e.right = y function getDeep(root) { if (root == null) return 0 //选择左子树和右子树中的最大深度 + 1 return Math.max(getDeep(root.left), getDeep(root.right)) + 1 } // 判断平衡二叉树 function isBalance(root) { if (root == null) return true var leftDeep = getDeep(root.left) var rightDeep = getDeep(root.right) // 根节点的左子树与右子树的高度差不能超过1 if (Math.abs(leftDeep - rightDeep) > 1) return false // 这颗二叉树的每个子树都符合第一条规则 else return isBalance(root.left) && isBalance(root.right) } console.log(isBalance(a)) // true
二叉树的单旋
把一个不平衡的二叉树变为平衡的二叉树，需要用到二叉树的单旋
二叉树单旋操作(左单旋、右单旋)
旋转节点：不平衡的节点为旋转节点
新根：旋转之后称为根节点的节点
变化分支：父级节点发生变化的那个分支
不变分支：父级节点不变的那个分支
- 某个节点不平衡，如果左边浅，右边深，进行左单旋
进行左单旋：
找到新根
找到变化分支
当前旋转节点的右孩子为变化分支
新根的左孩子为旋转节点
返回新的根节点 - 某个节点不平衡，如果右边浅，左边深，进行右单旋
进行右单旋：
找到新根
找到变化分支
当前旋转节点的左孩子为变化分支
新根的右孩子为旋转节点
返回新的根节点
function Node(value) { this.value = value this.left = null this.right = null } var node2 = new Node('2') var node5 = new Node('5') var node3 = new Node('3') var node6 = new Node('6') // 左旋 // node2.right = node5 // node5.left = node3 // node5.right = node6 // 右旋 node6.left = node3 node3.left = node2 node3.right = node5 function getDeep(root) { if (root == null) return 0 //选择左子树和右子树中的最大深度 return Math.max(getDeep(root.left), getDeep(root.right)) + 1 } // 判断平衡二叉树 function isBalance(root) { if (root == null) return true var leftDeep = getDeep(root.left) var rightDeep = getDeep(root.right) // 根节点的左子树与右子树的高度差不能超过1 if (Math.abs(leftDeep - rightDeep) > 1) return false // 这颗二叉树的每个子树都符合第一条规则 else return isBalance(root.left) && isBalance(root.right) } // 左旋 function leftRotate(root) { // 找到新根 let newRoot = root.right // 找到变化分支 let changeTree = root.right.left // 当前旋转节点的右孩子为变化分支 root.right = changeTree // 新根的左孩子为旋转节点 newRoot.left = root // 返回新的根节点 return newRoot } // 右旋 function rightRotate(root) { // 找到新根 let newRoot = root.left // 找到变化分支 let changeTree = root.left.right // 当前旋转节点的左孩子为变化分支 root.left = changeTree // 新根的右孩子为旋转节点 newRoot.right = root // 返回新的根节点 return newRoot } // 把不平衡的二叉树变为平衡的二叉树，返回新的二叉树,按照后序遍历顺序进行操作 function change(root) { if (isBalance(root)) return root if (root.left != null) root.left = change(root.left) if (root.right != null) root.right = change(root.right) var leftDeep = getDeep(root.left) var rightDeep = getDeep(root.right) // 不超过1 if (Math.abs(leftDeep - rightDeep) < 2) return root // 不平衡，左边深，进行右旋 else if (leftDeep > rightDeep) return rightRotate(root) // 不平衡，右边深，进行左旋 else return leftRotate(root) return root } console.log(isBalance(node6)) // false var newRoot = change(node6) console.log(newRoot) // Node { // value: '3', // left: Node { value: '2', left: null, right: null }, // right: // Node { // value: '6', // left: Node { value: '5', left: null, right: null }, // right: null } } console.log(isBalance(newRoot)) //true
二叉树双旋的概念
二叉树的双旋(左右双旋、右左双旋)
变化分支，不可以是唯一的最深分支，如果变化分支是唯一的最深分支，要先进行反向旋转
当要对某个节点进行左单旋时， 如果变化分支是唯一的最深分支，那么我们要对新根进行右单旋，然后再进行左单旋 这样的旋转叫做右左双旋
当要对某个节点进行右单旋时， 如果变化分支是唯一的最深分支，那么我们要对新根进行左单旋，然后再进行右单旋 这样的旋转叫做左右双旋
二叉树双旋的代码实现
function Node(value) { this.value = value this.left = null this.right = null } var node8 = new Node('8') var node7 = new Node('7') var node6 = new Node('6') var node5 = new Node('5') var node2 = new Node('2') // 左右双旋 // node8.left = node7 // node7.left = node6 // node6.left = node5 // node5.left = node2 // 右左双旋 node2.right = node5 node5.right = node6 node6.right = node7 node7.right = node8 function getDeep(root) { if (root == null) return 0 //选择左子树和右子树中的最大深度 return Math.max(getDeep(root.left), getDeep(root.right)) + 1 } // 判断平衡二叉树 function isBalance(root) { if (root == null) return true var leftDeep = getDeep(root.left) var rightDeep = getDeep(root.right) // 根节点的左子树与右子树的高度差不能超过1 if (Math.abs(leftDeep - rightDeep) > 1) return false // 这颗二叉树的每个子树都符合第一条规则 else return isBalance(root.left) && isBalance(root.right) } // 左旋 function leftRotate(root) { // 找到新根 let newRoot = root.right // 找到变化分支 let changeTree = root.right.left // 当前旋转节点的右孩子为变化分支 root.right = changeTree // 新根的左孩子为旋转节点 newRoot.left = root // 返回新的根节点 return newRoot } // 右旋 function rightRotate(root) { // 找到新根 let newRoot = root.left // 找到变化分支 let changeTree = root.left.right // 当前旋转节点的左孩子为变化分支 root.left = changeTree // 新根的右孩子为旋转节点 newRoot.right = root // 返回新的根节点 return newRoot } // 把不平衡的二叉树变为平衡的二叉树，返回新的二叉树,按照后序遍历顺序进行操作 function change(root) { if (isBalance(root)) return root if (root.left != null) root.left = change(root.left) if (root.right != null) root.right = change(root.right) var leftDeep = getDeep(root.left) var rightDeep = getDeep(root.right) // 不超过1 if (Math.abs(leftDeep - rightDeep) < 2) { return root } // 不平衡，左边深，进行右旋 else if (leftDeep > rightDeep) { <!--左右双旋--> let changeTreeDeep = getDeep(root.left.right) let nochangeTreeDeep = getDeep(root.left.left) if (changeTreeDeep > nochangeTreeDeep) { root.left = leftRotate(root.left) } return rightRotate(root) } // 不平衡，右边深，进行左旋 else { <!--右左双旋--> let changeTreeDeep = getDeep(root.right.left) let nochangeTreeDeep = getDeep(root.right.right) if (changeTreeDeep > nochangeTreeDeep) { root.right = rightRotate(root.right) } return leftRotate(root) } return root } console.log(isBalance(node2)) // false var newRoot = change(node2) console.log(newRoot) // Node { // value: '5', // left: Node { value: '2', left: null, right: null }, // right: // Node { // value: '7', // left: Node { value: '6', left: null, right: null }, // right: Node { value: '8', left: null, right: null } } } console.log(isBalance(newRoot)) //true 数据量大就不平衡 <!--以下数据量大会发生二叉树不平衡--> function addNode(root, num) { //num表示当前节点 if (root == null) return; if (root.value == num) return; // 目标值比当前节点大 if (root.value < num) { // 如果右侧为空，则创建节点 if (root.right == null) root.right = new Node(num) // 如果右侧有值，就形成递归 else addNode(root.right, num) } // 目标值比当前节点小 else { if (root.left == null) root.left = new Node(num) else addNode(root.left, num) } } function buildSearchTree(arr) { if (arr == null || arr.length == 0) return null var root = new Node(arr[0]) for (var i = 1; i < arr.length; i++) { addNode(root, arr[i]) } return root } var num2 = 0 function searchByTree(root, target) { if (root == null) return false; num2 += 1 if (root.value == target) return true if (root.value > target) return searchByTree(root.left, target) else return searchByTree(root.right, target) } var arr = [] for (var i = 0; i < 10000; i++) { arr.push(Math.floor(Math.random() * 10000)) } var root = buildSearchTree(arr) console.log(searchByTree(root, 1000), num2) // true 16 var newRoot = change(root) num2 = 0 console.log(searchByTree(newRoot, 1000), num2) // true 13 console.log(isBalance(newRoot)) //false 因为不平衡我们没有考虑左左双旋、右右双旋
左左双旋与右右双旋
function Node(value) { this.value = value this.left = null this.right = null } var node8 = new Node('8') var node7 = new Node('7') var node6 = new Node('6') var node5 = new Node('5') var node2 = new Node('2') // 左右双旋 // node8.left = node7 // node7.left = node6 // node6.left = node5 // node5.left = node2 // 右左双旋 node2.right = node5 node5.right = node6 node6.right = node7 node7.right = node8 function getDeep(root) { if (root == null) return 0 //选择左子树和右子树中的最大深度 return Math.max(getDeep(root.left), getDeep(root.right)) + 1 } // 判断平衡二叉树 function isBalance(root) { if (root == null) return true var leftDeep = getDeep(root.left) var rightDeep = getDeep(root.right) // 根节点的左子树与右子树的高度差不能超过1 if (Math.abs(leftDeep - rightDeep) > 1) return false // 这颗二叉树的每个子树都符合第一条规则 else return isBalance(root.left) && isBalance(root.right) } // 左旋 function leftRotate(root) { // 找到新根 let newRoot = root.right // 找到变化分支 let changeTree = root.right.left // 当前旋转节点的右孩子为变化分支 root.right = changeTree // 新根的左孩子为旋转节点 newRoot.left = root // 返回新的根节点 return newRoot } // 右旋 function rightRotate(root) { // 找到新根 let newRoot = root.left // 找到变化分支 let changeTree = root.left.right // 当前旋转节点的左孩子为变化分支 root.left = changeTree // 新根的右孩子为旋转节点 newRoot.right = root // 返回新的根节点 return newRoot } // 把不平衡的二叉树变为平衡的二叉树，返回新的二叉树,按照后序遍历顺序进行操作 function change(root) { if (isBalance(root)) return root if (root.left != null) root.left = change(root.left) if (root.right != null) root.right = change(root.right) var leftDeep = getDeep(root.left) var rightDeep = getDeep(root.right) // 不超过1 if (Math.abs(leftDeep - rightDeep) < 2) { return root } // 不平衡，左边深，进行右旋 else if (leftDeep > rightDeep) { // 左右双旋 let changeTreeDeep = getDeep(root.left.right) let nochangeTreeDeep = getDeep(root.left.left) if (changeTreeDeep > nochangeTreeDeep) { root.left = leftRotate(root.left) } // 右右双旋 let newRoot = rightRotate(root) newRoot.right = change(newRoot.right) newRoot = change(newRoot) return newRoot } // 不平衡，右边深，进行左旋 else { // 右左双旋 let changeTreeDeep = getDeep(root.right.left) let nochangeTreeDeep = getDeep(root.right.right) if (changeTreeDeep > nochangeTreeDeep) { root.right = rightRotate(root.right) } // 左左双旋 let newRoot = leftRotate(root) newRoot, left = change(newRoot.left) newRoot = change(newRoot) return newRoot } return root }
234树的由来
二叉平衡排序树是极致的吗？ 答： 不是
如果我们要提升二叉平衡排序树的性能该如何做？
影响二叉平衡排序树的性能的点在哪？ 答：在于二叉平衡排序树只能有两个叉，导致在节点铺满的时候也会有很多层。希望可以一个节点存多个数。可以提升空间的性能
如何才能让查找的效率尽可能的少？答： 树的层级越少，查找效率越高
怎么样才能让二叉平衡排序树的层数变的更少？ 答：如果不是二叉，层数会更少
叉越多，层数越少，但是叉越多，树的结构就越复杂，一般我们认为有4个叉的时候性能最好，就出现234树的由来
234树：
我们希望有一颗树，最多有四个叉(度为4)
234树子节点永远在最后一层 234树永远是平衡的(每一个路径高度都相同)
达到了一定的效果 分支变多了，层数变少了 节点中存的树变多了，节点变少了
因为分支多了，所以复杂度上升了
希望对234树进行简化
希望能简化为二叉树 希望依旧保留多叉 希望依旧单节点中存放多个值、
节点是红色或黑色 根节点是黑色 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径不能有两个连续的红色节点) 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点
未完待续！！！
