一、數(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、選擇排序

在未排序序列中找到最?。ù螅┰?，存放到排序序列的起始位置，然后，再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最?。ù螅┰兀缓蠓诺揭雅判蛐蛄械哪┪?。

3、快速排序

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

//判斷數(shù)組長(zhǎng)度是否小于等于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，對(duì)已排序數(shù)組從后往前進(jìn)行比較，將temp放到它本該在的位置

                //遍歷i，把第i項(xiàng)的值存起來(lái)
                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

三、二叉樹(shù)

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

數(shù)據(jù)結(jié)構(gòu) : 棧，后進(jìn)先出，用pop()
壓棧順序，先壓右子樹(shù)，再壓左子樹(shù)

    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()
入列順序，先入左子樹(shù)，再入右子樹(shù)

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

首先我們需要定義一個(gè)Node類，存儲(chǔ)自身的值和對(duì)兩個(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)
            }
        }
    }
}