第8章：树

1.树是什么

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

深度 / 广度遍历

深度优先遍历：尽可能深的搜索树的分支。如下图深度访问顺序：

广度优先遍历：先访问离跟节点最近的节点。

标题，目录，深入看每个目录下的小节。

深度优先遍历算法口诀：（其实就是一个递归）

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

只有2步，写代码也只有2行代码，但是这2行代码实现了深度优先递归，在遍历的过程中被反复调用很多次。

const tree = {val: 'a',children: [{val: 'b',children: [{val: 'd',children: []},{val: 'e',children: []}]},{val: 'c',children: [{val: 'f',children: []},{val: 'g',children: []}]}]
}
const dfs = function (tree) {console.log(tree.val)// root.children.forEach((child) => dfs(child))root.children.forEach(dfs)
}

广度优先遍历算法口诀（对列）

1.新建一个队列，把根节点入队
2.把队头出队并访问
3.把队头的children挨个入队
4.重复第2，3步，知道队列为空。

const root = {val: 'a',children: [{val: 'b',children: [{val: 'd',children: []},{val: 'e',children: []}]},{val: 'c',children: [{val: 'f',children: []},{val: 'g',children: []}]}]
}const bfs = function (root) {const q = [root]while(q.length > 0) {const n = q.shift()console.log(n.val)if (n.children) {n.children.forEach(child => {q.push(child)})}}
}

二叉树的先，中， 后序的三种遍历

1.二叉树：树中每个树的节点最多有2个节点
2.在js中通常用Object来模拟二叉树

先序遍历：（根，左，右）

1.访问根节点
2.对结节点的左子树进行先序遍历
3.对根节点的右子树进行先序遍历

如上图：访问顺序：1，2， 4， 5，3, 6， 7

const bt = {val: 1,left: {val: 2,left: {val: 4,left: {},right: {}},right: {val: 5,left: {},right: {}}},right: {val: 3,left: {val: 6,left: {},right: {}},right: {val: 7,left: {},right: {}}}}const preorder = function (root) {if (!root) return // 访问根节点console.log(root.val)preorder(root.left)preorder(root.right)
}

中序遍历