四種：集合結(jié)構(gòu)，線性結(jié)構(gòu)，樹形結(jié)構(gòu)，圖形結(jié)構(gòu)

• 集合結(jié)構(gòu)：數(shù)據(jù)元素同屬于一個結(jié)合，他們之間沒有其他的關(guān)系。它們的共同屬性是：同屬于一個集合
• 線性結(jié)構(gòu)：最典型的數(shù)據(jù)關(guān)系是一對一。線性結(jié)構(gòu)是一種有序數(shù)據(jù)的集合。
  • 數(shù)組：就是一個線性結(jié)構(gòu)，棧，隊(duì)列，F(xiàn)ILO
• 樹形結(jié)構(gòu)：數(shù)據(jù)元素是一對多，例如dom樹

• 圖形結(jié)構(gòu)：數(shù)據(jù)元素是多對多

  
  
  1.png

2.png

3.png

4.png

物理結(jié)構(gòu)：數(shù)據(jù)元素存儲到計(jì)算中的存儲器，針對內(nèi)存而言的
數(shù)據(jù)的存儲結(jié)構(gòu)應(yīng)該正確的反應(yīng)數(shù)據(jù)元素之間的邏輯關(guān)系
順序存儲，鏈?zhǔn)酱鎯?/p>

5.png

6.png

7.png

數(shù)組

js的數(shù)組不是真正意義上的數(shù)組；
數(shù)組：再內(nèi)存中用一串連續(xù)的區(qū)域來存放一些值。
數(shù)組是相同類型數(shù)據(jù)元素的集合(js的數(shù)組可以存儲不同類型)；
而且一般數(shù)組的容量是不會自動變化的
數(shù)組內(nèi)存地址是連續(xù)的，但是js中的內(nèi)存地址是不連續(xù)，原因是數(shù)據(jù)類型可以是任意類型導(dǎo)致的

數(shù)組的優(yōu)點(diǎn)：

1. 按照索引查詢元素的時候速度很快
2. 存儲大兩的數(shù)據(jù)
3. 按照索引去遍歷數(shù)組
4. 定義方便，訪問靈活

數(shù)組的缺點(diǎn)：

1. 根據(jù)內(nèi)容查找會很慢
2. 數(shù)組的大小一經(jīng)確定是不能改變的，不適合動態(tài)存儲
3. 數(shù)組只能存儲相同類型數(shù)據(jù)
4. 增加刪除元素效率慢，因?yàn)閮?nèi)存地址是連續(xù)的

棧

內(nèi)存區(qū)域：棧區(qū)
單片機(jī)：壓棧
數(shù)據(jù)結(jié)構(gòu)中有一個同名的數(shù)據(jù)結(jié)構(gòu)，棧

內(nèi)存中的堆棧和數(shù)據(jù)結(jié)構(gòu)中的堆棧不是一個概念，內(nèi)存中的堆棧是真實(shí)存在的物理區(qū)，數(shù)據(jù)結(jié)構(gòu)中的堆棧是抽象數(shù)據(jù)存儲結(jié)構(gòu)

棧：是一種受限制的線性表，LIFO
其限制是僅允許再表的一端進(jìn)行插入和刪除運(yùn)算，這一端被稱為棧頂，相對的，把另一端稱為棧底
向一個棧插入新元素被稱為進(jìn)棧，入棧，壓棧，它是把新元素放到棧頂元素的上面，使之成為新的棧頂元素
從一個棧刪除元素又稱作出?；蛲藯＃前褩ｍ斣貏h除掉，使其相鄰的元素成為新的棧頂元素

棧的應(yīng)用：十進(jìn)制轉(zhuǎn)二進(jìn)制

8.png

當(dāng)時js中有內(nèi)置api實(shí)現(xiàn)，但是此處只是說明一個應(yīng)用場景

class Stack {
    constructor() {
        this.items = [];
    }
    push(ele) {
        this.items.push(ele);
    }

    pop() {
        return this.items.pop();
    }
    //返回棧頂元素
    peek() {
        return this.items[this.items.length - 1];
    }
    //判斷棧中元素是否為空
    isEmpty(){
        return this.items.length==0;
    }
    size() {
        return this.items.length;
    }
    clear() {
        this.items=[];
    }
}

const binary = number => {
    let stack = new Stack();
    let remainder = 0;
    let top = '';
    while (number > 0) {
        //除以2取余數(shù)
        remainder = number % 2;
        stack.push(remainder);
        //向下取整
        number=Math.floor(number/2);
    }

    //不為空的時候
    while (!stack.isEmpty()) {
        //棧頂元素
        top+=stack.top();
    }
    return top;
}

JS 調(diào)用棧：

參考網(wǎng)址:https://www.cnblogs.com/shuajing/p/10800656.html

前置說明：
1 JavaScript 是一門單線程的語言，這意味著它只有一個調(diào)用棧，因此，它同一時間只能做一件事。
2 內(nèi)存堆：這是內(nèi)存分配發(fā)生的地方.
3 調(diào)用棧：這是你的代碼執(zhí)行時的地方

定義：調(diào)用棧是解釋器（就像瀏覽器中的javascript解釋器）追蹤函數(shù)執(zhí)行流的一種機(jī)制。當(dāng)執(zhí)行環(huán)境中調(diào)用了多個函數(shù)時，通過這種機(jī)制，我們能夠追蹤到哪個函數(shù)正在執(zhí)行，執(zhí)行的函數(shù)體中又調(diào)用了哪個函數(shù)。
1. 每調(diào)用一個函數(shù)，解釋器就會把該函數(shù)添加進(jìn)調(diào)用棧并開始執(zhí)行。
2 正在調(diào)用棧中執(zhí)行的函數(shù)還調(diào)用了其它函數(shù)，那么新函數(shù)也將會被添加進(jìn)調(diào)用棧，一旦這個函數(shù)被調(diào)用，便會立即執(zhí)行。
3 當(dāng)前函數(shù)執(zhí)行完畢后，解釋器將其清出調(diào)用棧，繼續(xù)執(zhí)行當(dāng)前執(zhí)行環(huán)境下的剩余的代碼。
4 當(dāng)分配的調(diào)用?？臻g被占滿時，會引發(fā)“堆棧溢出”

函數(shù)的調(diào)用本質(zhì)："壓棧和出棧操作"，但是函數(shù)在調(diào)用棧里面有一個特例，叫做遞歸
遞歸：自己調(diào)用自己，先進(jìn)棧，如果不出棧，就會導(dǎo)致：棧溢出

斐波那契數(shù)列：從第三項(xiàng)開始，每一項(xiàng)都等于前兩項(xiàng)的和1 1 2 3 5 8 13

當(dāng)數(shù)值很大的時候，計(jì)算斐波那契數(shù)列會出現(xiàn)計(jì)算慢(因?yàn)橛兄貜?fù)計(jì)算，函數(shù)多同時也會導(dǎo)致調(diào)用棧過多)調(diào)用棧溢出，解決方案是尾遞歸優(yōu)化

• 尾調(diào)用

尾調(diào)用自身就是尾遞歸

//函數(shù)b的尾部調(diào)用a函數(shù)，被稱為尾調(diào)用
function a(x) {}
function b(x){
    return a(x);
}



b(x);
實(shí)際上就是調(diào)用a(x);
可以看成沒有外部調(diào)用幀


如果a就是b本身的話，即使有很多層調(diào)用，因?yàn)槲策f歸優(yōu)化，實(shí)際上不會像常規(guī)調(diào)用一樣，幀一層套一層；
總共只有一個調(diào)用幀，避免了調(diào)用棧溢出

const factor=(n,total)=>{
    if (n==1) {
        return total;
    }
    return factor(n-1,n*total);
}

優(yōu)化斐波那契數(shù)列

//原始案例
const Fibonacci = (n) => {
    if (n <= 1) {
        return 1;
    }
    return Fibonacci(n - 1)+Fibonacci(n-2);
}

//優(yōu)化案例
//把前面兩位數(shù)當(dāng)作參數(shù)傳遞進(jìn)來
//此處沒有利用常規(guī)緩存函數(shù)計(jì)算結(jié)果，而是直接緩存上次總體計(jì)算結(jié)果；實(shí)際上也是利用了緩存
//遞歸需要同時保存成百上千個調(diào)用幀，很容易發(fā)生棧溢出，而且因?yàn)槲策f歸優(yōu)化，只有一個調(diào)用棧，永遠(yuǎn)不會棧溢出
const Fibonacci = (n, ac1 = 1, ac2 = 2) => {
    if (n <= 1) {
        return ac2;
    }
    return Fibonacci(n - 1, ac2, ac1 + ac2);
}
console.log(Fibonacci(50,1,1));

隊(duì)列

• 是一種受限的線性表，F(xiàn)IFO

• 受限之處：它只允許表的前端進(jìn)行刪除操作，在表的后端進(jìn)行增加操作

  
  
  9.png

class Quenue{
    constructor(){
        this.items= [];
    }
    //入隊(duì)
    enqueue(item){
        this.items.push(item);
    }
    //出隊(duì)操作
    dequeue(){
        return this.items.shift();
    }
    //查看隊(duì)首元素
    front() {
        return this.items[0];
    }
    //查看對尾
    rear() {
        return this.items[this.items.length-1];
    }
    //是否為空
    isEmpty(){
        return this.items.length===0;
    }
    size(){
        return this.items.length;
    }
    clear(){
        this.items=[];
    }
}

• JS的異步隊(duì)列
  js為什么是單線程：完成與用戶交互以及dom操作；一個線程添加dom一個刪除dom，瀏覽器聽誰的，避免復(fù)雜性所以直接單線程
• 主線程執(zhí)行完畢之后，從事件隊(duì)列中讀取任務(wù)隊(duì)列的過程，稱之為事件循環(huán)(EventLoop)
• Promise是同步的，then和catch是異步的

Promise補(bǔ)充：必須查看 https://segmentfault.com/a/1190000020980101

new Promise((resolve, reject) =>{
    resolve();
}).then(() =>{

})

Promise.resolve()


https://segmentfault.com/a/1190000020980101

任務(wù)隊(duì)列：存在著兩個隊(duì)列，一個宏任務(wù)一個微任務(wù)隊(duì)列

主線程：同步任務(wù)->微任務(wù)->宏任務(wù)

promise.then catch finally process.nexttick是微任務(wù)，
I/O,定時器，ajax,事件綁定是宏任務(wù)

鏈表

例如原型鏈

10.png

鏈表就可以解決這樣的問題

11.png

1. 插入刪除：鏈表的性能好
   鏈表沒有大小限制，支持動態(tài)擴(kuò)容，因?yàn)殒湵淼拿總€節(jié)點(diǎn)都需要存儲前驅(qū)/后驅(qū)節(jié)點(diǎn)的指針，內(nèi)存消耗會翻倍
2. 查詢修改：數(shù)組性能好

class Node {
    constructor(element){
        this.element = element;
        this.next=null;
    }
}
//鏈表
class LinkedList{
    constructor(){
        //鏈表頭
        this.head=null;
        //鏈表長度
        this.length=0;
    }
    //1.鏈表的尾部追加元素
    append(element){
        let node=new Node(element);
        //如果鏈表空的
        if (this.length===0){
            this.head=node;
        }else{
            //通過head找到后面的節(jié)點(diǎn)
            let current=this.head;
            //遍歷,是否是最后一個節(jié)點(diǎn),next為空就是最后一個
            while (current.next){
                current=current.next;
            }
            //while執(zhí)行完畢之后，current就已經(jīng)是最后一個節(jié)點(diǎn)了
        }
        current.next=node;
        this.length+=1;
    }
    getHead(){
        return this.head;
    }

    toString(){
        let current=this.head;
        let linkString='';
        while(current){
            linkString+=','+current.element;
            current=current.next;
        }
        return linkString.slice(1);
    }
    //任意位置插入元素
    insert(element,positon){
        //位置不能實(shí)負(fù)數(shù)
        if (positon<0||position>this.length) {
            return false;
        }

        let index=0;
        let current=this.head;
        let previous=null;
        let node=new Node(element);
        //判斷插入的是不是第一個
        if (position===0) {
            node.text=this.head;
            this.head=node;
        }else{
            while (index<positon) {
                previous=current;
                current=current.next;
                index++;
            }
            node.next=current;
            previous.next=node;
        }
        this.length+=1;
        return true;
    }

    get(positon){
        if (positon<0||positon>this.length) {
            return null
        }
        let current=this.head;
        let index=0;
        while (index<positon) {
            current=current.next;
            index++;
        }
        return current.element;
    }
// ......實(shí)際上還有代碼，此處省略
}

prototype和proto

1. 所有的引用類型(數(shù)組，函數(shù)，對象)可以自由的擴(kuò)展屬性(null除外)
2. 所有的引用類型都有一個proto屬性(隱式原型，它其實(shí)就是一個普通的對象)
3. 所有的函數(shù)都有一個prototype屬性(顯式原型，也是一個普通對)
4. 所有的引用類型的proto屬性都指向它的構(gòu)造函數(shù)的prototype屬性
5. 當(dāng)試圖得到一個對象的屬性時，如果這個對象的本身不存在這個屬性，那么就會去它的proto屬性中找(去它的構(gòu)造函數(shù)的prototype屬性中去尋找)
6. 當(dāng)調(diào)用這個對象本身并不存在的屬性或者方法時，它會一層層的往上找，一直找到null為止，null表示空的對象{}

案例

• 案例一

//構(gòu)造函數(shù)
function Teacher(name, habby) {
    this.name = name;
    this.habby = habby;
    this.show = function () {
        console.log(1111);
    }
}

var t1 = new Teacher('t1', '哈哈哈哈');
var t2 = new Teacher('t2', '呵呵呵呵');
/**
 * Teacher它就是一個普通函數(shù)但是這個函數(shù)的作用：構(gòu)造對象
 * 這種構(gòu)造對象的方式：工廠方式
 */

//這樣new多少次show就有多少個
console.log(t1.show === t2.show);//false

• 案例二

//構(gòu)造函數(shù)
function Teacher(name, habby) {
    this.name = name;
    this.habby = habby;
    this.show = fun
}
function fun() {
    console.log(1111);
}
var t1 = new Teacher('t1', '哈哈哈哈');
var t2 = new Teacher('t2', '呵呵呵呵');
console.log(t1.show === t2.show);//true
// 這樣存在問題，容易導(dǎo)致全局作用域的污染，并且數(shù)據(jù)是不安全的容易被覆蓋，例如后面還有一個同名的fun函數(shù)

• 案例三

//如下
function Teacher(name, habby) {
    this.name = name;
    this.habby = habby;
}
//Teacher就是構(gòu)造函數(shù)，其內(nèi)部有prototype屬性，而__proto__又會指向構(gòu)造函數(shù)的prototype屬性
//Teacher.prototype是一個普通對象，這個對象的構(gòu)造函數(shù)是Object
Teacher.prototype.show = function(){
    console.log(1111);
}
console.log(Teacher.prototype.__proto__===Object.prototype);//true

12.png

• 原型鏈繼承

function Teacher(name, habby) {
    this.name = name;
    this.habby = habby;
    this.show = function () {
        console.log(1111);
    }
}
//構(gòu)造方法是空的
function  Tt() {}


Tt.prototype = new Teacher('t1', '哈哈哈哈');
var t=new Tt();
t.show();

哈希表

MD5是目前應(yīng)用最廣泛的Hash算法，但是并不是唯一的算法

13.png

14.png

15.png

16.png

class HashTable {
    constructor() {
        this.table = [];//哈希表
    }
    //哈希函數(shù):這只是一個很簡化版的
    loseloseHashCode(key) {
        let hash = 0;
        for (let i = 0; i < key.length; i++) {
            hash += key[i].charCodeAt();//計(jì)算key   unicode碼

        }
        //取模
        return hash % 37;//37是質(zhì)數(shù)，可以很大程度上避免碰撞
    }
    //新增元素
    put(key, value) {
        //獲取key
        const position = this.loseloseHashCode(key);
        this.table[position] = value;
    }
    //移除元素
    remove(key) {
        this.table[this.loseloseHashCode(key)]=undefined;
    }
    //獲取元素
    get(key) {
        return this.table[this.loseloseHashCode(key)];
    }
}

const a=new HashTable();
a.put('zq',"zq@qq.com");
console.log(a);//HashTable { table: [ <13 empty items>, 'zq@qq.com' ] }    
//由上面輸出可知，有很多空項(xiàng)，是因?yàn)榇藭r索引不是數(shù)字的，所以前面可能存在空項(xiàng)
console.log(a.get('zq'));

• 碰撞

數(shù)組里面，如果數(shù)組的下標(biāo)相同，后邊添加的就會覆蓋前面的，這個叫覆蓋；

哈希表：沖突，碰撞，對于不同的要存儲的數(shù)據(jù)經(jīng)過哈希函數(shù)得到的索引有可能相同

const arr = [];
arr[1] = 'zq';
arr[1] = 'zq1';
//數(shù)組會覆蓋
console.log(arr); //[ <1 empty item>, 'zq1' ]

const loseloseHashCode = (key) => {
    let hash = 0;
    for (let i = 0; i < key.length; i++) {
        hash += key[i].charCodeAt();
    }
    return hash % 37;
}
console.log(loseloseHashCode('money'));//34
console.log(loseloseHashCode('oxgbx'));//34

class HashTable {
    constructor() {
        this.table = [];//哈希表
    }
    //哈希函數(shù):這只是一個很簡化版的
    loseloseHashCode(key) {
        let hash = 0;
        for (let i = 0; i < key.length; i++) {
            hash += key[i].charCodeAt();//計(jì)算key   unicode碼

        }
        //取模
        return hash % 37;//37是質(zhì)數(shù)，可以很大程度上避免碰撞
    }
    //新增元素
    put(key, value) {
        //獲取key
        const position = this.loseloseHashCode(key);
        this.table[position] = value;
    }
    //移除元素
    remove(key) {
        this.table[this.loseloseHashCode(key)]=undefined;
    }
    //獲取元素
    get(key) {
        return this.table[this.loseloseHashCode(key)];
    }
}

const a=new HashTable();
a.put('money',"money@qq.com");
a.put('oxgbx',"oxgbx@qq.com");
console.log(a.get('money')); //oxgbx@qq.com

解決沖突

開放地址法

• 線性探測法

  
  
  17.png
  
  

  35%10結(jié)果是5，發(fā)現(xiàn)5上面有數(shù)據(jù)，就會向后找，發(fā)現(xiàn)6沒有放數(shù)據(jù)就會放在6里面;

線性探測法在數(shù)據(jù)聚集的時候會影響hash表的性能，無論是插入/刪除/查詢

• 二次探測法(平方探測法)：步長以平方的方式進(jìn)行優(yōu)化
• 再哈希法

鏈地址法

18.png

因?yàn)殒湵硎窃乇旧砗椭赶蛳乱粋€元素的指針；所以首先哈希運(yùn)算取得對應(yīng)索引(例如：1，2，3這種)；然后后面是鏈表而且是多個，可以再利用元素本身和鏈表中元素進(jìn)行比較

樹

例如：dom樹，linux系統(tǒng)的層級結(jié)構(gòu)

19.png

20.png

21.png

樹的術(shù)語

• 結(jié)點(diǎn)的度：結(jié)點(diǎn)所擁有的子樹的個數(shù)
• 樹的度：樹中節(jié)點(diǎn)度的最大值
• 葉子(終端結(jié)點(diǎn)): 度為0的結(jié)點(diǎn)
• 分支結(jié)點(diǎn)(非終端結(jié)點(diǎn))：度不為0的結(jié)點(diǎn)。除根節(jié)點(diǎn)之外的分支結(jié)點(diǎn)統(tǒng)稱為：內(nèi)部結(jié)點(diǎn)。根節(jié)點(diǎn)我們又稱為：開始結(jié)點(diǎn)
• 結(jié)點(diǎn)的層：根節(jié)點(diǎn)層：1；其余結(jié)點(diǎn)的層數(shù)等于父結(jié)點(diǎn)的層數(shù)+1
• 樹的深度：樹中所有節(jié)點(diǎn)層數(shù)的最大值
• 森林：擁有N顆樹，就被稱為森林

樹的存儲結(jié)構(gòu)

1. 計(jì)算機(jī)只能是順序存儲或者鏈?zhǔn)酱鎯?，所以樹這樣的結(jié)構(gòu)是不能夠直接存儲的，要將其轉(zhuǎn)換為順序或者鏈?zhǔn)酱鎯?/li>

• 雙親表示法：采用數(shù)組存儲普通的樹，其核心思想：順序存儲每個結(jié)點(diǎn)的同時，給各個結(jié)點(diǎn)附加一個記錄其父結(jié)點(diǎn)位置的變量，存儲父結(jié)點(diǎn)的下標(biāo)。
  實(shí)際操作的時候，就是從上到下，順序去遍歷一棵樹，并為相應(yīng)的域賦值。
  優(yōu)點(diǎn)：可以快速的獲取任意結(jié)點(diǎn)的父結(jié)點(diǎn)位置。
  缺點(diǎn)：如果要獲取某個結(jié)點(diǎn)的子結(jié)點(diǎn)就要遍歷了

22.png

• 孩子表示法:建立多個指針域，指向它的子結(jié)點(diǎn)的地址；也就是說任何一個結(jié)點(diǎn)，都掌握它所有子結(jié)點(diǎn)的信息。數(shù)組+鏈表的形式來實(shí)現(xiàn)

順序表=》數(shù)組，從樹的根節(jié)點(diǎn)開始，使用數(shù)組依次存儲樹的各個結(jié)點(diǎn)，需要注意的是，孩子表示法會被各個結(jié)點(diǎn)配備一個鏈表，用于存儲各結(jié)點(diǎn)的孩子結(jié)點(diǎn)位于數(shù)組中的位置，如果說，結(jié)點(diǎn)沒有子結(jié)點(diǎn)(葉子結(jié)點(diǎn))，則該結(jié)點(diǎn)的鏈表為空鏈表。

23.png

• 孩子兄弟表示法：把普通的樹轉(zhuǎn)換成了二叉樹：從樹的根結(jié)點(diǎn)開始，依次用鏈表存儲各個結(jié)點(diǎn)的孩子結(jié)點(diǎn)和兄弟結(jié)點(diǎn)

25.png

24.png

二叉樹：其實(shí)所有的樹的本質(zhì)都是可以使用二叉樹進(jìn)行模擬出來的，所以二叉樹很重要；二叉樹的存儲方式有數(shù)組和鏈表，最合適的方式是鏈表；從上到下從左至右

26.png

滿二叉樹：在一顆二叉樹中，如果所有的分支結(jié)點(diǎn)都存在于左子樹和右子樹，并且所有的葉子都在同一層，這樣的二叉樹就是滿二叉樹；葉子只能出現(xiàn)在最下一層，出現(xiàn)在其他層，不可能達(dá)成平衡；非葉子結(jié)點(diǎn)的度一定是2

27.png

完全二叉樹：滿二叉樹一定是完全二叉樹，反之則不是；設(shè)二叉樹的深度為h，除第 h 層外，其它各層 (1～h-1) 的結(jié)點(diǎn)數(shù)都達(dá)到最大個數(shù)(其實(shí)就是2，因?yàn)橥耆鏄渚褪菨M二叉樹分支最多兩個)，

第 h 層所有的結(jié)點(diǎn)都連續(xù)集中在最左邊

28.png

左斜樹

29.png

右斜樹

30.png

二叉搜索樹(BST)

二叉搜索樹其實(shí)就是普通二叉樹加上了一些限制

1. 非空左子樹的所有鍵值都小于其根節(jié)點(diǎn)的鍵值
2. 非空右子樹的所有鍵值都大于其根節(jié)點(diǎn)的鍵值
3. 左右子樹本身也都是二叉搜索樹
   總結(jié)：相對較小的值總保存在左子結(jié)點(diǎn)上，相對較大的值總是保存在右子結(jié)點(diǎn)上

class Node {
   constructor(key) {
       this.key = key;
       this.left = null;
       this.right = null;
   }
}

class BinaryTree {
   constructor() {
       this.root = null;
   }
   insert(key) {     // 插入數(shù)據(jù)
       var newNode = new Node(key);
       if (this.root == null) {
           this.root = newNode;
       } else {
           var current = this.root;
           while (true) {
               if (key < current.key) {
                   if (current.left) {
                       current = current.left;
                   } else {
                       current.left = newNode;
                       break;
                   }
               } else if (key > current.key) {
                   if (current.right) {
                       current = current.right;
                   } else {
                       current.right = newNode;
                       break;
                   }
               }
           }
       }
   }


   centerSort(node, arr = []) {        // 中序排列
       if (node) {
           this.centerSort(node.left, arr);
           arr.push(node.key);
           this.centerSort(node.right, arr);
       }
       return arr;
   }

   prevSort(node, arr = []) {           // 前序排列
       if (node) {
           arr.push(node.key);
           this.prevSort(node.left, arr);
           this.prevSort(node.right, arr);
       }
       return arr;
   }

   nextSort(node, arr = []) {               // 后續(xù)排列
       if (node) {
           this.nextSort(node.left, arr);
           this.nextSort(node.right, arr);
           arr.push(node.key);
       }
       return arr;
   }

   getMin(node) {                // 獲取二叉樹的最小值
       node = node || this.root;
       while (node.left != null) {
           node = node.left;
       }
       return node.key;
   }

   getMax(node) {                //獲取二叉樹最大值
       node = node || this.root;
       while (node.right != null) {
           node = node.right;
       }
       return node.key;
   }

   find(key) {               // 查找 給定的值
       var node = this.root;
       while (node != null) {
           if (key < node.key) {
               node = node.left;
           } else if (key > node.key) {
               node = node.right;
           } else {
               return node;
           }
       }
       return null;
   }

   remove(key) {         // 刪除給定的值
       this.root = this.removeNode(this.root, key);
   }

   removeNode(node, key) {      // 真正刪除的函數(shù)
       if (node == null) {
           return null;
       }
       if (key < node.key) {
           node.left = this.removeNode(node.left, key);
           return node;
       } else if (key > node.key) {
           node.right = this.removeNode(node.right, key);
           return node;
       } else {
           if (node.left == null && node.right == null) {
               node = null;
               return node;
           } else if (node.left == null) {
               return node.right;
           } else if (node.right == null) {
               return node.left;
           } else {
               var minNode = this.getMin(node.right);
               node.key = minNode.key;
               node.count = minNode.count;
               node.right = this.removeNode(node.right, minNode.key);
               return node;
           }
       }
   }
}

先序遍歷，中序遍歷，后序遍歷(用的少,也叫層次遍歷)

1. 先序遍歷: 訪問根結(jié)點(diǎn)，先序遍歷其左子樹，然后先序遍歷其右子樹

31.png

2. 中序遍歷：先遞歸遍歷其左子樹，從最后一個左子樹開始存入數(shù)組，然后回溯遍歷雙親結(jié)點(diǎn)，再是右子樹，遞歸循環(huán)

32.png

3. 后序遍歷：后序遍歷其左子樹，然后后序遍歷其右子樹，最后訪問根節(jié)點(diǎn)

33.png

刪除：

1. 沒有子樹

34.png

2. 有一顆子樹

35.png

3. 有兩顆子樹：保持中序遍歷順序不變

36.png

37.png

二叉搜索樹的優(yōu)點(diǎn)：作為數(shù)據(jù)存儲的結(jié)構(gòu)有重要的意義，可以快速的找到給定的關(guān)鍵字的數(shù)據(jù)項(xiàng)，并且可以快速的插入和刪除數(shù)據(jù)
二叉搜索樹的缺點(diǎn)：具有局限性，同樣的數(shù)據(jù)(但是順序不同的情況下)，可以對應(yīng)不同的二叉搜索樹，主要就是因?yàn)樽蟠笥倚〉囊?guī)則

38.png

如上圖：二叉搜索樹可能退化成一個鏈表的，二叉搜索樹的操作速度和高度是相關(guān)的，如果出現(xiàn)這種右斜樹類型的鏈表，則效率高也就成了一句空話

好的二叉搜索樹的結(jié)構(gòu)：左右分布均勻，但是我們插入連續(xù)的數(shù)據(jù)的時候，會導(dǎo)致數(shù)據(jù)分布不均勻，就把分布不均勻的樹稱為非平衡樹(如上圖右邊)

平衡樹：AVL(不常用，整體效率低于紅黑樹)，紅黑樹

二叉平衡樹

39.png

下圖只是說明平衡因子計(jì)算規(guī)則，而不是平衡二叉樹

39-1.png

40.png

41.png

42.png

43.png

紅黑樹(R-B tree)

AVL樹相對于紅黑樹，它的插入/刪除操作效率不高。

紅黑樹是一種自平衡的二叉搜索樹，以前叫做平衡二叉B樹;紅黑樹之所以效率高就是因?yàn)槠胶?，平衡則層級少，則性能高

紅黑樹增加的一些特性

1. 結(jié)點(diǎn)是紅色或者黑色(結(jié)點(diǎn)上有一個color屬性)
2. 根節(jié)點(diǎn)是黑色
3. 葉子結(jié)點(diǎn)都是黑色，且為null
4. 鏈接紅色結(jié)點(diǎn)的兩個子結(jié)點(diǎn)都是黑色，紅色結(jié)點(diǎn)的父結(jié)點(diǎn)都是黑色，紅色結(jié)點(diǎn)的子結(jié)點(diǎn)都是黑色
5. 從任意的結(jié)點(diǎn)出發(fā)，到其每個葉子結(jié)點(diǎn)的路徑中包含相同數(shù)據(jù)的黑色結(jié)點(diǎn)

這幾條規(guī)定：保證從根節(jié)點(diǎn)到葉子結(jié)點(diǎn)的最長路徑不大于最短路徑的2倍

紅黑樹插入數(shù)據(jù)的時候，會先去遍歷數(shù)據(jù)應(yīng)該插入到哪個位置，插入的數(shù)據(jù)一定是紅色的，因?yàn)椴迦牒谏珪茐钠胶?/p>

通過旋轉(zhuǎn)(左旋轉(zhuǎn)，右旋轉(zhuǎn))變色等滿足上述五條性質(zhì)；

44.png

const RED = true;
const BLACK = false;
class Node {
    constructor(key, value) {
        this.key = key;
        this.value = value;
        this.left = null;
        this.right = null;
        this.color = RED;
    }
}


class RBT {
    constructor() {
        this.root = null;
        this.size = 0;
    }
    isRed(node) {
        if (!node) return BLACK;
        return node.color;
    }
    // 左旋 右紅左黑
    leftRotate(node) {
        let tmp = node.right;
        node.right = tmp.left;
        tmp.left = node;
        tmp.color = node.color;
        node.color = RED;
        return tmp;
    }
    // 右旋轉(zhuǎn) 左紅左子紅
    rightRoate(node) {
        let tmp = node.left;
        node.left = tmp.right;
        tmp.right = node;
        tmp.color = node.color;
        node.color = RED;
        return tmp;
    }
    // 顏色翻轉(zhuǎn)
    flipColors(node) {
        node.color = RED;
        node.left.color = BLACK;
        node.right.color = BLACK;
    }
    add(key, value) {
        this.root = this.addRoot(this.root, key, value);
        this.root.color = BLACK; // 根節(jié)點(diǎn)始終是黑色
    }
    addRoot(node, key, value) {
        if (!node) {
            this.size++;
            return new Node(key, value);
        }
        if (key < node.key) {
            node.left = this.addRoot(node.left, key, value);
        } else if (key > node.key) {
            node.right = this.addRoot(node.right, key, value);
        } else {
            node.value = value;
        }
        if (this.isRed(node.right) && !this.isRed((node.left))) {
            node = this.leftRotate(node);
        }
        if (this.isRed(node.left) && this.isRed((node.left.left))) {
            node = this.rightRoate(node);
        }
        if (this.isRed(node.left) && this.isRed(node.right)) {
            this.flipColors(node);
        }
        return node;
    }
    isEmpty() {
        return this.size == 0 ? true : false;
    }
    getSize() {
        return this.size;
    }
    contains(key) {
        let ans = '';
        !(function getNode(node, key) {
            if (!node || key == node.key) {
                ans = node;
                return node;
            } else if (key > node.key) {
                return getNode(node.right, key);
            } else {
                return getNode(node.right, key);
            }
        })(this.root, key);
        return !!ans;
    }
    // bst前序遍歷(遞歸版本)
    preOrder(node = this.root) {
        if (node == null) return;
        console.log(node.key);
        this.preOrder(node.left);
        this.preOrder(node.right);
    }
    preOrderNR() {
        if (this.root == null) return;
        let stack = [];
        stack.push(this.root);
        while (stack.length > 0) {
            let curNode = stack.pop();
            console.log(curNode.key);
            if (curNode.right != null) stack.push(curNode.right);
            if (curNode.left != null) curNode.push(curNode.left);
        }
    }
    // bst中序遍歷
    inOrder(node = this.root) {
        if (node == null) return;
        this.inOrder(node.left);
        console.log(node.key);
        this.inOrder(node.right);
    }
    // bst后續(xù)遍歷
    postOrder(node = this.root) {
        if (node == null) return;
        this.postOrder(node.left);
        this.postOrder(node.right);
        console.log(node.key);
    }
    // bsf + 隊(duì)列的方式實(shí)現(xiàn)層次遍歷
    generateDepthString1() {
        let queue = [];
        queue.unshift(this.root);
        while (queue.length > 0) {
            let tmpqueue = []; let ans = [];
            queue.forEach(item => {
                ans.push(item.key);
                item.left ? tmpqueue.push(item.left) : '';
                item.right ? tmpqueue.push(item.right) : '';
            });
            console.log(...ans);
            queue = tmpqueue;
        }
    }
    minmun(node = this.root) {
        if (node.left == null) return node;
        return this.minmun(node.left);
    }
    maximum(node = this.root) {
        if (node.right == null) return node;
        return this.maximum(node.right);
    }
}


let btins = new RBT();
let ary = [5, 3, 6, 8, 4, 2];

ary.forEach(value => btins.add(value));
btins.generateDepthString1();
// ///////////////
//      5       //
//    /   \     //
//   3     8    //
//  / \   /     //
// 2  4  6      //
// ///////////////
console.log(btins.minmun());  // 2
console.log(btins.maximum()); // 8

樹的應(yīng)用

• 組織索引，mysql中用的B+樹
• JDK1.8的hashmap在單鏈表沖突之后會使用紅黑樹

樹的深度：從根結(jié)點(diǎn)開始，自頂向下逐層累加
樹的高度：自底向上逐層累加

圖(image)

• 集合只有同屬于一個集合的關(guān)系
• 線性結(jié)構(gòu)存在一對一的關(guān)系
• 樹形結(jié)構(gòu)一對多的關(guān)系
• 圖形結(jié)構(gòu)，多對多的關(guān)系

例如微信中，許多的用戶組成了一個多對多的朋友關(guān)系網(wǎng)，這個關(guān)系網(wǎng)就是數(shù)據(jù)結(jié)構(gòu)當(dāng)中的圖(Graph)
還有導(dǎo)航的最優(yōu)路徑：耗時最短的路徑等

45.png

自環(huán)：即一條鏈接一個頂點(diǎn)和自身的邊
平行邊：連接同一對頂點(diǎn)的兩條邊

52.png

圖的分類

• 無向圖: 邊沒有方向的圖稱為無向圖，邊的作用僅僅是連接兩個頂點(diǎn)，沒有其他含義
• 有向圖: 邊不僅連接兩個頂點(diǎn)，并且具有方向性，可能單向/雙向
• 帶權(quán)圖: 邊可以帶權(quán)重

46.png

47.png

圖的術(shù)語

1. 相鄰頂點(diǎn)：當(dāng)兩個頂點(diǎn)通過一條邊相連時候，我們稱這兩個頂點(diǎn)是相連的，并且是依附于這兩個頂點(diǎn)的
2. 度：某個頂點(diǎn)的度：是依附于這個頂點(diǎn)的邊的個數(shù)
3. 子圖:一幅圖中，所有邊的子集組成的圖，包含這些邊的依附的頂點(diǎn)
4. 路徑：是由邊順序鏈接的一系列的頂點(diǎn)組成
5. 環(huán)：至少含有一條邊，且終點(diǎn)和起來相同的路徑
6. 連通圖：如果圖中任意一個頂點(diǎn)都存在一條路徑到達(dá)另外一個頂點(diǎn)，那么這幅圖就稱為連通圖
7. 連通子圖：組成連通圖的非連通圖

48.png

歐拉七橋

歐拉開創(chuàng)了新的學(xué)科：圖論

49.png

圖的存儲結(jié)構(gòu)

圖是由頂點(diǎn)和邊構(gòu)成的，所以在圖里邊，要存儲的圖形結(jié)構(gòu)的信息，無非就是存儲圖的頂點(diǎn)和圖的邊；

頂點(diǎn)可以直接用數(shù)組去存儲

1，2，3，4=》[1,2,3,4]

邊存儲起來就麻煩一些

存儲結(jié)構(gòu)：

1. 鄰接矩陣
   • 矩陣是一個按照長方陣列的負(fù)數(shù)或者實(shí)數(shù)集合
   • N*M數(shù)據(jù)的集合(類似九宮格)；可以用1表示頂點(diǎn)與頂點(diǎn)有直接的關(guān)系，用0表示沒有連接
   • 優(yōu)點(diǎn)：表示明確，例如有向圖A->D:1 D->A:0
   • 缺點(diǎn)：消耗內(nèi)存大，存儲了太多的0；但是刪除會很麻煩，需要一個個置為0；下面的鄰接表就可以解決這個問題

50.png

2. 鄰接表
   • 由圖中的每個頂點(diǎn)以及和頂點(diǎn)相鄰的頂點(diǎn)列表組成。數(shù)組/鏈表/字典

51.png

圖的遍歷

1. 遍歷：從某個結(jié)點(diǎn)出發(fā)，按照一定的搜索路線，依次訪問數(shù)據(jù)結(jié)構(gòu)中的全部結(jié)點(diǎn)，而且每個結(jié)點(diǎn)訪問一次
2. 廣度優(yōu)先遍歷(BFS)

優(yōu)先橫向遍歷圖，廣度優(yōu)先的思想，從圖中的某個頂點(diǎn)V出發(fā)，在訪問V之后，依次去訪問V的各個未曾訪問過的鄰結(jié)點(diǎn)，然后分別從這些鄰結(jié)點(diǎn)出發(fā)，依次訪問他們的鄰結(jié)點(diǎn)。
注意：圖沒有橫向和縱向的概念

53.png

3. 深度優(yōu)先遍歷(LFS)

深度優(yōu)先有遞歸的概念

54.png

圖遍歷的思路

• 每個頂點(diǎn)有三種狀態(tài)
  1. 未發(fā)現(xiàn)
  2. 已經(jīng)發(fā)現(xiàn)
  3. 已經(jīng)探索

55.png

• 記錄頂點(diǎn)是否被訪問過，使用三種顏色來反應(yīng)它們的狀態(tài)
  1. 白色，未發(fā)現(xiàn)
  2. 灰色，以發(fā)現(xiàn)
  3. 黑色，已經(jīng)探索
• 廣度優(yōu)先的遍歷過程
  1. 發(fā)現(xiàn)未發(fā)現(xiàn)頂點(diǎn)后，存放隊(duì)列中，等待查找，并且將這些頂點(diǎn)標(biāo)記為以發(fā)現(xiàn)
  2. 在隊(duì)列中拿出已經(jīng)發(fā)現(xiàn)的頂點(diǎn)，開始探索全部頂點(diǎn)，并且要跳過已經(jīng)探索的頂點(diǎn)
  3. 遍歷完這個頂點(diǎn)以后，將這個頂點(diǎn)標(biāo)志為已經(jīng)探索
  4. 循環(huán)在隊(duì)列中探索下一個頂點(diǎn)
• 深度優(yōu)先的遍歷過程
  1. 廣度優(yōu)先使用的是隊(duì)列，深度優(yōu)先的原理：使用遞歸
  2. 從某一個頂點(diǎn)開始查找，并且將這個頂點(diǎn)標(biāo)記為已經(jīng)發(fā)現(xiàn)(灰色)
  3. 從這個頂點(diǎn)開始探索其他的全部的頂點(diǎn)，并且跳過已經(jīng)發(fā)現(xiàn)的頂點(diǎn)
  4. 遞歸返回，繼續(xù)探索下一個路徑的最深頂點(diǎn)

代碼案例

• 利用鄰接矩陣（邊數(shù)組）創(chuàng)建圖

let scanf = require('scanf');
//定義鄰接矩陣
let Arr2 = [
    [0, 1, 0, 0, 0, 1, 0, 0, 0],
    [1, 0, 1, 0, 0, 0, 1, 0, 1],
    [0, 1, 0, 1, 0, 0, 0, 0, 1],
    [0, 0, 1, 0, 1, 0, 1, 1, 1],
    [0, 0, 0, 1, 0, 1, 0, 1, 0],
    [1, 0, 0, 0, 0, 0, 1, 0, 0],
    [0, 1, 0, 1, 0, 1, 0, 1, 0],
    [0, 0, 0, 1, 1, 0, 1, 0, 0],
    [0, 1, 1, 1, 0, 0, 0, 0, 0],
]
 
let numVertexes = 9, //定義頂點(diǎn)數(shù)
    numEdges = 14; //定義邊數(shù)
 
// 定義圖結(jié)構(gòu)
function MGraph() {
    this.vexs = []; //頂點(diǎn)表
    this.arc = []; // 鄰接矩陣，可看作邊表
    this.numVertexes = null; //圖中當(dāng)前的頂點(diǎn)數(shù)
    this.numEdges = null; //圖中當(dāng)前的邊數(shù)
}
let G = new MGraph(); //創(chuàng)建圖使用
 
//創(chuàng)建圖
function createMGraph() {
    G.numVertexes = numVertexes; //設(shè)置頂點(diǎn)數(shù)
    G.numEdges = numEdges; //設(shè)置邊數(shù)
 
    //錄入頂點(diǎn)信息
    for (let i = 0; i < G.numVertexes; i++) {
        G.vexs[i] = scanf('%s'); //String.fromCharCode(i + 65); ascii碼轉(zhuǎn)字符
    }
    console.log(G.vexs) //打印頂點(diǎn)
 
    //鄰接矩陣初始化
    for (let i = 0; i < G.numVertexes; i++) {
        G.arc[i] = [];
        for (j = 0; j < G.numVertexes; j++) {
            G.arc[i][j] = Arr2[i][j]; //INFINITY;
        }
    }
 
    /**以下是手動錄入的方式 */
    // for (let k = 0; k < G.numEdges; k++) {
    //     console.log('輸入邊（vi,vj）上的下標(biāo)i,下標(biāo)j和權(quán)w:');
    //     let rlt = scanf('%d,%d,%d');
    //     let i = rlt[0], j = rlt[1], w = rlt[2];
    //     G.arc[i][j] = w;
    //     G.arc[j][i] = G.arc[i][j]; //無向圖，矩陣對稱
    // }
 
    console.log(G.arc); //打印鄰接矩陣
}

• 深度優(yōu)先遍歷

let visited = []; //訪問標(biāo)志數(shù)組，遍歷時使用
 
//鄰接矩陣的深度優(yōu)先遞歸算法
function DFS(i) {
    visited[i] = true;
    console.log('打印頂點(diǎn):', G.vexs[i]) //打印頂點(diǎn) ,也可以其他操作
    for (let j = 0; j < G.numVertexes; j++) {
        if (G.arc[i][j] == 1 && !visited[j]) {
            console.log(G.vexs[i], '->', G.vexs[j])
            DFS(j) //對未訪問的頂點(diǎn)進(jìn)行遞歸
        }
    }
}
//鄰接矩陣的深度遍歷操作
function DFSTraverse() {
    for (let i = 0; i < G.numVertexes; i++) {
        visited[i] = false;
    }
    for (let i = 0; i < G.numVertexes; i++) {
        if (!visited[i])
            DFS(i)
    }
}

• 廣度優(yōu)先遍歷

//鄰接矩陣的廣度遍歷算法
function BFSTraverse() {
    let queue = []; //初始化隊(duì)列
    for (let i = 0; i < G.numVertexes; i++) {
        visited[i] = false;
    }
    for (let i = 0; i < G.numVertexes; i++) { //對每一個頂點(diǎn)做循環(huán)
        if (!visited[i]) { //如果沒有訪問過就處理
            visited[i] = true;
            console.log('打印頂點(diǎn)：', G.vexs[i]) //也可以是其他操作
            queue.push(i); //將此頂點(diǎn)入隊(duì)列
            while (queue.length != 0) { //當(dāng)前隊(duì)列不為空
                queue.shift();
                for (let j = 0; j < G.numVertexes; j++) {
                    //判斷其他頂點(diǎn)若與當(dāng)前頂點(diǎn)存在邊且未訪問過
                    if (G.arc[i][j] == 1 && !visited[j]) {
                        visited[j] = true;
                        console.log(G.vexs[i], '->', G.vexs[j])
                        console.log('打印頂點(diǎn)：', G.vexs[j])
                        queue.push(j) //將此頂點(diǎn)放入隊(duì)列
                    }
                }
            }
        }
    }
}

最短路徑

1. 路徑：由邊順序連接的頂點(diǎn)組成的

   • 尋找最短路徑，所謂路徑指的是：如果從圖中的某一個頂點(diǎn)(起點(diǎn)，圓點(diǎn))到達(dá)另外一個頂點(diǎn)(終點(diǎn))路徑步可能只有一條，如何找到一條路徑使得沿這個路徑邊上的權(quán)值總和(路徑長度)達(dá)到最小

2. 回溯點(diǎn)

   • 回溯點(diǎn)是離上一個頂點(diǎn)最近的頂點(diǎn)。A的回溯電是null,B的回溯點(diǎn)是：A，E的回溯點(diǎn)是B
     回溯路徑(所有回溯點(diǎn)組成)
     通過回溯點(diǎn)可以查找到最短路徑

56.png

const prev={
    'A':null,
    'B':'A',
    'E':'B'
}

3. 常見得求最短路徑得算法

有了回溯點(diǎn)，但是實(shí)際上通過回溯點(diǎn)計(jì)算最短路徑的算法有多種

• 迪杰斯拉特算法，是貪心算法的一個應(yīng)用，用來解決單元點(diǎn)到其余頂點(diǎn)的最短路徑的問題
• Floyd算法，經(jīng)典的動態(tài)規(guī)劃算法