一、數(shù)組去重的幾種方法

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顽分、選擇排序

在未排序序列中找到最小（大）元素施蜜，存放到排序序列的起始位置卒蘸，然后，再從剩余未排序元素中繼續(xù)尋找最蟹（大）元素缸沃，然后放到已排序序列的末尾。

3修械、快速排序

拿到一個(gè)基準(zhǔn)點(diǎn)趾牧，把比它小的數(shù)放到leftArr，比他大的放到rightArr肯污，遞歸翘单，直到leftArr長度為1

//判斷數(shù)組長度是否小于等于1，如果是蹦渣，則直接返回arr
if (arr.length <= 1) {  
    return arr;
}

//拿到基準(zhǔn)點(diǎn)
let temp = arr.splice(midIndex, 1)[0]
//遞歸調(diào)用
return quickSort(leftArr).concat([temp],quickSort(rightArr))

4哄芜、插入排序

默認(rèn)是一個(gè)未排序的數(shù)組，再建一個(gè)已排序數(shù)組剂桥，從未排序數(shù)組中依次取數(shù)temp忠烛，對已排序數(shù)組從后往前進(jìn)行比較，將temp放到它本該在的位置

                //遍歷i权逗，把第i項(xiàng)的值存起來
                let temp = arr[i];
                let j = i - 1;
                while (j >= 0 && arr[j] > temp) {
                    //如果前一個(gè)數(shù)大于后一個(gè)數(shù),將前一個(gè)數(shù)往后移一位
                    arr[j + 1] = arr[j]
                    j--
                }
                //此時(shí)的j是要處理的數(shù)排序后應(yīng)該在的位置
                arr[j+1] = temp

三美尸、二叉樹

1、深度優(yōu)先遍歷

數(shù)據(jù)結(jié)構(gòu) : 棧斟薇，后進(jìn)先出师坎，用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胯陋、廣度優(yōu)先遍歷

數(shù)據(jù)結(jié)構(gòu) : 隊(duì)列，先進(jìn)先出，用shift()
入列順序遏乔，先入左子樹义矛，再入右子樹

3、前序遍歷

數(shù)據(jù)結(jié)構(gòu):棧
使用兩個(gè)while循環(huán)盟萨，大循環(huán)保證遍歷到所有節(jié)點(diǎn)凉翻，小循環(huán)是不斷進(jìn)行向左深入

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
        }
        //出來的時(shí)候node的左樹已經(jīng)遍歷完了，此時(shí)是null
        if (stack.length > 0) {
            node = stack.pop()
            node = node.right
        }
        //出來后回到大循環(huán)的開始捻激，又進(jìn)入第一個(gè)小循環(huán)遍歷左樹
    }
    return arr
}

4制轰、中序遍歷

只需要將arr.push(node.data)換個(gè)位置即可

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)  //最先接觸到的節(jié)點(diǎn)最后才會(huì)被插入數(shù)組
            node = node.left
 }

5胞谭、創(chuàng)建二叉樹

首先我們需要定義一個(gè)Node類垃杖，存儲(chǔ)自身的值和對兩個(gè)兒子的指針
并且定義有一個(gè)插入節(jié)點(diǎn)的方法

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)
            }
        }
    }
}