一、數(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、快速排序

拿到一個基準點，把比它小的數(shù)放到leftArr，比他大的放到rightArr，遞歸，直到leftArr長度為1

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

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

4、插入排序

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

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

三、二叉樹

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

數(shù)據(jù)結(jié)構(gòu) : 棧，后進先出，用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) : 隊列，先進先出，用shift()
入列順序，先入左子樹，再入右子樹

3、前序遍歷

數(shù)據(jù)結(jié)構(gòu):棧
使用兩個while循環(huán)，大循環(huán)保證遍歷到所有節(jié)點，小循環(huá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
        }
        //出來的時候node的左樹已經(jīng)遍歷完了，此時是null
        if (stack.length > 0) {
            node = stack.pop()
            node = node.right
        }
        //出來后回到大循環(huán)的開始，又進入第一個小循環(huán)遍歷左樹
    }
    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)  //最先接觸到的節(jié)點最后才會被插入數(shù)組
            node = node.left
 }

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

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

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