相关概念
「树的遍历」 指按照一定规则不重复地访问树中所有节点的过程。
「访问」指针对节点的操作，如打印节点的值，更新节点的值等。
本文讨论二叉树的遍历，对节点的访问通过打印节点的值体现出来。
从二叉树的根节点出发，遍历可分为三个环节：
- 访问节点（打印节点的值）
- 遍历节点的左子树
- 遍历节点的右子树
不同环节执行的先后顺序产生了不同的遍历方式。
「前序遍历」指先访问节点，再遍历节点的左子树，最后遍历节点的右子树，按照这种规则不重复地访问树中所有节点的过程。
「中序遍历」指先遍历节点的左子树，再访问节点，最后遍历节点的右子树，按照这种规则不重复地访问树中所有节点的过程。
「后序遍历」指先遍历节点的左子树，再遍历节点的右子树，最后访问节点，按照这种规则不重复地访问树中所有节点的过程。
前序遍历
图1 前序遍历
图1展现了前序遍历的整个过程，图中树的结构用代码表示如下
function Node(value) {
this.value = value
this.left = null
this.right = null
}
root {
value: 'A',
left: {
value: 'B',
left: {
value: 'D',
left: {
value: 'H',
left: null,
right: null
},
right: {
value: 'I',
left: null,
right: null
}
},
right: {
value: 'E',
left: null,
right: null
}
},
right: {
value: 'C',
left: {
value: 'F',
left: null,
right: null
},
right: {
value: 'G',
left: null,
right: null
}
}
}
我们要设计一个函数，用于遍历二叉树，传入的参数是二叉树的根节点，函数会先访问节点（打印节点的值），再遍历节点的左子树，最后遍历节点的右子树。
上述代码翻译成代码片段就是
/**
* 函数的作用是遍历二叉树
* 传入的参数是表示二叉树的根节点
* @param {any} root
*/
function preOrderTraverse(root){
console.log(root.value) // 访问节点（打印节点的值）
... // 遍历节点的左子树
... // 遍历节点的右子树
}
... 处应该是遍历节点的左，右子二叉树的代码。遍历二叉树不正是这个函数的作用吗？故想到了递归
function preOrderTraverse(root){
console.log(root.value) // 访问节点（打印节点的值）
preOrderTraverse(root.left) // 遍历节点的左子树
preOrderTraverse(root.right) // 遍历节点的右子树
}
添加递归的终止条件，即访问到叶节点就停止调用函数
const preOrderTraverse = root => {
console.log(root.value) // 访问节点（打印节点的值）
root.left && preOrderTraverse(root.left) // 若节点的左子树存在，则遍历节点的左子树
root.right && preOrderTraverse(root.right) // 若节点的右子树存在，则遍历节点的右子树
}
preOrderTraverse(root)
// A B D H I E C F G
举一反三
中序遍历
const inOrderTraverse = root => {
root.left && inOrderTraverse(root.left) // 若节点的左子树存在，则遍历节点的左子树
console.log(root.value) // 访问节点（打印节点的值）
root.right && inOrderTraverse(root.right) // 若节点的右子树存在，则遍历节点的右子树
}
inOrderTraverse(root)
// H D I B E A F C G
后序遍历
const postOrderTraverse = root => {
root.left && postOrderTraverse(root.left) // 若节点的左子树存在，则遍历节点的左子树
root.right && postOrderTraverse(root.right) // 若节点的右子树存在，则遍历节点的右子树
console.log(root.value) // 访问节点（打印节点的值）
}
postOrderTraverse(root)
// H I D E B F G C A
非递归遍历
随着被调用次数的增加，递归函数会线性地增加栈空间的使用。
至于二叉树的非递归遍历，且听下回分解。
