树是一种数据结构，它是由n(n≥0)个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：
每个节点有零个或多个子节点；没有父节点的节点称为根节点；每一个非根节点有且只有一个父节点；除了根节点外，每个子节点可以分为多个不相交的子树。

• 深度优先遍历/广度优先遍历

const tree = {
  name: 'node-1',
  children: [
    {
      name: 'node-2',
      children: [
        {
          name: 'node-6',
          children: []
        }
      ]
    }, 
    {
      name: 'node-3',
      children: [
        {
          name: 'node-4',
          children: []
        },
        {
          name: 'node-5',
          children: []
        }
      ]
    }
  ]
}
//深度优先
const dfs = (node) => {
  console.log(node.name)
  node.children.forEach(dfs)
}
dfs(tree)
//node-1
//node-2
//node-6
//node-3
//node-4
//node-5

//广度优先
const bfs = (node) => {
  const queue = [node]
  while (queue.length) {
    const head = queue.shift()
    console.log(head.name)
    head.children.forEach(child => queue.push(child))
  }
}
bfs(tree)
//node-1
//node-2
//node-3
//node-6
//node-4
//node-5

二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个节点最多只能有两棵子树，且有左右之分 ^[1] 。
二叉树是n个有限元素的集合，该集合或者为空、或者由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个节点 ^[1] 。

const binaryTree = {
  name: 'node-1',
  left: {
    name: 'node-2',
    left: {
      name: 'node-4',
      left: null,
      right: null
    },
    right: {
      name: 'node-5',
      left: null,
      right: {
        name: 'node-8',
        left: null,
        right: null
      }
    }
  },
  right: {
    name: 'node-3',
    left: {
      name: 'node-6',
      left: null,
      right: null
    },
    right: {
      name: 'node-7',
      left: null,
      right: null
    }
  }
}

• 先序遍历/中序遍历/后序遍历（递归）

//先序遍历
const preorder = (node) => {
  if (!node) return
  console.log(node.name)
  preorder(node.left)
  preorder(node.right)
}
preorder(binaryTree)
// node-1
// node-2
// node-4
// node-5
// node-8
// node-3
// node-6
// node-7

//中序遍历
const inorder = (node) => {
  if (!node) return
  inorder(node.left)
  console.log(node.name)
  inorder(node.right)
}
inorder(binaryTree)
// node-4
// node-2
// node-5
// node-8
// node-1
// node-6
// node-3
// node-7

//后序遍历
const postorder = (node) => {
  if (!node) return
  postorder(node.left)
  postorder(node.right)
  console.log(node.name)
}
postorder(binaryTree)
// node-4
// node-8
// node-5
// node-2
// node-6
// node-7
// node-3
// node-1

• 先序遍历/中序遍历/后序遍历（使用栈实现）

//先序遍历
const preorder = (node) => {
  if (!node) return
  const stack = [node]
  while (stack.length) {
    const head = stack.pop()
    console.log(head.name)
    if (head.right) {
      stack.push(head.right)
    }
    if (head.left) {
      stack.push(head.left)
    }
  }
}
preorder(binaryTree)
// node-1
// node-2
// node-4
// node-5
// node-8
// node-3
// node-6
// node-7

//中序遍历
const inorder = (node) => {
  if (!node) return
  const stack = []
  let p = node
  while (stack.length || p) {
    while (p) {
      stack.push(p)
      p = p.left
    }
    const head = stack.pop()
    console.log(head.name)
    p = head.right
  }
}
inorder(binaryTree)
// node-4
// node-2
// node-5
// node-8
// node-1
// node-6
// node-3
// node-7

//后序遍历
const postorder = (node) => {
  if (!node) return
  const stack = [node]
  const outputStack = []
  while (stack.length) {
    const head = stack.pop()
    outputStack.push(head.name)
    if (head.left) {
      stack.push(head.left)
    }
    if (head.right) {
      stack.push(head.right)
    }
  }
  while (outputStack.length) {
    const head = outputStack.pop()
    console.log(head)
  }
}
postorder(binaryTree)
// node-4
// node-8
// node-5
// node-2
// node-6
// node-7
// node-3
// node-1