二叉树遍历算法

// 定义结点TreeNode类
class TreeNode {
  node
  left
  right

  constructor(node) {
    this.node = node
    this.left = null
    this.right = null
  }
}

// 前序遍历生成二叉树
const creatTree = (list) => {
  const n = list.length
  if (n === 0) {
    return null
  }
  const node = new TreeNode(list[0])
  // 分割数组
  const index = (n - 1) / 2 + 1
  const left = list.slice(1, index)
  const right = list.slice(index)
  node.left = creatTree(left)
  node.right = creatTree(right)
  return node
}

creatTree(['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'])

// 递归遍历
const getDLR = (tree, DLR) => {
  if (tree) {
    DLR.push(tree.node)
    getDLR(tree.left, DLR)
    getDLR(tree.right, DLR)
  }
  return DLR
}
getDLR(tree, [])

// 非递归遍历
const getDLR = (tree, DLR) => {
  if (tree) {
    const stack = [tree] // 将二叉树压入栈
    while (stack.length !== 0) {
      tree = stack.pop() // 取栈顶
      DLR.push(tree.node)
      // 先右后左，栈是先进后出
      if (tree.right) stack.push(tree.right) // 把右子树入栈
      if (tree.left) stack.push(tree.left) // 把左子树入栈
    }
  }
  return DLR
}
getDLR(tree, [])

// ['A','B','C','D','E','F','G','H','I']

// 递归遍历
const getLDR = (tree, LDR) => {
  if (tree) {
    getLDR(tree.left, LDR)
    LDR.push(tree.node)
    getLDR(tree.right, LDR)
  }
  return LDR
}
getLDR(tree, [])

// 非递归遍历
const getLDR = (tree, LDR) => {
  if (tree) {
    const stack = [] // 建空栈
    // 如果栈不为空或结点不为空，则循环遍历
    while (stack.length !== 0 || tree) {
      //如果结点不为空
      if (tree) {
        stack.push(tree) // 将结点压入栈
        tree = tree.left // 将左子树作为当前结点
      } else {
        tree = stack.pop() // 将结点取出
        LDR.push(tree.node)
        tree = tree.right // 将右结点作为当前结点
      }
    }
  }
  return LDR
}
getLDR(tree, [])

// ['C','B','D','E','A','G','F','H','I']

// 递归遍历
const getLRD = (tree, LRD) => {
  if (tree) {
    getLRD(tree.left, LRD)
    getLRD(tree.right, LRD)
    LRD.push(tree.node)
  }
  return LRD
}
getLRD(tree, [])

// 非递归遍历
const getLRD = (tree, LRD) => {
  if (tree) {
    const stack = [tree] // 将二叉树压入栈
    let tmp = null // 定义缓存变量
    while (stack.length !== 0) {
      tmp = stack[stack.length - 1] // 将栈顶的值保存在tmp中
      // 如果存在左子树,node !== tmp.left && node !== tmp.righ 是为了避免重复将左右子树入栈
      if (tmp.left && tree !== tmp.left && tree !== tmp.right) {
        stack.push(tmp.left) // 将左子树结点压入栈
      } else if (tmp.right && tree !== tmp.right) {
        // 如果结点存在右子树
        stack.push(tmp.right) // 将右子树压入栈中
      } else {
        const out = stack.pop().node
        LRD.push(out)
        tree = tmp
      }
    }
  }
  return LRD
}
getLRD(tree, [])

// ['C','E','D','B','G','I','H','F','A']

const breadthTraversal = (tree, BRT) => {
  if (tree) {
    const queue = [tree] // 将二叉树放入队列
    while (queue.length !== 0) {
      tree = queue.shift() // 从队列中取出一个结点
      BRT.push(tree.node)
      // 如果存在左子树，将左子树放入队列
      if (tree.left) queue.push(tree.left)
      // 如果存在右子树，将右子树放入队列
      if (tree.right) queue.push(tree.right)
    }
  }
  return BRT
}
breadthTraversal(tree, [])

// ['A','B','F','C','D','G','H','E','I']