js 树遍历

js 树遍历

在前端开发中，经常会遇到需要对树形数据进行遍历的情况，比如渲染菜单、展示目录结构等。JavaScript 提供了多种方式来遍历树形结构，包括先序遍历、中序遍历、后序遍历以及广度优先搜索等方法。

先序遍历

先序遍历是一种深度优先搜索的算法，它先访问根节点，然后依次递归遍历左子树和右子树。在 JavaScript 中，可以通过递归或者使用栈来实现先序遍历。

以下是使用递归实现先序遍历的示例代码：

class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

function preOrderTraversal(node) {
  if (node) {
    console.log(node.value);
    preOrderTraversal(node.left);
    preOrderTraversal(node.right);
  }
}

// 构建一颗二叉树
const root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);

// 先序遍历
preOrderTraversal(root);

运行结果为：

1
2
4
5
3

中序遍历

中序遍历是先遍历左子树，再访问根节点，最后遍历右子树的一种算法。同样可以使用递归或者栈来实现中序遍历。

以下是使用递归实现中序遍历的示例代码：

function inOrderTraversal(node) {
  if (node) {
    inOrderTraversal(node.left);
    console.log(node.value);
    inOrderTraversal(node.right);
  }
}

// 中序遍历
inOrderTraversal(root);

运行结果为：

4
2
5
1
3

后序遍历

后序遍历是先遍历左子树，再遍历右子树，最后访问根节点的一种算法。同样可以使用递归或者栈来实现后序遍历。

以下是使用递归实现后序遍历的示例代码：

function postOrderTraversal(node) {
  if (node) {
    postOrderTraversal(node.left);
    postOrderTraversal(node.right);
    console.log(node.value);
  }
}

// 后序遍历
postOrderTraversal(root);

运行结果为：

4
5
2
3
1

广度优先搜索

广度优先搜索是从根节点开始，逐层遍历树的节点。可以使用队列来实现广度优先搜索。

以下是使用队列实现广度优先搜索的示例代码：

function breadthFirstSearch(node) {
  const queue = [];
  queue.push(node);

  while (queue.length > 0) {
    const current = queue.shift();
    console.log(current.value);

    if (current.left) {
      queue.push(current.left);
    }

    if (current.right) {
      queue.push(current.right);
    }
  }
}

// 广度优先搜索
breadthFirstSearch(root);

运行结果为：

1
2
3
4
5

通过以上几种方法，可以方便地对树形结构进行遍历操作。在实际开发中，根据具体的需求选择合适的遍历方式能够更快、更高效地处理树形数据。