一、数组去重的几种方法
1、利用indexof
2、[...new set()]
二、排序算法
1、冒泡O(n^2)
for(i=0){
for(j=i+1){
//从小到大排
//把大的放到后面
if(arr[i]>arr[j]){交换位置}
//从大到小排,把小的放到后面
if(arr[i]<arr[j]){交换位置}
}
}
2、选择排序
在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
3、快速排序
拿到一个基准点，把比它小的数放到leftArr，比他大的放到rightArr，递归，直到leftArr长度为1
//判断数组长度是否小于等于1，如果是，则直接返回arr
if (arr.length <= 1) {
return arr;
}
//拿到基准点
let temp = arr.splice(midIndex, 1)[0]
//递归调用
return quickSort(leftArr).concat([temp],quickSort(rightArr))
4、插入排序
默认是一个未排序的数组，再建一个已排序数组，从未排序数组中依次取数temp，对已排序数组从后往前进行比较，将temp放到它本该在的位置
//遍历i，把第i项的值存起来
let temp = arr[i];
let j = i - 1;
while (j >= 0 && arr[j] > temp) {
//如果前一个数大于后一个数,将前一个数往后移一位
arr[j + 1] = arr[j]
j--
}
//此时的j是要处理的数排序后应该在的位置
arr[j+1] = temp
三、二叉树
1、深度优先遍历
数据结构 : 栈，后进先出，用pop()
压栈顺序，先压右子树，再压左子树
let stack = [];
stack.push(biTree);
while (stack.length != 0) {
let node = stack.pop();
console.log(node.data);
if (node.rChild) {
stack.push(node.rChild);
}
if (node.lChild) {
stack.push(node.lChild);
}
}
2、广度优先遍历
数据结构 : 队列，先进先出，用shift()
入列顺序，先入左子树，再入右子树
3、前序遍历
数据结构:栈
使用两个while循环，大循环保证遍历到所有节点，小循环是不断进行向左深入
preOrder2() {
var node = this.root
var arr = []
var stack = []
while (node !== null || stack.length > 0) {
while (node !== null) {
stack.push(node)
arr.push(node.data)
node = node.left
}
//出来的时候node的左树已经遍历完了，此时是null
if (stack.length > 0) {
node = stack.pop()
node = node.right
}
//出来后回到大循环的开始，又进入第一个小循环遍历左树
}
return arr
}
4、中序遍历
只需要将arr.push(node.data)换个位置即可
if (stack.length > 0) {
node = stack.pop()
arr.push(node.data)
node = node.right
}
5、后序遍历
将前序遍历的arr.push(node.data)换成arr.unshift(node.data)
while (node !== null) {
stack.push(node)
arr.unshift(node.data) //最先接触到的节点最后才会被插入数组
node = node.left
}
5、创建二叉树
首先我们需要定义一个Node类，存储自身的值和对两个儿子的指针
并且定义有一个插入节点的方法
class Node {
constructor(data) {
this.data = data
this.left = null
this.right = null
}
insertNode(newNode) {
if (newNode.data < this.data) {
if (this.left === null) { this.left = newNode }
else {
this.left.insertNode(newNode)
}
}
else {
if (this.right === null) { this.right = newNode }
else {
this.right.insertNode(newNode)
}
}
}
}
