二叉树的遍历

在之前的二叉树章节当中，我们介绍了二叉树的定义以及性质，所以本章我们就重点来看看二叉树遍历的相关内容

二叉树的遍历

二叉树的遍历（traversing binary tree）是指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次的遍历方式，这里需要注意上文提及的两个概念『某种次序依次访问』和『访问一次且仅被访问一次』

这是因为二叉树的遍历次序不同于线性结构，因为线性结构最多也就是分为顺序、循环、双向等简单的遍历方式，而树的结点之间不存在唯一的前驱和后继这样的关系，所以在访问一个结点后，下一个被访问的结点面临着不同的选择，所以二叉树的遍历方式就可以有很多，在这里我们简单的总结一下，主要分为以下四种遍历方式

前序遍历
中序遍历
后序遍历
层序遍历

有个比较简单的记忆方式就是

先序遍历，根 ==> 左 ==> 右
中序遍历，左 ==> 根 ==> 右
中序遍历，左 ==> 右 ==> 根

可以发现，前中后的遍历顺序是看『根结点』放在何处来决定的，下面我们就借助下方这个二叉树的图（注意不是完全二叉树），一个一个来进行了解

前序遍历

基本逻辑是，如果二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树，顺序如下图所示

遍历的顺序为 A ==> B ==> D ==> H ==> I ==> E ==> J ==> C ==> F ==> K ==> G

中序遍历

若树为空，则空操作返回，否则从根结点开始（注意并不是先访问根结点），中序遍历根结点的左子树，然后是访问根结点，最后中序遍历右子树，顺序如下图所示

遍历的顺序为 H ==> D ==> I ==> B ==> E ==> J ==> A ==> F ==> K ==> C ==> G

后序遍历

若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后访问根结点，顺序如下图所示

遍历的顺序为 H ==> I ==> D ==> J ==> E ==> B ==> K ==> F ==> G ==> C ==> A

层序遍历

这个也是我们最好理解的方式，就是一层一层的遍历，若树为空，则空操作返回，否则从树的第一层，也就是根结点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问，顺序如下图所示

遍历的顺序为 A ==> B ==> C ==> D ==> E ==> F ==> G ==> H ==> I ==> J ==> K

二叉树的建立和遍历

我们直接来看如何用代码进行实现

// 首先创建一个类来表示二叉树，它的内部有一个 Node 类，用来创建节点
class Node {
  constructor(key) {
    this.key = key
    this.left = null
    this.right = null
  }
}

class BinaryTree {
  constructor() {
    this.root = null
  }

  // 插入数据
  insert(key) {
    // 传入需要插入的 key 值，它会自动初始化为左右节点为 null 的一个新节点
    var newNode = new Node(key)
    if (this.root == null) {
      this.root = newNode
    } else {
      var current = this.root
      // 通过循环来找到新添加节点的合适位置
      while (true) {
        if (key < current.key) {
          if (current.left) {
            current = current.left
          } else {
            current.left = newNode
            break
          }
        } else if (key > current.key) {
          if (current.right) {
            current = current.right
          } else {
            current.right = newNode
            break
          }
        }
      }
    }
  }

  // 中序遍历
  centerSort(node) {
    // 检查传入的 node 是否为 null，如果不为空，就继续递归调用自身检查 node 的 left、right 节点
    if (node) {
      this.centerSort(node.left)
      console.log(node.key)
      this.centerSort(node.right)
    }
  }

  // 前序遍历
  prevSort(node) {
    if (node) {
      console.log(node.key)
      this.prevSort(node.left)
      this.prevSort(node.right)
    }
  }

  // 后续遍历
  nextSort(node) {
    if (node) {
      this.nextSort(node.left)
      this.nextSort(node.right)
      console.log(node.key)
    }
  }
}

var arr = [13, 21, 15, 29, 3, 55]
var bst = new BinaryTree()

arr.map(item => {
  bst.insert(item)
})

bst.centerSort(bst.root)
// bst.prevSort(bst.root)
// bst.nextSort(bst.root)