二叉树

在计算机科学中，二叉树（英语：Binary tree）是每个节点最多只有两个分支（即不存在分支度大于 2 的节点）的树结构。通常分支被称作“左子树”或“右子树”。

二叉树遍历

先序遍历

先遍历自己，然后再遍历左节点，最后遍历右节点

// 先序遍历
module.exports = function preorderTraversal(node) {
  if (node) {
    console.log(node.value)
    preorderTraversal(node.left)
    preorderTraversal(node.right)
  }
}

中序遍历

先遍历左节点，然后再遍历自己，最后遍历右节点

// 中序遍历
module.exports = function middleOrderTraversal(node) {
  if (node) {
    preorderTraversal(node.left)
    console.log(node.value)
    preorderTraversal(node.right)
  }
}

后序遍历

先遍历左节点，然后再遍历右节点，最后遍历自己

// 后序遍历
module.exports = function postorderTraversal(node) {
  if (node) {
    preorderTraversal(node.left)
    preorderTraversal(node.right)
    console.log(node.value)
  }
}

广度优先遍历

广度优先遍历即为，二叉树一层一层的遍历。

// 广度优先遍历
module.exports = function breadthTraversa(node) {
  const queen = []
  if (node) {
    queen.push(node)
  }
  while (queen.length) {
    const n = queen.shift()
    console.log(n.value)
    if (n.left) queen.push(n.left)
    if (n.right) queen.push(n.right)
  }
}

计算二叉树深度

获得二叉树深度

module.exports = function(node) {
  const queen = []
  let depth = 0

  if (node) {
    queen.push(node)
  }

  while (queen.length) {
    let len = queen.length
    depth++
    while (len > 0) {
      len--
      const n = queen.shift()
      if (n.left) queen.push(n.left)
      if (n.right) queen.push(n.right)
    }
  }

  return depth
}