四种：集合结构，线性结构，树形结构，图形结构

• 集合结构：数据元素同属于一个结合，他们之间没有其他的关系。它们的共同属性是：同属于一个集合
• 线性结构：最典型的数据关系是一对一。线性结构是一种有序数据的集合。
  • 数组：就是一个线性结构，栈，队列，FILO
• 树形结构：数据元素是一对多，例如dom树

• 图形结构：数据元素是多对多

  
  
  1.png

物理结构：数据元素存储到计算中的存储器，针对内存而言的
数据的存储结构应该正确的反应数据元素之间的逻辑关系
顺序存储，链式存储

数组

js的数组不是真正意义上的数组；
数组：再内存中用一串连续的区域来存放一些值。
数组是相同类型数据元素的集合(js的数组可以存储不同类型)；
而且一般数组的容量是不会自动变化的
数组内存地址是连续的，但是js中的内存地址是不连续，原因是数据类型可以是任意类型导致的

数组的优点：

1. 按照索引查询元素的时候速度很快
2. 存储大两的数据
3. 按照索引去遍历数组
4. 定义方便，访问灵活

数组的缺点：

1. 根据内容查找会很慢
2. 数组的大小一经确定是不能改变的，不适合动态存储
3. 数组只能存储相同类型数据
4. 增加删除元素效率慢，因为内存地址是连续的

栈

内存区域：栈区
单片机：压栈
数据结构中有一个同名的数据结构，栈

内存中的堆栈和数据结构中的堆栈不是一个概念，内存中的堆栈是真实存在的物理区，数据结构中的堆栈是抽象数据存储结构

栈：是一种受限制的线性表，LIFO
其限制是仅允许再表的一端进行插入和删除运算，这一端被称为栈顶，相对的，把另一端称为栈底
向一个栈插入新元素被称为进栈，入栈，压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素
从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素

栈的应用：十进制转二进制

当时js中有内置api实现，但是此处只是说明一个应用场景

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取余数
        remainder = number % 2;
        stack.push(remainder);
        //向下取整
        number=Math.floor(number/2);
    }

    //不为空的时候
    while (!stack.isEmpty()) {
        //栈顶元素
        top+=stack.top();
    }
    return top;
}

JS 调用栈：

参考网址:https://www.cnblogs.com/shuajing/p/10800656.html

前置说明：
1 JavaScript 是一门单线程的语言，这意味着它只有一个调用栈，因此，它同一时间只能做一件事。
2 内存堆：这是内存分配发生的地方.
3 调用栈：这是你的代码执行时的地方

定义：调用栈是解释器（就像浏览器中的javascript解释器）追踪函数执行流的一种机制。当执行环境中调用了多个函数时，通过这种机制，我们能够追踪到哪个函数正在执行，执行的函数体中又调用了哪个函数。
1. 每调用一个函数，解释器就会把该函数添加进调用栈并开始执行。
2 正在调用栈中执行的函数还调用了其它函数，那么新函数也将会被添加进调用栈，一旦这个函数被调用，便会立即执行。
3 当前函数执行完毕后，解释器将其清出调用栈，继续执行当前执行环境下的剩余的代码。
4 当分配的调用栈空间被占满时，会引发“堆栈溢出”

函数的调用本质："压栈和出栈操作"，但是函数在调用栈里面有一个特例，叫做递归
递归：自己调用自己，先进栈，如果不出栈，就会导致：栈溢出

斐波那契数列：从第三项开始，每一项都等于前两项的和1 1 2 3 5 8 13

当数值很大的时候，计算斐波那契数列会出现计算慢(因为有重复计算，函数多同时也会导致调用栈过多)调用栈溢出，解决方案是尾递归优化

• 尾调用

尾调用自身就是尾递归

//函数b的尾部调用a函数，被称为尾调用
function a(x) {}
function b(x){
    return a(x);
}



b(x);
实际上就是调用a(x);
可以看成没有外部调用帧


如果a就是b本身的话，即使有很多层调用，因为尾递归优化，实际上不会像常规调用一样，帧一层套一层；
总共只有一个调用帧，避免了调用栈溢出

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

优化斐波那契数列

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

//优化案例
//把前面两位数当作参数传递进来
//此处没有利用常规缓存函数计算结果，而是直接缓存上次总体计算结果；实际上也是利用了缓存
//递归需要同时保存成百上千个调用帧，很容易发生栈溢出，而且因为尾递归优化，只有一个调用栈，永远不会栈溢出
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));

队列

• 是一种受限的线性表，FIFO

• 受限之处：它只允许表的前端进行删除操作，在表的后端进行增加操作

  
  
  9.png

class Quenue{
    constructor(){
        this.items= [];
    }
    //入队
    enqueue(item){
        this.items.push(item);
    }
    //出队操作
    dequeue(){
        return this.items.shift();
    }
    //查看队首元素
    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的异步队列
  js为什么是单线程：完成与用户交互以及dom操作；一个线程添加dom一个删除dom，浏览器听谁的，避免复杂性所以直接单线程
• 主线程执行完毕之后，从事件队列中读取任务队列的过程，称之为事件循环(EventLoop)
• Promise是同步的，then和catch是异步的

Promise补充：必须查看 https://segmentfault.com/a/1190000020980101

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

})

Promise.resolve()


https://segmentfault.com/a/1190000020980101

任务队列：存在着两个队列，一个宏任务一个微任务队列

主线程：同步任务->微任务->宏任务

promise.then catch finally process.nexttick是微任务，
I/O,定时器，ajax,事件绑定是宏任务

链表

例如原型链

链表就可以解决这样的问题

1. 插入删除：链表的性能好
   链表没有大小限制，支持动态扩容，因为链表的每个节点都需要存储前驱/后驱节点的指针，内存消耗会翻倍
2. 查询修改：数组性能好

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找到后面的节点
            let current=this.head;
            //遍历,是否是最后一个节点,next为空就是最后一个
            while (current.next){
                current=current.next;
            }
            //while执行完毕之后，current就已经是最后一个节点了
        }
        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){
        //位置不能实负数
        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;
    }
// ......实际上还有代码，此处省略
}

prototype和proto

1. 所有的引用类型(数组，函数，对象)可以自由的扩展属性(null除外)
2. 所有的引用类型都有一个proto属性(隐式原型，它其实就是一个普通的对象)
3. 所有的函数都有一个prototype属性(显式原型，也是一个普通对)
4. 所有的引用类型的proto属性都指向它的构造函数的prototype属性
5. 当试图得到一个对象的属性时，如果这个对象的本身不存在这个属性，那么就会去它的proto属性中找(去它的构造函数的prototype属性中去寻找)
6. 当调用这个对象本身并不存在的属性或者方法时，它会一层层的往上找，一直找到null为止，null表示空的对象{}

案例

• 案例一

//构造函数
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它就是一个普通函数但是这个函数的作用：构造对象
 * 这种构造对象的方式：工厂方式
 */

//这样new多少次show就有多少个
console.log(t1.show === t2.show);//false

• 案例二

//构造函数
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
// 这样存在问题，容易导致全局作用域的污染，并且数据是不安全的容易被覆盖，例如后面还有一个同名的fun函数

• 案例三

//如下
function Teacher(name, habby) {
    this.name = name;
    this.habby = habby;
}
//Teacher就是构造函数，其内部有prototype属性，而__proto__又会指向构造函数的prototype属性
//Teacher.prototype是一个普通对象，这个对象的构造函数是Object
Teacher.prototype.show = function(){
    console.log(1111);
}
console.log(Teacher.prototype.__proto__===Object.prototype);//true

• 原型链继承

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


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

哈希表

MD5是目前应用最广泛的Hash算法，但是并不是唯一的算法

class HashTable {
    constructor() {
        this.table = [];//哈希表
    }
    //哈希函数:这只是一个很简化版的
    loseloseHashCode(key) {
        let hash = 0;
        for (let i = 0; i < key.length; i++) {
            hash += key[i].charCodeAt();//计算key   unicode码

        }
        //取模
        return hash % 37;//37是质数，可以很大程度上避免碰撞
    }
    //新增元素
    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' ] }    
//由上面输出可知，有很多空项，是因为此时索引不是数字的，所以前面可能存在空项
console.log(a.get('zq'));

• 碰撞

数组里面，如果数组的下标相同，后边添加的就会覆盖前面的，这个叫覆盖；

哈希表：冲突，碰撞，对于不同的要存储的数据经过哈希函数得到的索引有可能相同

const arr = [];
arr[1] = 'zq';
arr[1] = 'zq1';
//数组会覆盖
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 = [];//哈希表
    }
    //哈希函数:这只是一个很简化版的
    loseloseHashCode(key) {
        let hash = 0;
        for (let i = 0; i < key.length; i++) {
            hash += key[i].charCodeAt();//计算key   unicode码

        }
        //取模
        return hash % 37;//37是质数，可以很大程度上避免碰撞
    }
    //新增元素
    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结果是5，发现5上面有数据，就会向后找，发现6没有放数据就会放在6里面;

线性探测法在数据聚集的时候会影响hash表的性能，无论是插入/删除/查询

• 二次探测法(平方探测法)：步长以平方的方式进行优化
• 再哈希法

链地址法

因为链表是元素本身和指向下一个元素的指针；所以首先哈希运算取得对应索引(例如：1，2，3这种)；然后后面是链表而且是多个，可以再利用元素本身和链表中元素进行比较

树

例如：dom树，linux系统的层级结构

树的术语

• 结点的度：结点所拥有的子树的个数
• 树的度：树中节点度的最大值
• 叶子(终端结点): 度为0的结点
• 分支结点(非终端结点)：度不为0的结点。除根节点之外的分支结点统称为：内部结点。根节点我们又称为：开始结点
• 结点的层：根节点层：1；其余结点的层数等于父结点的层数+1
• 树的深度：树中所有节点层数的最大值
• 森林：拥有N颗树，就被称为森林

树的存储结构

1. 计算机只能是顺序存储或者链式存储，所以树这样的结构是不能够直接存储的，要将其转换为顺序或者链式存储

• 双亲表示法：采用数组存储普通的树，其核心思想：顺序存储每个结点的同时，给各个结点附加一个记录其父结点位置的变量，存储父结点的下标。
  实际操作的时候，就是从上到下，顺序去遍历一棵树，并为相应的域赋值。
  优点：可以快速的获取任意结点的父结点位置。
  缺点：如果要获取某个结点的子结点就要遍历了

• 孩子表示法:建立多个指针域，指向它的子结点的地址；也就是说任何一个结点，都掌握它所有子结点的信息。数组+链表的形式来实现

顺序表=》数组，从树的根节点开始，使用数组依次存储树的各个结点，需要注意的是，孩子表示法会被各个结点配备一个链表，用于存储各结点的孩子结点位于数组中的位置，如果说，结点没有子结点(叶子结点)，则该结点的链表为空链表。

• 孩子兄弟表示法：把普通的树转换成了二叉树：从树的根结点开始，依次用链表存储各个结点的孩子结点和兄弟结点

二叉树：其实所有的树的本质都是可以使用二叉树进行模拟出来的，所以二叉树很重要；二叉树的存储方式有数组和链表，最合适的方式是链表；从上到下从左至右

满二叉树：在一颗二叉树中，如果所有的分支结点都存在于左子树和右子树，并且所有的叶子都在同一层，这样的二叉树就是满二叉树；叶子只能出现在最下一层，出现在其他层，不可能达成平衡；非叶子结点的度一定是2

完全二叉树：满二叉树一定是完全二叉树，反之则不是；设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数(其实就是2，因为完全二叉树就是满二叉树分支最多两个)，

第 h 层所有的结点都连续集中在最左边

左斜树

右斜树

二叉搜索树(BST)

二叉搜索树其实就是普通二叉树加上了一些限制

1. 非空左子树的所有键值都小于其根节点的键值
2. 非空右子树的所有键值都大于其根节点的键值
3. 左右子树本身也都是二叉搜索树
   总结：相对较小的值总保存在左子结点上，相对较大的值总是保存在右子结点上

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

class BinaryTree {
   constructor() {
       this.root = null;
   }
   insert(key) {     // 插入数据
       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 = []) {               // 后续排列
       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) {      // 真正删除的函数
       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. 先序遍历: 访问根结点，先序遍历其左子树，然后先序遍历其右子树

2. 中序遍历：先递归遍历其左子树，从最后一个左子树开始存入数组，然后回溯遍历双亲结点，再是右子树，递归循环

3. 后序遍历：后序遍历其左子树，然后后序遍历其右子树，最后访问根节点

删除：

1. 没有子树

2. 有一颗子树

3. 有两颗子树：保持中序遍历顺序不变

二叉搜索树的优点：作为数据存储的结构有重要的意义，可以快速的找到给定的关键字的数据项，并且可以快速的插入和删除数据
二叉搜索树的缺点：具有局限性，同样的数据(但是顺序不同的情况下)，可以对应不同的二叉搜索树，主要就是因为左大右小的规则

如上图：二叉搜索树可能退化成一个链表的，二叉搜索树的操作速度和高度是相关的，如果出现这种右斜树类型的链表，则效率高也就成了一句空话

好的二叉搜索树的结构：左右分布均匀，但是我们插入连续的数据的时候，会导致数据分布不均匀，就把分布不均匀的树称为非平衡树(如上图右边)

平衡树：AVL(不常用，整体效率低于红黑树)，红黑树

二叉平衡树

下图只是说明平衡因子计算规则，而不是平衡二叉树

红黑树(R-B tree)

AVL树相对于红黑树，它的插入/删除操作效率不高。

红黑树是一种自平衡的二叉搜索树，以前叫做平衡二叉B树;红黑树之所以效率高就是因为平衡，平衡则层级少，则性能高

红黑树增加的一些特性

1. 结点是红色或者黑色(结点上有一个color属性)
2. 根节点是黑色
3. 叶子结点都是黑色，且为null
4. 链接红色结点的两个子结点都是黑色，红色结点的父结点都是黑色，红色结点的子结点都是黑色
5. 从任意的结点出发，到其每个叶子结点的路径中包含相同数据的黑色结点

这几条规定：保证从根节点到叶子结点的最长路径不大于最短路径的2倍

红黑树插入数据的时候，会先去遍历数据应该插入到哪个位置，插入的数据一定是红色的，因为插入黑色会破坏平衡

通过旋转(左旋转，右旋转)变色等满足上述五条性质；

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;
    }
    // 右旋转 左红左子红
    rightRoate(node) {
        let tmp = node.left;
        node.left = tmp.right;
        tmp.right = node;
        tmp.color = node.color;
        node.color = RED;
        return tmp;
    }
    // 颜色翻转
    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; // 根节点始终是黑色
    }
    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后续遍历
    postOrder(node = this.root) {
        if (node == null) return;
        this.postOrder(node.left);
        this.postOrder(node.right);
        console.log(node.key);
    }
    // bsf + 队列的方式实现层次遍历
    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

树的应用

• 组织索引，mysql中用的B+树
• JDK1.8的hashmap在单链表冲突之后会使用红黑树

树的深度：从根结点开始，自顶向下逐层累加
树的高度：自底向上逐层累加

图(image)

• 集合只有同属于一个集合的关系
• 线性结构存在一对一的关系
• 树形结构一对多的关系
• 图形结构，多对多的关系

例如微信中，许多的用户组成了一个多对多的朋友关系网，这个关系网就是数据结构当中的图(Graph)
还有导航的最优路径：耗时最短的路径等

自环：即一条链接一个顶点和自身的边
平行边：连接同一对顶点的两条边

图的分类

• 无向图: 边没有方向的图称为无向图，边的作用仅仅是连接两个顶点，没有其他含义
• 有向图: 边不仅连接两个顶点，并且具有方向性，可能单向/双向
• 带权图: 边可以带权重

图的术语

1. 相邻顶点：当两个顶点通过一条边相连时候，我们称这两个顶点是相连的，并且是依附于这两个顶点的
2. 度：某个顶点的度：是依附于这个顶点的边的个数
3. 子图:一幅图中，所有边的子集组成的图，包含这些边的依附的顶点
4. 路径：是由边顺序链接的一系列的顶点组成
5. 环：至少含有一条边，且终点和起来相同的路径
6. 连通图：如果图中任意一个顶点都存在一条路径到达另外一个顶点，那么这幅图就称为连通图
7. 连通子图：组成连通图的非连通图

欧拉七桥

欧拉开创了新的学科：图论

图的存储结构

图是由顶点和边构成的，所以在图里边，要存储的图形结构的信息，无非就是存储图的顶点和图的边；

顶点可以直接用数组去存储

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

边存储起来就麻烦一些

存储结构：

1. 邻接矩阵
   • 矩阵是一个按照长方阵列的负数或者实数集合
   • N*M数据的集合(类似九宫格)；可以用1表示顶点与顶点有直接的关系，用0表示没有连接
   • 优点：表示明确，例如有向图A->D:1 D->A:0
   • 缺点：消耗内存大，存储了太多的0；但是删除会很麻烦，需要一个个置为0；下面的邻接表就可以解决这个问题

2. 邻接表
   • 由图中的每个顶点以及和顶点相邻的顶点列表组成。数组/链表/字典

图的遍历

1. 遍历：从某个结点出发，按照一定的搜索路线，依次访问数据结构中的全部结点，而且每个结点访问一次
2. 广度优先遍历(BFS)

优先横向遍历图，广度优先的思想，从图中的某个顶点V出发，在访问V之后，依次去访问V的各个未曾访问过的邻结点，然后分别从这些邻结点出发，依次访问他们的邻结点。
注意：图没有横向和纵向的概念

3. 深度优先遍历(LFS)

深度优先有递归的概念

图遍历的思路

• 每个顶点有三种状态
  1. 未发现
  2. 已经发现
  3. 已经探索

• 记录顶点是否被访问过，使用三种颜色来反应它们的状态
  1. 白色，未发现
  2. 灰色，以发现
  3. 黑色，已经探索
• 广度优先的遍历过程
  1. 发现未发现顶点后，存放队列中，等待查找，并且将这些顶点标记为以发现
  2. 在队列中拿出已经发现的顶点，开始探索全部顶点，并且要跳过已经探索的顶点
  3. 遍历完这个顶点以后，将这个顶点标志为已经探索
  4. 循环在队列中探索下一个顶点
• 深度优先的遍历过程
  1. 广度优先使用的是队列，深度优先的原理：使用递归
  2. 从某一个顶点开始查找，并且将这个顶点标记为已经发现(灰色)
  3. 从这个顶点开始探索其他的全部的顶点，并且跳过已经发现的顶点
  4. 递归返回，继续探索下一个路径的最深顶点

代码案例

• 利用邻接矩阵（边数组）创建图

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, //定义顶点数
    numEdges = 14; //定义边数
 
// 定义图结构
function MGraph() {
    this.vexs = []; //顶点表
    this.arc = []; // 邻接矩阵，可看作边表
    this.numVertexes = null; //图中当前的顶点数
    this.numEdges = null; //图中当前的边数
}
let G = new MGraph(); //创建图使用
 
//创建图
function createMGraph() {
    G.numVertexes = numVertexes; //设置顶点数
    G.numEdges = numEdges; //设置边数
 
    //录入顶点信息
    for (let i = 0; i < G.numVertexes; i++) {
        G.vexs[i] = scanf('%s'); //String.fromCharCode(i + 65); ascii码转字符
    }
    console.log(G.vexs) //打印顶点
 
    //邻接矩阵初始化
    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）上的下标i,下标j和权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); //打印邻接矩阵
}

• 深度优先遍历

let visited = []; //访问标志数组，遍历时使用
 
//邻接矩阵的深度优先递归算法
function DFS(i) {
    visited[i] = true;
    console.log('打印顶点:', G.vexs[i]) //打印顶点 ,也可以其他操作
    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) //对未访问的顶点进行递归
        }
    }
}
//邻接矩阵的深度遍历操作
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)
    }
}

• 广度优先遍历

//邻接矩阵的广度遍历算法
function BFSTraverse() {
    let queue = []; //初始化队列
    for (let i = 0; i < G.numVertexes; i++) {
        visited[i] = false;
    }
    for (let i = 0; i < G.numVertexes; i++) { //对每一个顶点做循环
        if (!visited[i]) { //如果没有访问过就处理
            visited[i] = true;
            console.log('打印顶点：', G.vexs[i]) //也可以是其他操作
            queue.push(i); //将此顶点入队列
            while (queue.length != 0) { //当前队列不为空
                queue.shift();
                for (let j = 0; j < G.numVertexes; j++) {
                    //判断其他顶点若与当前顶点存在边且未访问过
                    if (G.arc[i][j] == 1 && !visited[j]) {
                        visited[j] = true;
                        console.log(G.vexs[i], '->', G.vexs[j])
                        console.log('打印顶点：', G.vexs[j])
                        queue.push(j) //将此顶点放入队列
                    }
                }
            }
        }
    }
}

最短路径

1. 路径：由边顺序连接的顶点组成的

   • 寻找最短路径，所谓路径指的是：如果从图中的某一个顶点(起点，圆点)到达另外一个顶点(终点)路径步可能只有一条，如何找到一条路径使得沿这个路径边上的权值总和(路径长度)达到最小

2. 回溯点

   • 回溯点是离上一个顶点最近的顶点。A的回溯电是null,B的回溯点是：A，E的回溯点是B
     回溯路径(所有回溯点组成)
     通过回溯点可以查找到最短路径

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

3. 常见得求最短路径得算法

有了回溯点，但是实际上通过回溯点计算最短路径的算法有多种

• 迪杰斯拉特算法，是贪心算法的一个应用，用来解决单元点到其余顶点的最短路径的问题
• Floyd算法，经典的动态规划算法