JS二叉树遍历

function Node(value){
  this.value= value
}

let a = new Node('a')
let b = new Node('b')
let c = new Node('c')
let d = new Node('d')
let e = new Node('e')
let f = new Node('f')
let g = new Node('g')

a.left = b
a.right = c
b.left = d
d.right = g
c.left = e
c.right = f

// 前序遍历，遍历顺序为：'根左右'
function walk(root) {
  if(!root) return
  console.log(root.value)
  walk(root.left)
  walk(root.right)
}
walk(a)

// 中序遍历，遍历顺序为：'左根右'
function walk1(root) {
  if(!root) return
  walk1(root.left)
  console.log(root.value)
  walk1(root.right)
}
walk1(a)

// 后序遍历，遍历顺序为：'左右根'
function walk2(root) {
  if(!root) return
  walk2(root.left)
  walk2(root.right)
  console.log(root.value)
}
walk2(a)

// 层序遍历
function walk3(root) {
  if(!root) return
  let nodes = []
  nodes.push(root)
  while(nodes.length) {
    const node = nodes.shift()
    console.log(node.value)
    if (node.left) {
      nodes.push(node.left)
    }
    if (node.right) {
      nodes.push(node.right)
    }
  }
}
walk3(a) // 输出 a,b,c,d,e,f,g