js递归遍历树结构(JavaScript实现树形结构递归遍历)

什么是树结构

树结构是一种非线性数据结构，它由若干个节点（节点可以是对象、字符或者其他类型）构成。树结构中每个节点都有一个父节点，除了根节点没有父节点，同时每个节点还可以有零个或多个子节点。

树结构通常用于表示具有层次关系的数据，例如公司的组织架构图、文件系统等。

树结构的遍历方式

树结构的遍历指的是将树结构中的所有节点按照一定规则依次访问一遍的操作。

树结构的遍历方式可以分为以下三种：

前序遍历

前序遍历是先访问根节点，再依次遍历左子树和右子树。具体实现过程如下：

function preOrder(node) {

  if(node !== null) {
    console.log(node.value);
    preOrder(node.left);
    preOrder(node.right);
  }
}

上述代码中，preOrder为前序遍历函数，参数为node，表示要遍历的树的根节点。如果当前节点不为null时，将当前节点打印出来，并依次递归遍历其左右子树。

中序遍历

中序遍历是先遍历左子树，再访问根节点，最后遍历右子树。具体实现过程如下：

function inOrder(node) {

  if(node !== null) {
    inOrder(node.left);
    console.log(node.value);
    inOrder(node.right);
  }
}

上述代码中，inOrder为中序遍历函数，参数为node，表示要遍历的树的根节点。如果当前节点不为null时，依次递归遍历其左子树，将当前节点打印出来，最后再递归遍历右子树。

后序遍历

后序遍历是先遍历左子树，再遍历右子树，最后访问根节点。具体实现过程如下：

function postOrder(node) {

  if(node !== null) {
    postOrder(node.left);
    postOrder(node.right);
    console.log(node.value);
  }
}

上述代码中，postOrder为后序遍历函数，参数为node，表示要遍历的树的根节点。如果当前节点不为null时，依次递归遍历其左右子树，最后将当前节点打印出来。

js递归遍历树结构

在JavaScript中，我们可以使用递归的方式遍历树结构。首先我们需要定义一个树的数据结构，可以使用对象实现：

const tree = {

  value: 1,
  left: {
    value: 2,
    left: {
      value: 4,
      left: null,
      right: null
    },
    right: null
  },
  right: {
    value: 3,
    left: {
      value: 5,
      left: null,
      right: null
    },
    right: {
      value: 6,
      left: null,
      right: null
    }
  }
};

上述代码中，我们定义了一个树结构，根节点的值为1，左子树包含了值为2的节点和值为4的叶子节点，右子树分别包含了值为3、5、6的节点。

接下来，我们可以分别使用前序、中序和后序遍历函数来遍历这棵树：

function preOrder(node) {

  if(node !== null) {
    console.log(node.value);
    preOrder(node.left);
    preOrder(node.right);
  }
}
function inOrder(node) {
  if(node !== null) {
    inOrder(node.left);
    console.log(node.value);
    inOrder(node.right);
  }
}
function postOrder(node) {
  if(node !== null) {
    postOrder(node.left);
    postOrder(node.right);
    console.log(node.value);
  }
}
preOrder(tree); // 1 2 4 3 5 6
inOrder(tree); // 4 2 1 5 3 6
postOrder(tree); // 4 2 5 6 3 1

上述代码中，我们调用了前序、中序和后序遍历函数，传入根节点tree作为参数，程序会自动遍历整棵树。

总结

使用递归的方式遍历树结构可以简化代码量，更容易理解和维护。通过前序、中序和后序遍历函数，我们可以按照不同的规则遍历树结构，这对于处理树形结构的应用十分重要。在实际开发中，我们可能会遇到更复杂的树形结构，但是使用递归的方式遍历的方法是普适的，在代码中扩展一下即可。