数据结构与算法有什么关系？
可以容纳数据的结构被称为数据结构
算法是用来对数据结构进行处理的方法
数据结构是静态的，算法是动态的
线性数据结构
线性数据结构强调存储与顺序
数组
数组的扩容会消耗大量CPU（如一个长度为8的数组，当为其添加第9个数据时，操作系统会为其重新分配一个长度为16的空间，然后将原数组中的8个数据复制到新分配的数组中，再添加第9个数据），因此尽量避免数组扩容
数组特性：
1、存储在物理空间上是连续的
2、底层的数组长度是不可变的
3、数组的变量，指向了数组第一个元素的位置
优点：查询性能好，指定查询某个位置
缺点：
1、因为空间必须得是连续的，所以如果数组比较大，当系统的空间碎片较多的时候，容易存不下
2、因为数组的长度是固定的，所以数组的内容难以被添加和删除
数组a[1]/a[2]中的方括号用来表示存储地址的偏移
操作系统小知识：通过偏移查询数据性能最好
链表
若向传递一个链表，则必须传递链表的根节点
每一个节点，都认为自己是根节点
链表的特点：
1、空间上不是连续的
2、每存放一个值，都要多开销一个引用空间
优点：
1、只要内存足够大，就能存下，不用担心空间碎片的问题
2、链表的添加和删除非常的容易
缺点：
1、查询速度慢（指的是查询某个位置）
2、链表每一个节点都需要创建一个指向next的引用，浪费一些空间。当节点内数据越多的时候，这部分开销的内存影响相对越少
创建
function Node(value){this.value = value;this.next = null;}let a = new Node("a");let b = new Node("b");let c = new Node("c");let d = new Node("d");a.next = b;b.next = c;c.next = d;
遍历
概念：将一个集合中的每一个元素进行获取并查看
//数组
let arr = [1, 2, 3, 4, 5];
function arrErgodic(arr){
if(arr === null){return;}
for(let i = 0; i < arr.length; i++){
console.log(arr[i]);
}
}
//链表
function Node(value){
this.value = value;
this.next = null;
}
let a = new Node("a");
let b = new Node("b");
let c = new Node("c");
let d = new Node("d");
a.next = b;
b.next = c;
c.next = d;
function linkErgodic(root){
if(root === null){
return;
}
let temp = root;
while(true){
if(temp !== null){
console.log(temp.value);
}else{
break;
}
temp = temp.next;
}
}
递归遍历
递归遍历必须有出口
function bianLi(root){
if (root === null){
return;
}
console.log(root.value);
bianLi(root.next);
}
链表反转
递归
function reverse(head){
//当链表为空，直接返回null，当链表长度为1时，直接返回head
if(head === null || head.next === null){
return head;
}
//当前节点不是最后一个节点时，递归寻找最后一个节点
let result = reverse(head.next);//在找到最后一个节点后，递归将该节点抛出，并从后向前进行链表反转
head.next.next = head;//将当前节点下一个节点的next指针指向当前节点
head.next = null;//将当前节点的next指针设为空
return result;
}
循环头插法
function reverse(head){
let temp = null;
let newNode = null;
while(head){
temp = head.next;//将当前节点的下一个节点临时保存
head.next = newNode;//将当前节点指向反转后的首节点
newNode = head;//将当前节点设置为首节点
head = temp;//将保存好的临时节点设为头节点并进入下一轮循环
}
}
排序
冒泡排序
排序不是比较大小
排序的本质时比较和交换
核心思路：每一轮对比都将数组中最大的值放到末尾，并且每次对比都可能交换数组中两个元素的位置
function compare(a, b) {
if (a > b) {
return true;
}
return false;
}
function exchange(arr, a, b) {
var temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
function sort(arr) {
for (var i = 0; i < arr.length - 1; i++) {
for (var j = 0; j < arr.length - 1 - i; j++) {
if (compare(arr[j], arr[j + 1])) {
exchange(arr, j, j + 1);
}
}
}
return arr;
}
选择排序
核心思路：每一轮对比都将数组中最大的值放到末尾，与冒泡排序不同的是，选择排序的每一轮只进行一次交换，在比对过程中仅记录最大值的下标
function SelectSort(arr) {
for (var i = 0; i < arr.length - 1; i++) {
let maxIndex = 0;
for (var j = 0; j < arr.length - i; j++) {
if (compare(arr[maxIndex], arr[j])) {
maxIndex = j;
}
}
exchange(arr, maxIndex, arr.length - 1 - i);
}
return arr;
}
任何一种排序算法，都没有优劣之分，只有是否适合的场景
简单快速排序
牺牲性能换取的简单写法
核心思路：取数组中的某个值为参考值，遍历整个数组其他值，将比参考值大的元素放到参考值的右边，比参考值小的值放到参考值的左边，遍历完后，对左右两组数据再进行递归，使左右两组数据均为有序数组，最后将左右数组与参考值进行拼接
function quickSort(arr) {
if (arr === null || arr.length === 0) {//当数组为空的时候返回空数组，这里不是null的原因是为了后续进行递归时，拼接左右数组
return [];
}
let leader = arr[0];//取数组的第一位当参考
let left = [];
let right = [];
for (let i = 1; i < arr.length; i++) {//从第二位开始遍历整个数组，比参考值大的放到右边数组，否则放到左边数组
if (arr[i] < leader) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
left = quickSort(left);//对左右数组进行递归的排序，使得左右两边数组均为有序数组
right = quickSort(right);
left.push(leader);//将参考值push到左边有序数组的最后一位
return left.concat(right);//返回拼接后的有序数组
}
标准快速排序
核心思路：指定左右指针，因为要将第一位设为参考值，所以在向函数中传入区间时，使用左闭右开的方式，初次传入时，左边传入0，右边传入数组的长度，使用do…while循环进行比对，这样做指针从参考值的右侧一位开始比对，右指针从数组边界的最后一位开始比对，当左指针的索引值小于右指针的索引，且左指针对应值大于参考值时，移动右指针，当右指针对应值小于参考值，且右指针索引大于左指针索引时，对两个指针对应的值进行交换，循环进行两个指针的移动的对比，直到左指针索引值不小于右指针索引值，即完成一轮比对，将参考值与左指针左边一位进行交换，将数组分成两个部分进行递归的比对排序
function StandardQuickSort(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 (left < right && arr[right] > arr[begin]);
if (left < right) {
exchange(arr, left, right);
}
} while (left < right);
let changePoint = left - 1;
exchange(arr, begin, changePoint);
StandardQuickSort(arr, begin, changePoint);
StandardQuickSort(arr, changePoint + 1, end);
}
function quickSort(arr) {
StandardQuickSort(arr, 0, arr.length)
}
栈和队列
栈结构特点：先进后出
function Stack() {
this.arr = [];
this.push = function(value) {
this.arr.push(value);
};
this.pop = function() {
this.arr.pop();
}
}
队列结构特点：先进先出
function Queue(arr = []) {
this.arr = arr;
this.push = function(value) {
this.arr.push(value);
};
this.shift = function() {
this.arr.shift();
}
}
双向链表
function Node(value){
this.value = value;
this.next = null;
this.pre = null;
}
双向链表的优点是，无论给出哪一个节点，都能对整个链表进行遍历
缺点：多耗费一个引用的空间，而且构建双向链表比较复杂
二维数据结构
二位数组
创建一个i行j列的数组
//可以封装成一个函数
let arr = new Array(i);
for(let i = 0; i < arr.length; i++){
arr[i] = new Array(j);
}
二维拓扑结构（图）
只在乎关系，只要数据之间关系一样，就判定相等，由链表变化而来
树形结构
树形结构有一个根节点，树形结构没有回路
树形结构——有向无环图，树是图的一种
叶子节点：没有其他子节点
节点：既不是根节点，又不是叶子节点的普通节点
树的度：这棵树有最多叉的节点有多少个叉，这棵树的度就为多少
树的深度：树最深有几层，树的深度就为几
满二叉树
二叉树：树的度最多为2的树形结构
满二叉树：1、所有的叶子节点都在最底层；2、每个非叶子节点都有两个子节点
完全二叉树
国内定义：1、叶子节点都在最后一层或倒数第二层；2、叶子节点都向左聚拢
国外定义：1、叶子节点都在最后一层或倒数第二层；2、如果有叶子节点，就必然有两个叶子节点
二叉树中子树的概念
在二叉树中，每个节点都认为自己是根节点
子树：二叉树中，每一个节点或叶子节点，都是一个字数的根节点
左子树、右子树
二叉树的遍历
遍历：将集合中的每一个元素获取并查看
传递二叉树要传根节点
二叉树的遍历可以分为：
- 前序遍历（先根次序遍历）：先打印当前的，再打印左边的，再打印右边的
- 中序遍历（中根次序遍历）：先打印左边的，再打印当前的，再打印右边的
- 后序遍历（后根次序遍历）：先打印左边的，再打印右边的，在打印当前的
前序遍历
前序遍历的第一个节点即为根节点
function prevErgodic(root) {
if (root === null) {
return;
}
console.log(root.value);
prevErgodic(root.left);
prevErgodic(root.right);
}
中序遍历
根节点左边的为左子树，右边的为右子树
function middleErgodic(root) {
if (root === null) {
return;
}
middleErgodic(root.left);
console.log(root.value);
middleErgodic(root.right);
}
后序遍历
后续遍历的最后一个节点即为根节点
function behindErgodic(root) {
if (root === null) {
return;
}
behindErgodic(root.left);
behindErgodic(root.right);
console.log(root.value);
}
还原二叉树
根据前序中序还原二叉树
回顾：前序遍历的第一个节点为根节点，中序遍历根节点左边的即为左子树，根节点右边的即为右子树，其左右子树依然为同种遍历方式
根据中序后序还原二叉树
回顾：后续遍历的最后一个节点即为根节点，中序遍历根节点左边的即为左子树，根节点右边的即为右子树
代码实现前序中序还原二叉树
// 根据前序中序还原二叉树
let prev = ["A", "C", "F", "G", "B", "D", "E"];
let middle = ["F", "C", "G", "A", "D", "B", "E"];
function Node(value) {
this.value = value;
this.left = null;
this.right = null;
}
function returnTree(prev, middle) {
if (prev === null || middle === null || prev.length === 0 || prev.length === 0 || prev.length !== middle.length) return null;
let root = new Node(prev[0]);
let rootIndex = middle.indexOf(root.value); // 找到根节点在中序遍历中的位置，其值即为左子树的长度
let prevLeft = prev.slice(1, 1 + rootIndex); // 前序遍历的左子树
let prevRight = prev.slice(1 + rootIndex, prev.length); // 前序遍历的右子树
let middleLeft = middle.slice(0, rootIndex); // 中序遍历的左子树
let middleRight = middle.slice(rootIndex + 1, middle.length); // 中序遍历的右子树
root.left = returnTree(prevLeft, middleLeft); // 根据左子树的前序和中序还原左子树并赋值给root.left
root.right = returnTree(prevRight, middleRight); // 根据右子树的前序和中序还原右子树并赋值给root.right
return root;
}
console.log(returnTree(prev, middle));
代码实现中序后序还原二叉树
function returnTree(prev, middle) {
if (prev === null || middle === null || prev.length === 0 || middle.length === 0 || prev.length !== middle.length) return null;
let root = new Node(prev[0]);
let rootIndex = middle.indexOf(root.value);
let prevLeft = prev.slice(1, rootIndex + 1);
let prevRight = prev.slice(rootIndex + 1, prev.length);
let middleLeft = middle.slice(0, rootIndex);
let middleRight = middle.slice(rootIndex + 1, middle.length);
root.left = returnTree(prevLeft, middleLeft);
root.right = returnTree(prevRight, middleRight);
return root;
}
二叉树的搜索
深度优先搜索：纵向查找，更适合探索未知
广度优先搜索：横向查找，更适合探索局域
深度优先搜索
对于二叉树来说，深度优先搜索，和前序遍历的顺序是一样的
function deepSearch(root, target) {
if (root == null) return false;
if (root.value == target) return true;
let left = deepSearch(root.left, target);
let right = deepSearch(root.right, target);
return left || right;
}
广度优先搜索
核心思路，将当前层的所有节点遍历，在遍历过程中保存所有节点的子节点，若当前层为搜索到，则将保存的子节点列表递归传入下一次遍历
function rangeSearch(rootList, target) {
if (rootList === null || rootList.length === 0) return false;
let childList = []; // 创建一个childList用来存放当前层的所有子节点
for (let i = 0; i < rootList.length; i++) {
// 遍历当前层的所有节点查找是否与目标值匹配
if (rootList[i] !== null && rootList[i].value === target) {
return true;
} else {
childList.push(rootList[i].left);
childList.push(rootList[i].right);
}
}
return rangeSearch(childList, target);
}
二叉树的比较
function compareTree(root1, root2){
if(root1 === root2)return true;// 是同一棵树
if(root1 === null && root2 !== null || root1 !== null && root2 === null)return false;// 其中一棵树为空，另一棵树不为空
if(root1.value !== root2.value)return false;// 相同位置的值不相等
let leftBool = compareTree(root1.left, root2.left);// 递归对比左子树
let rightBool = compareTree(root1.right, root2.right);// 递归对比右子树
return leftBool && rightBool;// 当左右子树均相同时，才判定两棵树相等
}
遇到二叉树比较问题时，必须要确定，左右两棵子树如果交换位置，即左右呼唤，还算不算同一棵二叉树
如果是笔试，没有特殊的说明左右呼唤还是同一棵树，那么默认互换后不是同一棵树，如果是面试，尽量问一下
function compareTree(root1, root2) {
if (root1 === root2) return true; // 两棵树是同一棵树
if (root1 === null && root2 !== null || root1 !== null && root2 === 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);
}
diff算法
返回结果为一个数组，效果如下
//[
// {type: "新增", origin: "null", now: "xxx"},
// {type: "删除", origin: "xxx", now: "null"},
// {type: "修改", origin: "xxx1", now: "xxx2"}
//]
function diffTree(root1, root2, 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});
diffTree(root1.left, root2.left, diffList);
diffTree(root1.right, root2.right, diffList);
}else{
diffTree(root1.left, root2.left, diffList);
diffTree(root1.right, root2.right, diffList);
}
return diffList;
}
图的最小生成树问题
1、普利姆算法（加点法）
2、克鲁斯卡尔算法（加边法）
表示一个图，可以使用点集合和边集合
点集合：[a, b, c, d, e]
| A | B | C | D | E | |
|---|---|---|---|---|---|
| A | 0 | 4 | 7 | Max | Max |
| B | 4 | 0 | 8 | 6 | Max |
| C | 7 | 8 | 0 | 5 | Max |
| D | Max | 6 | 5 | 0 | 7 |
| E | Max | Max | Max | 7 | 0 |
普利姆算法
1、任选一个点作为起点
2、找到以当前选中点为起点路径最短的边
3、如果这个边的另一端没有被联通进来，那么就连结
4、如果这个边的另一端也早就被连进来了，则看倒数第二短的边
5、重复2-4直到将所有的点都联通为止
代码实现：
向函数中传入一个节点数组，其中每个节点以对象的方式进行表示，如{value: "A", neighbor}，传入一个距离数组，以二维数组表示，再传入一个起始点，可以取节点数组的任意一位；
主函数体：首先创建一个nowPointSet用来存放已经连结的点信息，并将起始节点push到该数组中，利用一个循环去依次寻找距离已连结点距离最短的节点，当已连结点数组的长度与传入节点数组的长度相等时，表示所有节点以连结完成，跳出循环，并返回nowPointSet
寻找距离最短节点的函数：该函数需传入节点集、距离集、已连结节点作为参数，声明一个起始节点一个终止节点以备找到最短距离后存放起始节点和中止节点，并声明一个最小距离minDis传入循环中来查找最小距离，这里的循环分为两层，外层循环的目标为nowPointSet的长度，内层循环的目标为当前循环节点在距离集中所在行的长度，因此需要判断当前循环节点在节点集中的位置，用nowIndex进行保存，在每次循环中，创建一个nowNode用来记录当前检验距离的终点，若当前终点不在nowPointSet中，并且当前距离小于minDis，则将先前声明的起始节点设为外层循环节点，即nowPointSet[i]，将终止节点设为nowNode，并将minDis设为当前循环的距离，两层循环结束后，即可找到当前已连结的所有节点中距离最近的未连接节点，为起始节点和终止节点设置neighbor并将终止节点返回
/**
* 根据当前已有节点，来进行判断，获取到距离最短的点
* @param {*} pointSet 点集合
* @param {*} distance 边集合
* @param {*} nowPointSet 当前已经连结进入的集合
*/
function getMinDisNode(pointSet, distance, nowPointSet) {
let fromNode = null; // 线段的起点
let minDisNode = null; // 线段的终点
let minDis = max;
// 根据当前已有的这些为起点，依次判断连结其他的点的距离是多少
for (let i = 0; i < nowPointSet.length; i++) {
let nowIndex = pointSet.indexOf(nowPointSet[i]); //获取当前节点的序号
for (let j = 0; j < distance[nowIndex].length; j++) {
let thisNode = pointSet[j]; //thisNode是一个字母
if (nowPointSet.indexOf(thisNode) < 0 && distance[nowIndex][j] < minDis) {
//首先当前点不能是已接入的点，其次点之间的距离得是目前的最小值
fromNode = nowPointSet[i];
minDisNode = thisNode;
minDis = distance[nowIndex][j];
}
}
}
fromNode.neighbor.push(minDisNode);
minDisNode.neighbor.push(fromNode);
return minDisNode;
}
/**
* 图节点构造函数
* @param {*} value
*/
function Node(value) {
this.value = value;
this.neighbor = [];
}
/**
* 普利姆算法
* @param {*} pointSet 点的集合
* @param {*} distance 边的集合
* @param {*} start 起始点
*/
function prim(pointSet, distance, start) {
let nowPointSet = []; //用来存放已连结的点
nowPointSet.push(start);
//获取最小代价的边
while (true) {
let minDisNode = getMinDisNode(pointSet, distance, nowPointSet);
nowPointSet.push(minDisNode);
if (nowPointSet.length === pointSet.length) {
break;
}
}
return nowPointSet;
}
克鲁斯卡尔算法
1、选择最短的边进行连结
2、要保证边连结的两端至少有一个点是新的点
3、或者这边是将两个部落进行连结的
4、重复1-3直到所有的点都连通为止
代码实现
// 克鲁斯卡尔算法
let pointSet = ["A", "B", "C", "D", "E"];
let max = 999999;
let 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]
];
/**
* 图节点构造函数
* @param {*} value
*/
function Node(value) {
this.value = value;
this.neighbor = [];
}
let a = new Node("A");
let b = new Node("B");
let c = new Node("C");
let d = new Node("D");
let e = new Node("E");
pointSet = [a, b, c, d, e];
/**
* 判断两个节点是否可以连结
* @param {Array} resultList
* @param {Object} tempBegin 传入的临时起始节点
* @param {Obect} tempEnd 传入的临时终止节点
*/
function canLink(resultList, tempBegin, tempEnd) {
let beginIn = null;
let endIn = null;
for (let 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在A部落，end没有部落 ——A部落扩张一个村落
// end在A部落，begin没有部落 ——A部落扩张一个村落
// begin在A部落，end在B部落 ——将AB部落合并
// begin和end在同一个部落 ——不可以连接
if (beginIn === endIn && beginIn !== null && endIn !== null) {
return false;
}
return true;
}
/**
* 连结两个点
* @param {Array} resultList
* @param {Object} begin
* @param {Object} end
*/
function link(resultList, begin, end) {
let beginIn = null;
let endIn = null;
for (let i = 0; i < resultList.length; i++) {
if (resultList[i].indexOf(begin) > -1) {
beginIn = resultList[i];
}
if (resultList[i].indexOf(end) > -1) {
endIn = resultList[i];
}
}
// 两个点都是新的点（都不在任何部落里）——可以连接
if (beginIn === null && endIn === null) {
let newArr = [];
newArr.push(begin, end);
resultList.push(newArr);
} else if (beginIn !== null && endIn === null) {
// begin在A部落，end没有部落 ——A部落扩张一个村落
beginIn.push(end);
} else if (beginIn === null && endIn !== null) {
// end在A部落，begin没有部落 ——A部落扩张一个村落
endIn.push(begin);
} else if (beginIn !== null && endIn !== null && beginIn !== endIn) {
// begin在A部落，end在B部落 ——将AB部落合并
allIn = beginIn.concat(endIn);
let removeIndex = resultList.indexOf(endIn);
resultList.splice(removeIndex, 1);
let removeIndex1 = resultList.indexOf(beginIn);
resultList.splice(removeIndex1, 1);
resultList.push(allIn);
}
// begin和end在同一个部落 ——不可以连接
begin.neighbor.push(end);
end.neighbor.push(begin);
}
/**
* 克鲁斯卡尔算法
* @param {*} pointSet 原始节点集
* @param {*} distance 原始距离集
*/
function kruskal(pointSet, distance) {
let resultList = []; //这里是一个二维数组，此数组代表的长度有多少个"部落"
while (true) {
let minDis = max;
let begin = null;
let end = null;
for (let i = 0; i < distance.length; i++) {
for (let j = 0; j < distance[i].length; j++) {
let tempBegin = pointSet[i];
let tempEnd = pointSet[j];
if (i !== j && distance[i][j] < minDis &&
canLink(resultList, tempBegin, tempEnd)) {
minDis = distance[i][j];
begin = tempBegin;
end = tempEnd;
}
}
}
link(resultList, begin, end);
if (resultList.length === 1 &&
resultList[0].length === pointSet.length) {
//当仅有一个部落，且该部落中的节点树与原始节点集的长度相等，则跳出循环
break;
}
}
return resultList;
}
console.log(kruskal(pointSet, distance));
二叉搜索树
二叉搜索树也叫二叉排序树
首先，这是一棵二叉树，其次有排序的效果，左子树的节点都比当前节点小，右子树的节点都比当前节点大
构建二叉搜索树
function buildSearchTree(arr) {
if (arr === null || arr.length === 0) return null;
let root = new Node(arr[0]);
for (let i = 1; i < arr.length; i++) {
addNode(root, arr[i]);
}
return root;
}
function addNode(root, 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 searchByTree(root, target) {
if (root === null) return false;
if (root.value === target) return true;
if (root.value > target) return searchByTree(root.left, target);
if (root.value < target) return searchByTree(root.right, target);
}
平衡二叉树
1、根节点的左子树与右子树的高度差不能超过1
2、这棵二叉树的每个子树都符合第一条
代码实现
function Node(value){
this.value = value;
this.left = null;
this.right = null;
}
let a = new Node("a");
let b = new Node("b");
let c = new Node("c");
let d = new Node("d");
let e = new Node("e");
let f = new Node("f");
let g = new Node("g");
let h = new Node("h");
let j = new Node("j");
a.left = b;
a.right = c;
b.left = d;
b.right = e;
c.left = f;
c.right = g;
d.right = h;
e.right = j;
//获取二叉树的最大深度
function getDeep(root){
if(root === null)return 0;
let leftDeep = getDeep(root.left);
let rightDeep = getDeep(root.right);
return Math.max(leftDeep, rightDeep) + 1;
}
//通过递归判断根节点及其所有子树是否为平衡二叉树
function isBalance(root) {
if(root === null){
return true;
}
//得到当前节点左右子树的度并判断差值是否大于1
let leftDeep = getDeep(root.left);
let rightDeep = getDeep(root.right);
if(Math.abs(leftDeep - rightDeep) > 1){
return false
}else{
//若当前节点平衡，判断其左右子树分别是否平衡
return isBalance(root.left) && isBalance(root.right);
}
}
二叉树的单旋
左单旋和右单旋
注：二叉树的旋转从子树开始
某一节点不平衡，如果左边浅，右边深，进行左单旋
旋转节点：不平衡的节点为旋转节点（2）
新根：旋转之后称为根节点的节点（5）
变化分支：父级节点发生变化的那个分支
不变分支：父级节点不变的那个分支
左单旋时：
旋转节点：当前不平衡的节点（2）
新根：右子树的根节点（5）
变化分支：右子树的左子树（3）
不变分支：右子树的右子树（6）
以上图为例，左旋之后即为以下效果
进行左单旋：
1、找到新根（5）
2、找到变化分支（3）
3、当前旋转节点的右孩子为变化分支（2.right = 3）
4、新根的左孩子为旋转节点（5.left = 2）
5、返回新的根节点（5）
//左旋
function leftRotate(root){
//找到新根
let newRoot = root.right;
//找到变化分支
let changeRoot = newRoot.left;
//新根的左孩子为旋转节点
root.right = changeRoot;
//新根的左孩子为旋转节点
newRoot.left = root;
//返回新的根节点
return newRoot;
}
右单旋时：
旋转节点：当前不平衡的节点（6）
新根：左子树的根节点（3）
变化分支：左子树的右子树（5）
不变分支：左子树的左子树（2）
进行右单旋：
1、找到新根（3）
2、找到变化分支（5）
3、当前旋转节点的左孩子为变化分支（6.left = 5）
4、新根的右孩子为当前旋转节点（3.right = 6）
5、返回新根节点
//右旋
function rightRotate(root){
let newRoot = root.left;
let changeRoot = newRoot.right;
root.right = changeRoot;
newRoot.right = root;
return newRoot;
}
以上图为例，右单旋之后即为以下效果
function Node(value) {
this.value = value;
this.left = null;
this.right = null;
}
let node2 = new Node("2");
let node5 = new Node("5");
let node3 = new Node("3");
let node6 = new Node("6");
node2.right = node5;
node5.left = node3;
node5.right = node6;
//获取二叉树的最大深度
function getDeep(root) {
if (root === null) return 0;
let leftDeep = getDeep(root.left);
let rightDeep = getDeep(root.right);
return Math.max(leftDeep, rightDeep) + 1;
}
function isBalance(root) {
if(root === null){
return true;
}
let leftDeep = getDeep(root.left);
let rightDeep = getDeep(root.right);
if(Math.abs(leftDeep - rightDeep) > 1){
return false
}else{
return isBalance(root.left) && isBalance(root.right);
}
}
//首先判断root是否为平衡二叉树，如果是，则直接返回root
//判断左右子树是否为空，若不为空，则采用递归的方式旋转子树，递归遵循栈原则，先进后出，因此这里相当于自底向上进行单旋，即中序遍历的顺序，当递归到叶子节点时，计算左右子树的深度，并判断节点树是否平衡，若不平衡，左边深则需要右旋，右边深则需要左旋
//以左单旋为例，单旋过程为：先找到新根（newRoot = root.right），找到变化分支（changeRoot = newRoot.left），将变化分支变为旧根的右子树（root.right = changeRoot），将旧根变为新根的左子树（newRoot.left = root），最后返回新根，即为单旋过后的根节点
//判断并旋转树，使其成为平衡二叉树
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);
}
//计算左右子树的深度
let leftDeep = getDeep(root.left);
let rightDeep = getDeep(root.right);
//当前节点树平衡，直接返回
if(Math.abs(leftDeep - rightDeep) < 2){
return true;
}else if(leftDeep > rightDeep){
//不平衡，左边深，需要右旋
return rightRotate(root);
}else{
//不平衡，右边深，需要左旋
return leftRotate(root);
}
}
//左旋
function leftRotate(root){
//找到新根
let newRoot = root.right;
//找到变化分支
let changeRoot = newRoot.left;
//当前旋转节点的右孩子为变化分支
root.right = changeRoot;
//新根的左孩子为旋转节点
newRoot.left = root;
//返回新的根节点
return newRoot;
}
//右旋
function rightRotate(root){
let newRoot = root.left;
let changeRoot = newRoot.right;
root.right = changeRoot;
newRoot.right = root;
return newRoot;
}
let newRoot = change(node2);
console.log(isBalance(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);
}
let leftDeep = getDeep(root.left);
let rightDeep = getDeep(root.right);
if (Math.abs(leftDeep - rightDeep) < 2) {
return root;
} else if (leftDeep > rightDeep) {
//不平衡，左边深，需要右旋
let changeRootDeep = getDeep(root.left.right);
let noChangeRootDeep = getDeep(root.left.left);
if (changeRootDeep > noChangeRootDeep) {
root.left = leftRotate(root.left);
}
return rightRotate(root);
} else {
//不平衡，右边深，需要左旋
let changeRootDeep = getDeep(root.right.left);
let noChangeRootDeep = getDeep(root.right.right);
if (changeRootDeep > noChangeRootDeep) {
root.right = rightRotate(root.right);
}
return leftRotate(root);
}
return root;
}
左左双旋、右右双旋
如果变化分支的高度比旋转节点的另一侧高度差距超过2，那么单旋之后依然不平衡
核心思路：当进行右（左）旋之后，右（左）侧分支可能会变得不平衡，因此需对右（左）侧分支再进行判断旋转，旋转过后，再次判断当前旋转树是否平衡，最后返回旋转后的根节点
//二叉树的双旋
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);
}
let leftDeep = getDeep(root.left);
let rightDeep = getDeep(root.right);
if (Math.abs(leftDeep - rightDeep) < 2) {
return root;
} else if (leftDeep > rightDeep) {
//不平衡，左边深，需要右旋
let changeRootDeep = getDeep(root.left.right);
let noChangeRootDeep = getDeep(root.left.left);
if (changeRootDeep > noChangeRootDeep) {
root.left = leftRotate(root.left);
}
let newRoot = rightRotate(root);
newRoot.right = change(newRoot.right);
newRoot = change(newRoot);
return newRoot;
} else {
//不平衡，右边深，需要左旋
let changeRootDeep = getDeep(root.right.left);
let noChangeRootDeep = getDeep(root.right.right);
if (changeRootDeep > noChangeRootDeep) {
root.right = rightRotate(root.right);
}
let newRoot = leftRotate(root);
newRoot.left = change(newRoot.left);
newRoot = change(newRoot);
return newRoot;
}
return root;
}
234树
树的层级越少，查找效率越高，234树便是为提升效率而产生的
234树：我们希望有一棵树，最多有四个叉（度为4）
234树子节点永远在最后一层，即永远是平衡树（每一个路径高度都相同）
因为分支多了，所以复杂度上升了，希望多二三四树进行简化。（依旧保留多叉，依旧单节点中存放多个值）
红黑树
性质1：节点是红色或黑色
性质2：根节点是黑色
性质3：每个红色节点的两个子节点都是黑色（从每个叶子到根的所有路径上不能有两个利阿努的红色节点）
性质4：从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点
树的深度优先搜索
function Node(value){
this.value = value;
this.children = [];
}
function deepSearch(root, target){
if(root === null)return false;
if(root.value === target){
return true;
}
let result = false;
for(let i = 0; i < root.children; i++){
result |= deepSearch(root.children[i], target);
}
return result;
}
树的广度优先搜索
function rangeSearch(roots, target){
if(roots === null || roots.length === 0)return false;
let children = [];
for(let i = 0; i < roots.length; i++){
if(roots[i].value === target){
return true;
}else{
children = children.concat(roots[i].children);
}
}
return rangeSearch(children, target);
}
图的深度优先搜索
function Node(value){
this.value = value;
this.neighbor = [];
}
function dfs(node, target, path){
if(node === null) return false;
if(path.indexOf(node) > -1)return false;
path.push(node);
if(node.value === target) return true;
let result = false;
for(let i = 0; i < node.neighbor.length; i++){
result |= dfs(node.neighbor[i], target, path);
}
return result;
}
console.log(dfs(b, "c", []));
图的广度优先搜索
function Node(value){
this.value = value;
this.neighbor = [];
}
function bfs(nodes, target, path){
if(nodes === null || nodes.length === 0) return false;
let nextNodes = [];
for(let i = 0; i < nodes.length; i++){
if(path.indexOf(nodes[i]) > -1)continue;
path.push(nodes[i]);
if(nodes[i].value === target)return true;
else{
nextNodes = nextNodes.concat(nodes[i].neighbor);
}
}
return bfs(nextNodes, target, path);
}
console.log(bfs(b, "c", []));
动态规划之斐波那契
传统解法
function fib(n){
if(n <= 0)return -1;
if(n === 1)return 0;
if(n === 2)return 1;
let a = 0;
let b = 1;
let c;
for(let i = 3; i <= n; i++){
c = a + b;
a = b;
b = c;
}
return c;
}
function fib(n){
if(n <= 0)return -1;
if(n === 1)return 0;
if(n === 2)return 1;
return fib(n - 1) + fib(n - 2);
}
青蛙跳台阶问题
问题：一个青蛙，一次只能跳一级台阶，或者跳两级台阶，问这个青蛙跳上n级台阶有多少种跳法
如果这只青蛙，跳上了n级台阶，那么最后一次跳跃之前，他一定在n-1级台阶或n-2级台阶上，这样跳上n级台阶有多少种情况就变成了两个子问题
即跳上n - 1级台阶的跳法加上跳上n - 2级台阶的跳法
function jump(n){
if(n <= 0)return -1;
if(n === 1)return 1;
if(n === 2)return 2;
return jump(n - 2) + jump(n - 1);
}
变态青蛙跳台阶问题
问题：这只青蛙一次可以跳1级台阶，2级台阶或者n级台阶，问这只青蛙跳上n级台阶有多少种方法？
function jump(n){
if(n === 0)return -1;
if(n === 1)return 1;
if(n === 2)return 2;
let result = 0;
for(let i = 1; i < n; i++){
result += jump(n - i);
}
return result + 1;
}
若有收获，就点个赞吧
0 人点赞
