[数据结构与算法]树的各种遍历总结

一、写在前面
本篇博客主要是对树的一些遍历方式进行总结，其中包含树的深度优先遍历，和树的广度优先遍历，以及二叉树的先中后序遍历，其中先中后序遍历分别使用递归版本的遍历方式和非递归版本的递归方式。
二、树的深度优先遍历和广度优先遍历

如上图所示为我们需要遍历的数结构。

数据可以整理为：
const tree = {
  val: 'a',
  children: [{
      val: 'b',
      children: [{
          val: 'd',
          children: [],
        },
        {
          val: 'e',
          children: [],
        }
      ],
    },
    {
      val: 'c',
      children: [{
          val: 'f',
          children: [],
        },
        {
          val: 'g',
          children: [],
        }
      ],
    }
  ],
};

深度优先遍历

const dfs = (root) => {
  console.log(root.val)
  root.children.forEach(item => {
    dfs(item)
  })
}

dfs(tree)

广度优先遍历

const bfs = (node) => {
  let queue = [node]
  while(queue.length > 0) {
    let curNode = queue.shift()
    console.log(curNode.val)
    let child = curNode.children
    if(child && child.length > 0) {
      child.forEach(item => {
        queue.push(item)
      })
    }   
  }
}

bfs(tree)

总结：树的深度优先遍历使用的是递归，树的广度优先遍历使用的是：队列这种数据结构。
三、二叉树的先中后序遍历
database

const dbs = {
  val: 4,
  left: {
    val: 3,
    left: {
      val: 2,
      left: null,
      right: null
    },
    right: {
      val: 1,
      left: null,
      right: null
    }
  },
  right: {
    val: 5,
    left: {
      val: 6,
      left: null,
      right: null
    },
    right: {
      val: 7,
      left: null,
      right: null
    }
  }
}

先序遍历

const preorder = (root) => {
  if(!root) return
  console.log(root.val)
  if(root.left) preorder(root.left)
  if(root.right) preorder(root.right)
}
preorder(dbs)

中序遍历

const midorder = (root) => {
  if(!root) return 
  if(root.left) midorder(root.left)
  console.log(root.val)
  if(root.right) midorder(root.right)
}
midorder(dbs)

后序遍历

const afterorder = (root) => {
  if(!root) return
  if(root.left) afterorder(root.left)
  if(root.right) afterorder(root.right)
  console.log(root.val)
}

afterorder(dbs)  

上述递归版的遍历方式太简单了，下面是非递归版的写法。
先序遍历——非递归版:使用数据结构栈

const preorder = (root) => {
  if (!root) return
  let stack = [root]
  while (stack.length > 0) {
    let cur = stack.pop()
    console.log(cur.val)
    if(cur.right) stack.push(cur.right)
    if(cur.left) stack.push(cur.left)
  }
}
preorder(dbs)

中序遍历——非递归版

const midorder = (root) => {
  if(!root) return 
  let stack = []
  let p = root
  while(stack.length > 0 || p) {
    while(p) {
      stack.push(p)
      p = p.left
    }
    let cur = stack.pop()
    console.log(cur.val)
    p = cur.right
  }
}

midorder(dbs)

后序遍历——非递归版

const postorder = (root) => {
  if(!root) return
  let stack1 = [root]
  let stack2 = []
  while(stack1.length > 0) {
    let cur = stack1.pop()
    stack2.push(cur)
    if(cur.left) stack1.push(cur.left)
    if(cur.right) stack1.push(cur.right)
  }
  while(stack2.length > 0) {
    let cur = stack2.pop()
    console.log(cur.val)
  }
}
postorder(dbs)