用 JS 数组方法模拟队列

队列实例演示视频，可以看出是先进先出

JS 异步中的任务队列

• JS 是单线程的，无法同时处理异步中的并发任务
• 使用任务队列先后处理异步任务

链表模拟

//链表  模拟
const a = { val: "a" };
const b = { val: "b" };
const c = { val: "c" };
const d = { val: "d" };
a.next = b;
b.next = c;
c.next = d;
//遍历链表
let p = a;
while (p) {
  console.log(p.val);
  p = p.next;
}
//插入 改变next指向
const e = { val: "e" };
c.next = e;
e.next = d;
while (p) {
  console.log(p.val);
  p = p.next;
}
//删除e
c.next = d;

集合

//去重
const arr = [1, 1, 1, 2];
const arr2 = [...new Set(arr)]; //得到一个集合
console.log(arr2);
//判断元素是否在集合中
const set = new Set(arr);
console.log(set.has(1));
//求交集
const set2 = new Set([2, 3]);
const set3 = new Set(
  [...set].filter((item) => {
    return set2.has(item);
  })
);
console.log([...set3]);

字典

• 与集合类似，字典也是一种储存为一只的数据结构，但他是以键值对的形式来储存

//ES6总有字典，名为Map
const m = new Map();
m.set("a", "aaa");
m.set("b", "bbb");
//删除字典
m.delete("a");
m.clear();
//改
m.set("a", "awdawd");

树

• 一种分层数据抽象模型
• 前端工作中常见的树包括，DOM 数，级联选择,树形控件
  js 中没有树，但是可以用 Object 和 Array 构建数
• 树的常用操作，深度/广度操作
  • 深度优先遍历 1.访问根节点 2.对根节点的 chidren 挨个进行深度优先遍历
    就是递归的使用

const tree = {
  val: "根节点",
  children: [
    {
      val: "二级节点1",
      children: [
        {
          val: "三级节点1",
          children: [],
        },
        {
          val: "三级节点2",
          children: [],
        },
      ],
    },
    {
      val: "二级节点2",
      children: [
        {
          val: "三级节点3",
          children: [],
        },
        {
          val: "三级节点4",
          children: [],
        },
      ],
    },
    {
      val: "二级节点3",
      children: [
        {
          val: "三级节点5",
          children: [],
        },
        {
          val: "三级节点6",
          children: [],
        },
      ],
    },
  ],
};
const dfs = (root) => {
  console.log(root.val);
  root.children.forEach(dfs);
};
dfs(tree);

执行结果

• 广度优先遍历
  • 新建一个队列，把根节点入队
  • 把队头出队，并访问
  • 把对头的 children 挨个入队
  • 重读第二，三步直到队列为空
    接续用上述的 tree 使用广度优先遍历实现

const bfs = function (root) {
  //拿到队头
  let queue = [root];
  while (queue.length > 0) {
    let n = queue.shift(); //出队并访问
    console.log(n);
    //把队头的children挨个入队
    n.children.forEach((item) => {
      queue.push(item);
    });
  }
};

二叉树的前中后序遍历

先序遍历

• 先序遍历算法口诀
  • 访问根节点
  • 对根节点的左子树进行先序遍历
  • 对根节点的右子树进行先序遍历

如下二叉树

const bt = {
  val: 1,
  left: {
    val: 2,
    left: {
      val: 3,
      left: null,
      right: null,
    },
    right: {
      val: 4,
      left: null,
      right: null,
    },
  },
  right: {
    val: 5,
    left: {
      val: 6,
      left: null,
      right: null,
    },
    right: {
      val: 7,
      left: null,
      right: null,
    },
  },
};
module.exports = bt;

根据算法口诀先序遍历

const perorder = function (root) {
  if (!root) {
    return; //当子树不存在时退出
  }
  console.log(root.val); //访问根节点
  perorder(root.left); //对根节点的左子树进行遍历
  perorder(root.right); //对根节点的右子树进行遍历
};

;
按照这个顺序进行遍历
得到

中序遍历算法口诀

1. 对根节点的左子树进行中序遍历
2. 访问根节点
3. 对根节点的右子树进行中序遍历
   code 实现

const inorder = function (root) {
  if (!root) {
    return; //判断
  }
  inorder(root.left); //先访问左子树
  console.log(root.val); //访问根节点
  inorder(root.right); //访问右子树
};

遍历顺序图

结果图

后续遍历

1. 对根节点中的左子树进行遍历
2. 对根节点的右子树进行遍历
3. 访问根节点
   code

const backorder = function (root) {
  if (!root) {
    return;
  }
  backorder(root.left);
  backorder(root.right);
  console.log(root.val);
};

遍历顺序

结果；

结果如图

解压小视频