第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)
}

中序遍历