二叉树的遍历就是以一定的顺序规则，逐个访问二叉树的所有结点
按照顺序规则的不同，最常见的有三种遍历顺序
- 1.先序遍历
- 2.中序遍历
- 3.后序遍历
最常见的遍历方法就是使用递归遍历
编程语言中，函数Func(Type a,……)直接或间接调用函数本身，则该函数称为递归函数。
用人话来说递归就是一个函数反复调用它自己.
在写递归函数时要确定两个点：
- 一是 递归式：它指的是你每一次重复的内容是什么。
- 二是 递归边界：它指的是你什么时候停下来。
如果你还不了解树与二叉树的区别，可以看这一篇文章：# 树和二叉树的特点与异同
我们先把树用代码表示一下：
const root = { val: "A", left: { val: "B", left: { val: "D" }, right: { val: "E" } }, right: { val: "C", right: { val: "F" } } };
先序遍历
先序遍历就是先遍历根节点，再遍历左子树最后遍历右子树
- 根节点 -> 左子树 -> 右子树
先来个简单的
这个树先序遍历的结果一眼可以看出是： A,B,C
接下来就用代码来验证一下，我们用递归代码实现就是：
具体步骤就是：
- 第一步：判断边界，把节点为空当做边界，如果当前节点为空就直接返回
- 第二步：打印
root.val - 第三步： 把左子树当做根节点，调用函数
- 第四步： 把右子树当做根节点，调用函数
// 所有遍历函数的入参都是树的根结点对象 function preorder(root) { // 递归边界，root 为空 if(!root) { return } // 输出当前遍历的结点值 console.log('当前遍历的结点值是：', root.val) // 递归遍历左子树 preorder(root.left) // 递归遍历右子树 preorder(root.right) }
如果说有 N 多个子树，那么我们在每一棵子树内部，都要重复这个顺序：
先序遍历的编码实现也是这样，最终打印的结果：
中序遍历
理解了先序遍历那么中序遍历和后序遍历就好理解了
唯一的区别只是把遍历顺序调换了：左子树 -> 根结点 -> 右子树：
先来个简单的
这个树先序遍历的结果一眼可以看出是： B,A,C
与先序遍历的区别就是递归式里调用递归函数的顺序，第二步与第三步调换一下
接下来就用代码来验证一下
具体步骤就是：
- 第一步：判断边界，把节点为空当做边界，如果当前节点为空就直接返回
- 第二步：把左子树当做根节点，调用函数
- 第三步： 打印
root.val - 第四步： 把右子树当做根节点，调用函数
function inorder(root) { // 递归边界，root 为空 if(!root) { return } // 递归遍历左子树 inorder(root.left) // 输出当前遍历的结点值 console.log('当前遍历的结点值是：', root.val) // 递归遍历右子树 inorder(root.right) }
输出结果就是：
当前遍历的结点值是： D 当前遍历的结点值是： B 当前遍历的结点值是： E 当前遍历的结点值是： A 当前遍历的结点值是： C 当前遍历的结点值是： F
后序遍历
在后序遍历中，我们先访问左子树，再访问右子树，最后访问根结点
先来个简单的
这个树先序遍历的结果一眼可以看出是： B,C,A
与先序遍历的区别就是递归式里调用递归函数的顺序，最后再输出节点值。
接下来就用代码来验证一下
具体步骤就是：
- 第一步：判断边界，把节点为空当做边界，如果当前节点为空就直接返回
- 第二步：把左子树当做根节点，调用函数
- 第三步： 把右子树当做根节点，调用函数
- 第四步：打印
root.val
function postorder(root) { // 递归边界，root 为空 if(!root) { return } // 递归遍历左子树 postorder(root.left) // 递归遍历右子树 postorder(root.right) // 输出当前遍历的结点值 console.log('当前遍历的结点值是：', root.val) }
输出结果就是：
当前遍历的结点值是： D 当前遍历的结点值是： E 当前遍历的结点值是： B 当前遍历的结点值是： F 当前遍历的结点值是： C 当前遍历的结点值是： A
