数据结构树详解：分层模型与常用遍历

什么是树

一种分层数据的抽象模型
前端工作中常见的树：DOM树，级联选择，树形控件
Js 中没有树，但是可以用 Object 和 Array 构建树

常用操作

深度/广度优先遍历
先中后序遍历

几个必须分清的术语

树的题目里这些词会反复出现，混了会直接理解错题意：

根节点（root） — 没有父节点的那个节点，一棵树只有一个。
叶子节点（leaf） — 没有子节点的节点。
度（degree） — 一个节点的子节点数量。二叉树就是度不超过 2 的树。
深度（depth） — 从根到某节点的边数，根的深度是 0（有些教材算 1，做题时看题目定义）。
高度（height） — 从某节点到最远叶子的边数，叶子的高度是 0。树的高度等于根的高度。
层（level） — 深度相同的节点在同一层。

深度和高度是一对反向的概念：深度自上往下数，高度自下往上数。LeetCode 上「二叉树的最大深度」求的其实是根的高度，这个命名不一致坑过很多人。

用 JS 构建一棵树

Object 和 Array 组合就够了。前端最常见的两种形态：

通用树（子节点放数组），级联选择器、树形控件的数据就是这个结构：

const tree = {
  val: 'A',
  children: [
    {
      val: 'B',
      children: [
        { val: 'D', children: [] },
        { val: 'E', children: [] },
      ],
    },
    {
      val: 'C',
      children: [{ val: 'F', children: [] }],
    },
  ],
};

二叉树（固定 left / right），算法题里的标准形态：

function TreeNode(val, left = null, right = null) {
  this.val = val;
  this.left = left;
  this.right = right;
}

//       1
//      / \
//     2   3
//    / \
//   4   5
const root = new TreeNode(
  1,
  new TreeNode(2, new TreeNode(4), new TreeNode(5)),
  new TreeNode(3),
);

还有一种在堆和线段树里常用的数组表示法：下标 i 的节点，左孩子在 2i + 1，右孩子在 2i + 2，父节点在 Math.floor((i - 1) / 2)。省掉了指针，但只对完全二叉树省空间，稀疏的树会浪费大量空位。

深度优先遍历

深度优先就是「一条路走到底，走不通再回头」。递归实现最直观，因为函数调用栈天然就是回溯机制：

function dfs(node) {
  if (!node) return;
  console.log(node.val); // 访问当前节点
  node.children.forEach(dfs); // 再递归每个子树
}

递归的隐患是栈深度。JS 引擎的调用栈大概一万多层（各引擎不同），退化成链表的树（每个节点只有一个孩子）深度上万就会 Maximum call stack size exceeded。要处理这种情况就得手动用栈改成迭代：

function dfsIterative(root) {
  if (!root) return;
  const stack = [root];
  while (stack.length) {
    const node = stack.pop();
    console.log(node.val);
    // 逆序入栈，出栈时才是从左到右
    for (let i = node.children.length - 1; i >= 0; i--) {
      stack.push(node.children[i]);
    }
  }
}

这里逆序入栈是关键：栈是后进先出，正序压入的话最右边的孩子会先弹出来。

广度优先遍历

广度优先是「逐层扫」，用队列而不是栈：

function bfs(root) {
  if (!root) return;
  const queue = [root];
  while (queue.length) {
    const node = queue.shift();
    console.log(node.val);
    queue.push(...node.children);
  }
}

注意 Array.prototype.shift() 是 O(n) 的——它要把后面所有元素往前挪一位，所以整体会退化到 O(n²)。节点量大的时候用一个头指针代替：

function bfsFast(root) {
  if (!root) return;
  const queue = [root];
  let head = 0; // 只移动指针，不真的删元素
  while (head < queue.length) {
    const node = queue[head++];
    console.log(node.val);
    queue.push(...node.children);
  }
}

二叉树的先中后序

这三个名字里的「先中后」指的是根节点在什么时候被访问，左右子树的相对顺序永远是先左后右。所以只要记住根的位置就不会混：

// 先序：根 → 左 → 右
function preorder(node, res = []) {
  if (!node) return res;
  res.push(node.val);
  preorder(node.left, res);
  preorder(node.right, res);
  return res;
}

// 中序：左 → 根 → 右
function inorder(node, res = []) {
  if (!node) return res;
  inorder(node.left, res);
  res.push(node.val);
  inorder(node.right, res);
  return res;
}

// 后序：左 → 右 → 根
function postorder(node, res = []) {
  if (!node) return res;
  postorder(node.left, res);
  postorder(node.right, res);
  res.push(node.val);
  return res;
}

拿上面那棵示例树验证：先序 [1, 2, 4, 5, 3]，中序 [4, 2, 5, 1, 3]，后序 [4, 5, 2, 3, 1]。

这三种顺序各自的用途，比记顺序更值得记：

先序 — 先处理父节点再处理子节点。复制一棵树、序列化一棵树用它，因为重建时必须先有父节点。
中序 — 对二叉搜索树做中序遍历，结果是升序有序的。这是 BST 最重要的性质，「验证一棵树是不是 BST」「找 BST 里第 k 小的元素」都靠它。
后序 — 先处理完所有子节点再处理父节点。计算树的高度、删除整棵树、以及任何「父节点的结果依赖子节点的结果」的场景，比如统计每棵子树的节点数。

复杂度

遍历类操作的时间复杂度都是 O(n)，每个节点访问一次，跑不掉。

空间复杂度要看形态：

DFS 递归 — O(h)，h 是树高。平衡树 h ≈ log n，退化成链表时 h = n。
BFS — O(w)，w 是最宽一层的节点数。满二叉树的最后一层有约 n/2 个节点，所以最坏是 O(n)。

有意思的是这两者的最坏情况正好互补：DFS 怕深，BFS 怕宽。所以选哪种遍历有时候不是看逻辑方便，而是看树的形态——找最短路径必须 BFS（先到达的一定是最浅的），找所有路径通常 DFS（回溯天然维护当前路径）。

前端里的实际用法

树形结构在业务里最常见的场景是「后端给一维数组，前端要渲染成树」。这个转换用一次遍历建映射就够，别写嵌套循环：

function listToTree(list) {
  const map = new Map();
  const roots = [];

  // 第一遍：建 id → node 的索引
  list.forEach(item => {
    map.set(item.id, { ...item, children: [] });
  });

  // 第二遍：挂到各自的父节点下
  list.forEach(item => {
    const node = map.get(item.id);
    if (item.parentId == null) {
      roots.push(node);
    } else {
      const parent = map.get(item.parentId);
      // 父节点可能不在当前数据集里（分页、权限过滤），要兜住
      if (parent) parent.children.push(node);
      else roots.push(node);
    }
  });

  return roots;
}

时间复杂度 O(n)，比每次去数组里 find 父节点的 O(n²) 快一个量级。数据量上千时差别很明显。

反过来，从树里查找某个节点、或者收集所有选中的叶子，就是标准的 DFS：

function findNode(tree, targetId) {
  for (const node of tree) {
    if (node.id === targetId) return node;
    if (node.children?.length) {
      const found = findNode(node.children, targetId);
      if (found) return found; // 找到就立刻往上返回，不再继续搜
    }
  }
  return null;
}

这里 if (found) return found 那一行是提前剪枝，漏了会把整棵树扫完才返回，功能对但白跑。