JS中的二叉树遍历详解

二叉树是一种非常重要的数据结构，它是由节点组成的树形结构，其中每个节点都有不超过两个子节点，分别称为左子节点和右子节点。在JavaScript中，我们通常使用嵌套对象的方式来实现二叉树。

安装

在使用JS实现二叉树遍历之前，我们需要安装一个依赖包：binary-tree。打开终端，输入以下命令进行安装。

npm install binary-tree

安装完毕后，就可以在JS中调用这个包。

创建二叉树

在JS中，我们可以通过创建一个普通的JS对象来表示一个二叉树。下面是一个示例。

const tree = {
  value: '+',
  left: { value: 'a' },
  right: {
    value: '*',
    left: { value: 'b' },
    right: { value: 'c' }
  }
};

其中，value表示节点的值，left和right表示节点的左子节点和右子节点。在上面的示例中，我们创建了一棵二叉树，根节点为+，左子节点为a，右子节点为乘法表达式*，*的左子节点为b，右子节点为c。

前序遍历

前序遍历是二叉树遍历中的一种，它的遍历顺序是先遍历当前节点，再遍历左子节点，最后遍历右子节点。使用递归的方式实现前序遍历，如下所示。

function preOrderTraversal(node) {
  if (node) {
    console.log(node.value); // 访问当前节点
    preOrderTraversal(node.left); // 遍历左子树
    preOrderTraversal(node.right); // 遍历右子树
  }
}

在上面的代码中，我们首先判断当前节点是否存在，如果当前节点存在则输出它的值，然后递归的遍历它的左子节点和右子节点。

为了验证前序遍历的结果，我们使用上面的示例代码来测试。

preOrderTraversal(tree);

输出的结果如下所示：

+
a
*
b
c

在以上结果中，+为根节点，a为其左子节点，*为其右子节点，*的左子节点为b，右子节点为c。

中序遍历

中序遍历是二叉树遍历中的一种，它的遍历顺序是先遍历左子节点，再遍历当前节点，最后遍历右子节点。使用递归的方式实现中序遍历，如下所示。

function inOrderTraversal(node) {
  if (node) {
    inOrderTraversal(node.left); // 遍历左子树
    console.log(node.value); // 访问当前节点
    inOrderTraversal(node.right); // 遍历右子树
  }
}

在上面的代码中，我们首先判断当前节点是否存在，如果当前节点存在则递归的遍历它的左子节点和右子节点，然后输出它的值。

为了验证中序遍历的结果，我们使用上面的示例代码来测试。

inOrderTraversal(tree);

输出的结果如下所示：

a
+
b
*
c

在以上结果中，a为第一个被输出的节点，因为它是左节点；+为第二个被输出的节点，因为它在中间；b为第三个被输出的节点，因为它是*的左子节点；*为第四个被输出的节点，因为它在中间；c为最后一个被输出的节点，因为它是*的右子节点。

后序遍历

后序遍历是二叉树遍历中的一种，它的遍历顺序是先遍历左子节点，再遍历右子节点，最后遍历当前节点。使用递归的方式实现后序遍历，如下所示。

function postOrderTraversal(node) {
  if (node) {
    postOrderTraversal(node.left); // 遍历左子树
    postOrderTraversal(node.right); // 遍历右子树
    console.log(node.value); // 访问当前节点
  }
}

在上面的代码中，我们首先判断当前节点是否存在，如果当前节点存在则递归的遍历它的左子节点和右子节点，然后输出它的值。

为了验证后序遍历的结果，我们使用上面的示例代码来测试。

postOrderTraversal(tree);

输出的结果如下所示：

a
b
c
*
+

在以上结果中，a为第一个被输出的节点；b和c依次为接下来被输出的节点，因为它们都是*的子节点；*为被输出的第四个节点；最后被输出的是根节点+。

结语

以上就是JS中二叉树遍历的详解。熟练掌握遍历方法，能够灵活应用数据结构是JS程序员必修的基础课程。