剑指offer-树（JavaScript）：如何用JS实现二叉树的遍历
- 本文目录导读：
- 1、什么是二叉树？
- 2、深度优先遍历（DFS）
- 3、广度优先搜索（BFS）
在计算机科学中，树是一种重要的数据结构。它由节点和边组成，并且每个节点可以有多个子节点。二叉树是其中最常见的一种形式，它只允许每个节点最多有两个子节点。
在面试过程中，关于树的问题很常见。因此，在本文中我们将探讨如何使用JavaScript来实现二叉树的遍历。
什么是二叉树？
第一，让我们回顾一下什么是二叉树。一个二叉搜索树（BST）是一个具有以下特性的二叉树：
- 对于任意一个非空节点X：
- 如果左子结点不为空，则左子结点上所有值都小于X所存储的值。
- 如果右子结点不为空，则右子结点上所有值都大于X所存储的值。
这意味着如果你按照正确顺序插入元素，则可以保证搜索时具有O(log n)复杂度。
深度优先遍历（DFS）
深度优先遍历方法包括前序、中序和后续三种方式：
1. 前序遍历
前序遍历从父节点开始，先访问父节点，然后遍历左子树和右子树。以下是前序遍历的示例代码：
```
function preOrder(node) {
if (node !== null) {
console.log(node.value);
preOrder(node.left);
preOrder(node.right);
}
}
2. 中序遍历
中序遍历从最左侧的叶子节点开始，按照从小到大的顺序访问每个节点。以下是中序遍历的示例代码：
function inOrder(node) {
inOrder(node.left);
inOrder(node.right);
3. 后续遍历
后续遍历从最深处开始，先访问左子树和右子树，最后再处理父节点。以下是后续遍历的示例代码：
function postOrder(node) {
postOrder(node.left);
postOrder(node.right);
console.log(node.value)
广度优先搜索（BFS）
广度优先搜索方法也称为层次顺序方法，在同一级别上按顺序处理所有元素，并逐步向下移动到下一个级别。
这可以通过使用队列来实现。我们将root添加到队列中，并在while循环内迭代直到队列为空。
对于每个项（即当前项），我们打印值并将其非空孩子推入队列中。以下是广度优先搜索的示例代码：
function bfs(root) {
let queue = [];
queue.push(root);
while(queue.length > 0) {
let node = queue.shift();
if (node.left !== null)
queue.push(node.left);
if (node.right !== null)
queue.push(node.right);
在本文中，我们探讨了如何使用JavaScript实现二叉树遍历。深度优先遍历方法包括前序、中序和后续三种方式，而广度优先搜索则按层次顺序处理元素。这些算法对于解决各种问题都非常有用。
如果您正在准备面试或想要提高自己的编程技能，请务必学习并理解这些算法！
