树

树是什么？

• 树是一种分层数据的抽象模型
• 前端工作中常见的树包括：DOM 树、级联选择、树型控件（目录树）

树的实现

• JS 中没有树这个数据结构，使用 Object 和 Array 来构建树

  {
    value: 'zhejiang',
    label: 'zhejiang',
    children: [
      {
        value: 'hangzhou',
        label: 'Hangzhou',
        children: [
          {
            value: 'xihu',
            label: 'Xihu'
          }
        ]
      }
    ],
  }

树的常用操作

深度优先遍历（DFS）

• 尽可能深的搜索树的分支（数字代表访问的顺序）

• 算法口诀
  1. 访问根节点
  2. 对根节点的 children 挨个进行深度优先遍历
• 代码实现 ```javascript const root = { val: ‘a’, children: [

    {
        val: 'b',
        children: [
            {
                val: 'd',
                children: [],
            },
            {
                val: 'e',
                children: [],
            }
        ],
    },
    {
        val: 'c',
        children: [
            {
                val: 'f',
                children: [],
            },
            {
                val: 'g',
                children: [],
            }
        ],
    }

  ], }

getResult(root) { // 1.定义结果数组 let result = []; // 2.定义递归函数 const dfs = (root) => { // 访问根节点 console.log(root.val); result.push(root.val); // 对根节点的 children 挨个进行深度优先遍历 root.children.forEach(element => { dfs(element); }); // 可缩写为 root.children.forEach(dfs) } // 3.调用递归函数 dfs(root); // 4.返回结果 return result; }

<a name="TYOjl"></a>
#### 广度优先遍历
- 先访问离根节点最近的节点
![](https://cdn.nlark.com/yuque/0/2022/jpeg/136255/1650223556294-2af80242-bc14-4fdf-932e-2bca7a424107.jpeg)
- 算法口诀
   - ① 新建一个队列，把根节点入队
   - ② 把队头出队并访问
   - ③ 把队头的 children 挨个入队
   - ④ 重复 ②、③ 步，直到队列为空
- 代码实现
```javascript
const root = {
    val: 'a',
    children: [
        {
            val: 'b',
            children: [
                {
                    val: 'd',
                    children: [],
                },
                {
                    val: 'e',
                    children: [],
                }
            ],
        },
        {
            val: 'c',
            children: [
                {
                    val: 'f',
                    children: [],
                },
                {
                    val: 'g',
                    children: [],
                }
            ],
        }
    ],
}
getResult(root) {
    // 1.定义结果数组
    let result = [];
    // 2.定义递归函数
    const bfs = (root) => {
        // 新建一个队列，把根节点放入
        let q = [root];
        // 循环执行
        while(q.length > 0) {
            // 队列头节点出队
            let n = q.shift();
            // 访问头节点
            console.log(n.val);
            result.push(n.val);
            n.children.forEach(child => {
                q.push(child);
            })
        }
    }
    // 3.调用递归函数
    bfs(root);
    // 4.返回结果
    return result;
}

二叉树特有 - 先中后序遍历

二叉树的先序遍历（深度优先遍历），注意 JS 闭包的使用

var preorderTraversal = function (root) {
    // 首先声明一个数组用来存放遍历得到的节点val值
    const result = []
    // 定义递归函数
    function preorder(node) {
        // 如果节点为空直接返回
        if (!node) return
        // 先序遍历就是把当前节点输出 放在左右递归调用之前 将其数值放入结果数组
        result.push(node.val)
        // 然后递归遍历左孩子
        preorder(node.left)
        // 最后递归遍历右孩子
        preorder(node.right)
    }
    preorder(root)
    // 返回结果
    return result
};