前端数据结构：二叉树遍历详解

前端数据结构：二叉树遍历详解

二叉树的遍历是指从根节点出发，按照某种顺序依次访问所有节点，而且只访问一次，二叉树的遍历方式很多，如果限制了从左到右的方式，那么主要有4种：

1. 先序遍历：根左右
2. 中序遍历：左根右
3. 后序遍历：左右根
4. 层序遍历：按层级、从上到下，在同一层从左到右遍历

以上一篇的二叉树为例子，先序遍历 先访问根节点，在访问左节点，在访问右节点，如图：

• 先(根)序遍历（根左右）：A、B、D、E、C、F、G
• 中(根)序遍历（左根右） : D、B、E、A、F、C、G
• 后(根)序遍历（左右根） : D、E、B、F、G、C、A
• 层序序遍历（上到下，左到右）：A、B、C、D、E、F、G

递归实现先序、中序、后序、层序遍历

二叉树的创建用上一篇链表方法存储的二叉树，只不过增加了4个遍历的方法而已。一颗大的树都是若干颗小树（根节点、左节点、右节点）构成，根节点也有可能是其他节点的左子树（树的根节点除外），所以递归遍历就是不断的递归子树的过程。

class Node {
  constructor (data = '#') {
    this.data = data
    this.lNode = null
    this.rNode = null
  }
}

class BiTree {
  root = null
  nodeList = []
  constructor (nodeList) {
    this.root = new Node()
    this.nodeList = nodeList
  }
  createNode (node) {
    const data = this.nodeList.shift()
    if (data === '#') return
    node.data = data
    // 下一个元素是不是空节点, 如果不是创建左节点
    if (this.nodeList[0] !== '#') {
      node.lNode = new Node(data)
    }
    this.createNode(node.lNode)

    // 下一个元素是不是空节点, 如果不是创建右节点
    if (this.nodeList[0] !== '#') {
      node.rNode = new Node(data)
    }
    this.createNode(node.rNode)
  }
  preorderTraverse (node) {
    if (node === null) return
    console.log(node.data)
    this.preorderTraverse(node.lNode)
    this.preorderTraverse(node.rNode)
  }
  inorderTraverse (node) {
    if (node === null) return
    this.inorderTraverse(node.lNode)
    console.log(node.data)
    this.inorderTraverse(node.rNode)
  }
  postorderTraverse (node) {
    if (node === null) return
    this.postorderTraverse(node.lNode)
    this.postorderTraverse(node.rNode)
    console.log(node.data)
  }
  sequenceTraverse (root) {
    if (!root) return
    let queue = []
    queue.push(root)
    while (queue.length) {
      const node = queue.shift()
      console.log(node.data)
      if(node.lNode) {
        queue.push(node.lNode)
      }
      if (node.rNode) {
        queue.push(node.rNode)
      }
    }
  }
}

let arr = ['A','B','D','#','#','E','#','#','C','F','#', '#', 'G', '#', '#']
let bi = new BiTree(arr)
bi.createNode(bi.root)
console.log(bi.root)

console.log('----先序----')
console.log(bi.preorderTraverse(bi.root))

console.log('----中序----')
console.log(bi.inorderTraverse(bi.root))

console.log('----后序----')
console.log(bi.postorderTraverse(bi.root))

console.log('----层序----')
console.log(bi.sequenceTraverse(bi.root))

层级遍历使用了队列来实现，思路也比较简单，一开始入队根节点，出队最后一个节点，出队时把相关左节点、右节点入队，如此循环，队列为空即遍历完成。

非递归实现先序、中序、后序

二叉树的递归遍历非常容易理解，但因为是递归调用需要在内存栈中分配内存用来保存参数，层数多了内存容易溢出。

非递归先序基本思路：使用数组来模拟栈的数据结构，首先根节点入栈，然后出栈，在出栈的时候把该节点结果放入数组，然后把相关需要的节点按要求把左右节点入栈，如此循环一直到这个栈为空。

步骤：

1. 根节点放入栈
2. 取出栈顶的节点，把该节点结果放入数组
3. 如果该右节点存在，将该节点右节点放入栈
4. 如果该左节点存在，将该节点左节点放入栈
5. 重复 1-4
6. 栈为空退出循环

preorderNonRecursion (root) {
  if (!root) return ''
  let stack = []
  let result = []
  stack.push(root)
  while (stack.length) {
    const node = stack.pop()
    result.push(node.data)

    // 如果存在右节点，先压入右节点
    if (node.rNode) {
      stack.push(node.rNode)
    }
    if (node.lNode) {
      stack.push(node.lNode)
    }
  }
  return result
}

中序、后序代码基本思路类似代码如下：

inorderNonRecursion (root) {
  if (!root) return ''
  let stack = []
  let result = []
  // stack.push(root)
  while (root !== null || stack.length) {
    // 找到左节点
    while (root !== null) {
      stack.push(root)
      root = root.lNode
    }
    root = stack.pop()
    result.push(root.data)
    // 右节点
    root = root.rNode
  }
  return result
}
postorderNonRecursion (root) {
  if (!root) return ''
  let stack = []
  let result = []
  stack.push(root)
  while (stack.length) {
    const node = stack.pop()
    result.unshift(node.data)

    if (node.lNode) {
      stack.push(node.lNode)
    }
    if (node.rNode) {
      stack.push(node.rNode)
    }
  }
  return result
}

递归遍历、非递归遍历完整代码

class Node {
  constructor (data = '#') {
    this.data = data
    this.lNode = null
    this.rNode = null
  }
}

class BiTree {
  root = null
  nodeList = []
  constructor (nodeList) {
    this.root = new Node()
    this.nodeList = nodeList
  }
  // 创建二叉树
  createNode (node) {
    const data = this.nodeList.shift()
    if (data === '#') return
    node.data = data
    // 下一个元素是不是空节点, 如果不是创建左节点
    if (this.nodeList[0] !== '#') {
      node.lNode = new Node(data)
    }
    this.createNode(node.lNode)
    // 下一个元素是不是空节点, 如果不是创建右节点
    if (this.nodeList[0] !== '#') {
      node.rNode = new Node(data)
    }
    this.createNode(node.rNode)
  }
  // 先序
  preorderTraverse (node) {
    if (node === null) return
    console.log(node.data)
    this.preorderTraverse(node.lNode)
    this.preorderTraverse(node.rNode)
  }
  // 中序
  inorderTraverse (node) {
    if (node === null) return
    this.inorderTraverse(node.lNode)
    console.log(node.data)
    this.inorderTraverse(node.rNode)
  }
  // 后序
  postorderTraverse (node) {
    if (node === null) return
    this.postorderTraverse(node.lNode)
    this.postorderTraverse(node.rNode)
    console.log(node.data)
  }
  // 层序
  sequenceTraverse (root) {
    if (!root) return
    let queue = []
    queue.push(root)
    while (queue.length) {
      const node = queue.shift()
      console.log(node.data)
      if(node.lNode) {
        queue.push(node.lNode)
      }
      if (node.rNode) {
        queue.push(node.rNode)
      }
    }
  }
  // 非递归-先序
  preorderNonRecursion (root) {
    if (!root) return ''
    let stack = []
    let result = []
    stack.push(root)
    while (stack.length) {
      const node = stack.pop()
      result.push(node.data)
      // 如果存在右节点，先压入右节点
      if (node.rNode) {
        stack.push(node.rNode)
      }
      if (node.lNode) {
        stack.push(node.lNode)
      }
    }
    return result
  }
  // 非递归-中序
  inorderNonRecursion (root) {
    if (!root) return ''
    let stack = []
    let result = []
    // stack.push(root)
    while (root !== null || stack.length) {
      // 找到左节点
      while (root !== null) {
        stack.push(root)
        root = root.lNode
      }
      root = stack.pop()
      result.push(root.data)
      // 右节点
      root = root.rNode
    }
    return result
  }
  // 非递归-后序
  postorderNonRecursion (root) {
    if (!root) return ''
    let stack = []
    let result = []
    stack.push(root)
    while (stack.length) {
      const node = stack.pop()
      result.unshift(node.data)
      if (node.lNode) {
        stack.push(node.lNode)
      }
      if (node.rNode) {
        stack.push(node.rNode)
      }
    }
    return result
  }
}

let arr = ['A','B','D','#','#','E','#','#','C','F','#', '#', 'G', '#', '#']
let bi = new BiTree(arr)
bi.createNode(bi.root)
console.log(bi.root)
console.log('----递归先序----')
console.log(bi.preorderTraverse(bi.root))
console.log('----非递归先序----')
console.log(bi.preorderNonRecursion(bi.root))
console.log('----递归中序----')
console.log(bi.inorderTraverse(bi.root))
console.log('----非递归中序----')
console.log(bi.inorderNonRecursion(bi.root))
console.log('----递归后序----')
console.log(bi.postorderTraverse(bi.root))
console.log('----非递归后序----')
console.log(bi.postorderNonRecursion(bi.root))
console.log('----层序----')
console.log(bi.sequenceTraverse(bi.root))