二叉树中的遍历方法——DFS、BFS以及迭代法
前言
在数据结构中，树是一种非线性的数据结构。
-
节点：树中的基本元素，包含数据信息。
-
根节点：树中最顶层的节点，一棵树只有一个根节点。
-
子节点：一个节点的直接下属节点。
-
父节点：一个节点的直接上级节点。
-
叶子节点：没有子节点的节点。
-
分支：节点之间的连接关系。
-
层次：从根节点开始计算，根节点为第一层，根节点的子节点为第二层。
-
树的高度：从根节点到最深叶子节点的最长路径长度（边数）。
二叉树
二叉树的定义与基本概念
二叉树是每个节点最多有两个子树的有序树结构。这两个子树通常被称为左子树和右子树。一个节点如果没有子节点，称为叶子节点。二叉树可以为空（即没有节点），或者由一个根节点以及两个互不相交的子二叉树（左子树和右子树）组成。
- 节点的度不超过 2，即节点最多有两个分支。
- 二叉树可以为空，即没有节点。
- 左子树和右子树也是二叉树。
- 二叉树具有有序性，即左右子树是有明确区分的。
那么在js中如何表示一颗二叉树呢？
function TreeNode(val) {
this.val = val;
this.left = null;
this.right = null;
}
// 根节点val1
const node = new TreeNode(1)
const node2 = new TreeNode(2)
const node3 = new TreeNode(3)
// 左子节点val2
node.left = node2
// 右子节点val3
node.right = node3
这样就简单的表示了一颗根节点为1，左子树为2，右子树为3的二叉树啦。
那么在对象中如何表示一颗二叉树呢？
const root = {
val: 1,
left: {
val: 2,
left: {
val: 4,
left: null,
right: null
}
, right: {
val: 5,
left: null,
right: null
}
},
right: {
val: 3,
left: null,
right: {
val: 6,
left: null,
right: null
}
}
}
这样我们就创建了一个如下图所示的二叉树啦。
二叉树的特点
- 有序性：二叉树的子树是有顺序的，分为左子树和右子树。
- 节点度数：二叉树中任何节点的度（子节点数量）不超过2。
- 递归结构：二叉树的定义是递归的，每个节点都可以看作一个小的二叉树的根。
二叉树的常见类型
- 满二叉树：所有非叶子节点都有两个子节点的二叉树，每一层都是满的。
- 完全二叉树：除了最后一层外，所有层都是满的，且最后一层的叶子节点尽可能靠左排列。
- 二叉查找树（BST）：左子树上所有节点的值小于它的根节点的值，右子树上所有节点的值大于它的根节点的值。
- 平衡二叉树：一种特殊的二叉查找树，左右两个子树的高度差的绝对值不超过1，确保了高效的查找性能.
二叉树的遍历方法
深度优先搜索（DFS）
深度优先搜索是一种递归或栈驱动的算法，它沿着一条路径深入探索图或树的结构，直到到达该路径的末端（通常是叶子节点或死胡同），然后回溯并探索下一条路径。具体来说：
- 过程：从起始节点开始，DFS选择一个分支进入，一直向前探索，直到到达一个叶子节点或者无法继续前进的节点，然后回退到上一步的节点，探索其下一个未访问的相邻节点。
- 数据结构：通常使用栈来实现DFS，因为栈的后进先出特性符合深度探索的逻辑。
- 特性：DFS不保证找到的是最短路径，但它对于寻找是否存在路径较为有效。
在二叉树中运用深度优先搜索时，主要有三种遍历方法：
接下来我就以这颗二叉树给大家详细介绍一下这三种方法是如何实现的哈：
法一 先序遍历
首先访问当前节点，然后递归地遍历左子树，最后遍历右子树。访问顺序为：根 -> 左 -> 右。（124536）
// 定义先序遍历函数，接收一个参数 root，即当前正在访问的节点
function preorder(root) {
// 如果当前节点为空（，则直接返回
if (!root) return
// 访问当前节点：打印当前节点的值
console.log(root.val);
// 递归遍历左子树：调用 preorder 函数，传入当前节点的左子节点作为新的根节点
preorder(root.left)
// 递归遍历右子树：调用 preorder 函数，传入当前节点的右子节点作为新的根节点
preorder(root.right)
}
最后输出的结果就为124536
法二 中序遍历
先递归遍历左子树，然后访问当前节点，最后遍历右子树。访问顺序为：左 -> 根 -> 右。（425136）
//中序遍历
function inorder(root) {
if(!root) return
inorder(root.left)
console.log(root.val);
inorder(root.right)
}
inorder(root)
同样的，中序遍历和先序遍历的思路差不多，递归的出口仍然是看root是否为空，为空的话则直接返回，不为空的话，就先调用本身这个函数递归遍历左子树，在访问当前节点，也就是根节点。最后再递归的调用右子树，在左子树和根节点都访问完之后，再去访问右子树的所有节点。最中输出的结果就是452631.
相信说到这里，后序遍历你自己也能知道怎么写了叭。就是最后输出根节点嘛
法三 后序遍历
先递归遍历左子树和右子树，最后访问当前节点。访问顺序为：左 -> 右 -> 根。
// 后序遍历
function lastorder(root) {
if(!root) return
lastorder(root.left)
lastorder(root.right)
console.log(root.val);
}
lastorder(root)
它和先序和中序遍历的代码都差不多，只是访问根节点的顺序不一样，同样递归出口为判断root是否为空，确保深度遍历到底，先递归的遍历左子树，再递归的遍历右子树，当左右子树都遍历完之后再遍历根节点。最后输出452631.
以上三种方法都是通过递归来实现遍历的，如果面试官问你有没有其他方法，不使用递归来实现遍历呢？有！咱们还可以通过迭代方法来实现。
法四 迭代遍历
迭代遍历也就是通过用栈和数组来实现的，通过在不同时间控制节点的入栈和出栈顺序，在将出栈后的节点存入一个新数组中实现。
这里咱们给大家讲一下先序遍历是如何用迭代法来实现的：
var preorderTraversal = function(root) {
if (!root) return []
const res = []
const stack = []
stack.push(root)
while (stack.length) {
const cur = stack.pop()
res.push(cur.val)
if (cur.right) {
stack.push(cur.right)
}
if (cur.left) {
stack.push(cur.left)
}
}
return res
};
console.log(preorderTraversal(root));
这里咱们首先将根节点root压入栈中，作为遍历的起点，在while循环中，每次从栈顶弹出一个节点赋值给cur，并将cur的值加入结果数组res中,表示当前节点已被访问。在利用栈访问子节点时，要遵循先右后左的顺序，首先检查cur的右节点是否存在，如果存在，则将其压入栈中，因为栈这种数据结构是一种后进先出的数据结构，你要先访问左节点的话，就要让左节点先出栈，那么左节点就要后入栈，让右节点先入栈，接着检查cur的左子节点，如果存在同样将其压入栈中，左子节点虽然后压入，但由于栈后进先出的机制，它会在下一个循环中先于右子节点被访问。这个循环一直进行，直至栈为空，就意味着所有的节点都已经按照先序遍历的顺序被访问并加入结果数组中了。
这里顺便给大家来讲一下广度优先搜索的算法：
广度优先搜索（BFS）
层序遍历
广度优先搜索则是一种层次遍历的方法，它从起始节点开始，先访问离起点最近的所有节点，然后逐步扩大探索范围。具体而言：
- 过程：BFS首先访问起始节点，然后访问所有与起始节点直接相连的节点，接着访问这些节点的相邻节点，以此类推，一层一层地往外探索。
- 数据结构：BFS通常使用队列来实现，因为队列的先进先出特性符合按层次遍历的需求。
- 特性：BFS保证找到的是从起点到目标节点的最短路径（在无权重或所有边权重相等的情况下）。它是完备搜索，适合解决最短路径问题，但需要更多的内存来存储待探索的节点。
那么在二叉树中层序遍历是如何实现的呢，通常使用队列来完成，我给大家举个例子：
function TreeNode(val, left, right) {
this.val = (val===undefined ? 0 : val)
this.left = (left===undefined ? null : left)
this.right = (right===undefined ? null : right)
}
function levelOrder(root) {
if (!root) return []; // 如果根节点为空，直接返回空数组
const result = []; // 存放每一层节点值的数组
const queue = [root]; // 初始化队列，将根节点放入队列中
while (queue.length > 0) {
const levelSize = queue.length; // 当前层的节点数量
const currentLevel = []; // 用于存放当前层节点的值
for (let i = 0; i < levelSize; i++) {
const node = queue.shift(); // 弹出队列的第一个节点，即当前层的节点
currentLevel.push(node.val); // 把当前节点的值加入到currentLevel中
// 将当前节点的左右子节点（如果存在）加入队列，供下一轮循环遍历
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
result.push(currentLevel); // 将当前层的所有节点值加入到结果数组中
}
return result; // 返回最终的层序遍历结果
}
// 使用示例：
const root = new TreeNode(3);
root.left = new TreeNode(9);
root.right = new TreeNode(20);
root.right.left = new TreeNode(15);
root.right.right = new TreeNode(7);
console.log(levelOrder(root)); // 输出: [[3], [9, 20], [15, 7]]
这里咱们首先定义了一个TreeNode构造函数用于创建二叉树的节点，然后定义了levelOrder函数来执行层序遍历。在遍历过程中，咱们使用队列来保存每一层的节点，并在每一轮循环中处理当前层的所有节点，同时将下一层的节点加入队列。最终，result数组将包含每层节点值的列表，形成了层序遍历的结果。
应用场景
- DFS常用于解决迷宫问题、寻找环、判断图的连通性、生成树等。
- BFS则常用于寻找两点间的最短路径、求解宽度限制问题、社交网络中的朋友推荐等。
总结
这篇文章咱们介绍了二叉树和它的所有遍历方法，包括深度优先搜索中运用递归的先序遍历、中序遍历、后序遍历还有用迭代法实现的前序遍历。以及二叉树的广度优先搜索层序遍历。希望这篇文章对屏幕前的你有所帮助，欢迎评论区留言讨论交流哈，可以点个免费的赞赞嘛，感谢感谢！
转载自:https://juejin.cn/post/7384617995873894437