树

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

深度优先遍历

• 深度优先遍历：尽可能深的搜索树的分支。

深度优先遍历算法口诀：

• 访问根节点
• 对根节点children挨个进行深度优先遍历。 ```javascript 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 = (root) => { console.log(root.val); // root.children.forEach((child)=> {dfs(child)}) root.children.forEach(dfs) }

<a name="zvgWp"></a>
## 广度优先遍历

- 先访问离根节点最近的节点
<a name="rbY3s"></a>
### 广度优先遍历算法口诀：

- 新建一个队列，把根节点入队。
- 把队头出队并访问。
- 把队头的children挨个入队。
- 重复第二、三步，直到队列为空。
```javascript
const bfs = (root) => {
    const q = [root];
    while(q.length > 0) {
        const n = q.shift();
        console.log(n.val);
        n.children.forEach(child => {
            q.push(child);
        })
    }
}

bfs(tree)

二叉树的先中后序遍历

二叉树是什么？

• 树中每个节点最多只能有两个子节点
• 在JS中通常用Object来模拟二叉树

const binaryTree = {
    val:1,
    left: {
      val:2,
      left: null,
      right: null
    },
    right: {
      val:3,
      left: null,
      right: null
    },
}

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

module.exports = bt

先序遍历算法口诀

• 访问根节点
• 对根节点左子树进行先序遍历。
• 对根节点的右子树进行先序遍历

递归版

const bt = require("./bt");

const preorder = (root) => {
      //判断root存不存在
    if(!root) { return;}
    console.log(root.val);
     preorder(root.left);
       preorder(root.right);
}

preorder(bt)
// 1 2 4 5 3 6 7

非递归版

用堆栈来模拟递归的过程。

const preorder = (root) => {
    if(!root) { return;}
    const stack = [root];
    //如果在函数里面调用另一个函数，就会向这个栈里推入一个函数
    //如果函数执行完了，就释放栈顶元素
    while(stack.length) {
        const n = stack.pop();
        console.log(n.val);
        // 栈是后进先出的，所以先要push  right
        if(n.right) stack.push(n.right)
        if(n.left) stack.push(n.left);
    }
}


preorder(bt)
// 1 2 4 5 3 6 7

中序遍历算法口诀

• 对根节点的左子树进行中序遍历
• 访问根节点
• 对根节点的右子树进行中序遍历

递归版

const bt = require("./bt");

const inorder = (root) => {
    if(!root) { return;}
    inorder(root.left);
    console.log(root.val)
    inorder(root.right)
}
inorder(bt)
//4 2 5 1 6 3 7

非递归版

const bt = require("./bt");

const inorder = (root) => {
    if(!root) { return;}
    const stack = [];
    let p = root;
    while(stack.length || p) {
        while(p) {
            stack.push(p)
            p = p.left;
        }
        const n = stack.pop();
        console.log(n.val);
        p = n.right;
    }
}
inorder(bt)
//4 2 5 1 6 3 7

后序遍历算法口诀

• 对根节点的左子树进行后序遍历。
• 对根节点的右子树进行后序遍历。
• 访问根节点。

递归版

const bt = require("./bt");

const postorder = (root) => {
    if(!root) { return;}
    postorder(root.left);
    postorder(root.right);
    console.log(root.val);
}
postorder(bt)

// 4 5 2 6 7 3 1

非递归版

首先后序遍历顺序是左右根。我们可以把它倒过来变成根右左。就和先序遍历有点类似了，把先序遍历的访问操作变成入栈操作。最后利用栈的后进先出的特点，再把子节点逆序输出再访问，就实现了后序遍历。

const bt = require("./bt");
const postorder = (root) => {
    if(!root) { return;}
    const stack = [root];
    const outputStack = [];
    while(stack.length) {
        const n = stack.pop();
        outputStack.push(n);
        if(n.left) stack.push(n.left);
        if(n.right) stack.push(n.right);
    }

    while(outputStack.length) {
        const n = outputStack.pop();
        console.log(n.val)
    }
}

postorder(bt)
// 4 5 2 6 7 3 1