【学习打卡】第11天 数据结构之“树”

课程名称：JavaScript版数据结构与算法
课程章节：第8章 数据结构之“树”
主讲老师：lewis

课程内容：

今天学习的内容包括：
8-1 树简介——一种分层数据的抽象模型。
8-2 深度与广度优先遍历——平时使用到的树结构，进行遍历处理，类如省市区处理，组织关系等。

课程收获：

树简介

1、一种分层数据的抽象模型
2、前端工作中常见的树包括：DOM树、级联选择，树形控件…
3、js中没有树，但是可以用Object和Array构件树
4、树的常用操作：深度/广度优先遍历、先中后序遍历

什么是深度/广度优先遍历

深度优先遍历：尽可能的搜索树的分支
广度优先遍历：先访问离根节点最近的节点

深度优先遍历

1、访问根节点
2、对根节点的children挨个进行深度优先遍历

const tree = {
  val: 'a',
  children: [
    { 
      val: 'b',
      children: [
        { val: 'd' },
        { val: 'e' }
      ]
    },
    { val: 'c' ,
      children: [
        { val: 'f' },
        { val: 'g' }
      ] 
    },
  ]
}

const dfs = (root) => {
  console.log(root.val);
  root.children?.forEach(dfs);
}
dfs(tree)

广度优先遍历

1、新建一个队列，把根节点入队。
2、把队头出队并访问。
3、把队头的children挨个入队。
4、重复第二、三步，直到队列为空。

const tree = {
  val: 'a',
  children: [
    { 
      val: 'b',
      children: [
        { val: 'd' },
        { val: 'e' }
      ]
    },
    { val: 'c' ,
      children: [
        { val: 'f' },
        { val: 'g' }
      ] 
    },
  ]
}

const bfs = (root) => {
  let queue = [root];
  while(queue.length > 0){
    const node = queue.shift();
    console.log(node.val);
    node.children?.forEach(child => queue.push(child));
  }
}
bfs(tree)

通过对树的初步学习，对算法初探究竟，从时间/控件复杂度到现在的深度/广度优先遍历，处处都是那么的美妙，对自己说一句，加油😀~

坚持打卡，坚持学习！明天见💪~

​​​​

​