二叉树遍历

二叉树构造

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class TreeNode {
    constructor(val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

// 示例构造一棵简单的二叉树
//       1
//      /  \
//     2    3
//    / \  / \
//   4   5 6  7

const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
root.right.left = new TreeNode(6);
root.right.right = new TreeNode(7);

深度优先遍历，前序遍历（Pre-order）：根 → 左 → 右

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function preorderRecursive(node) {
  if (!node) return;
  console.log('深度优先遍历，根 -> 左 -> 右：', node.val);
  preorderRecursive(node.left);
  preorderRecursive(node.right);
}
preorderRecursive(root);

/*
深度优先遍历，根 -> 左 -> 右： 1
深度优先遍历，根 -> 左 -> 右： 2
深度优先遍历，根 -> 左 -> 右： 4
深度优先遍历，根 -> 左 -> 右： 5
深度优先遍历，根 -> 左 -> 右： 3
深度优先遍历，根 -> 左 -> 右： 6
深度优先遍历，根 -> 左 -> 右： 7
*/

深度优先遍历，中序遍历（In-order）：左 → 根 → 右

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function inorderRecursive(node) {
  if (!node) return;
  inorderRecursive(node.left);
  console.log('深度优先遍历，左 -> 根 -> 右：',node.val);
  inorderRecursive(node.right);
}
inorderRecursive(root);

/*
深度优先遍历，左 -> 根 -> 右： 4
深度优先遍历，左 -> 根 -> 右： 2
深度优先遍历，左 -> 根 -> 右： 5
深度优先遍历，左 -> 根 -> 右： 1
深度优先遍历，左 -> 根 -> 右： 6
深度优先遍历，左 -> 根 -> 右： 3
深度优先遍历，左 -> 根 -> 右： 7
*/

深度优先遍历，后序遍历（Post-order）：左 → 右 → 根

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function postorderRecursive(node) {
  if (!node) return;
  postorderRecursive(node.left);
  postorderRecursive(node.right);
  console.log('深度优先遍历，左 → 右 → 根：', node.val);
}
postorderRecursive(root);

/*
深度优先遍历，左 → 右 → 根： 4
深度优先遍历，左 → 右 → 根： 5
深度优先遍历，左 → 右 → 根： 2
深度优先遍历，左 → 右 → 根： 6
深度优先遍历，左 → 右 → 根： 7
深度优先遍历，左 → 右 → 根： 3
深度优先遍历，左 → 右 → 根： 1
*/

广度优先遍历，层序遍历（Level-order）：一层一层从左到右

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function levelOrderTraversal(node) {
  if (!node) return;
  const queue = [node];
  while (queue.length) {
    const current = queue.shift();
    console.log('广度优先遍历, 层序遍历', current.val);
    if (current.left) queue.push(current.left);
    if (current.right) queue.push(current.right);
  }
}
levelOrderTraversal(root);

/*
广度优先遍历, 层序遍历 1
广度优先遍历, 层序遍历 2
广度优先遍历, 层序遍历 3
广度优先遍历, 层序遍历 4
广度优先遍历, 层序遍历 5
广度优先遍历, 层序遍历 6
广度优先遍历, 层序遍历 7
*/

二叉树应用

前序遍历 DOM

1
2
3
4
5
6
7
8
function traverseDOM(node) {
  if (!node) return;
  console.log(node.tagName); // visit root
  for (const child of node.children) {
    traverseDOM(child); // left -> right
  }
}
traverseDOM(document.body);

虚拟 DOM diff

使用后序遍历（自底向上）进行比较，便于复用

可视化组件（树结构 UI）

文件夹结构、组织架构图、流程图等

1
2
3
4
5
6
7
8
9
10
11
12
13
// 简单的 Tree 渲染逻辑
function renderTree(node) {
  if (!node) return '';
  return `
    <div class="tree-node">
      ${node.name}
      <div class="children">
        ${renderTree(node.left)}
        ${renderTree(node.right)}
      </div>
    </div>
  `;
}

前端路由或菜单生成

从嵌套路由或后台返回的菜单结构，生成平面结构或 DOM 元素，也常用树遍历实现。

1
2
3
4
5
6
7
8
9
10
11
12
function flatRoutes(tree) {
  const result = [];
  function dfs(node, path = '') {
    const fullPath = `${path}/${node.path}`;
    result.push(fullPath);
    if (node.children) {
      for (const child of node.children) dfs(child, fullPath);
    }
  }
  dfs(tree);
  return result;
}