树组件怎样设计？上万个节点时虚拟树怎样实现？

简答

比如一个组织架构树，公司下面有部门，部门下面有小组和员工。数据是嵌套的，但页面上显示出来其实是一行一行的列表，只是每行缩进不同。所以树组件的核心做法是：按当前哪些节点展开了，把嵌套数据拍平成一维数组，每一项记下自己的层级，渲染时按层级缩进。

拍平以后，树就变成了普通列表。节点上万时直接对这个数组做虚拟列表，只渲染可视区域里的几十行；展开或收起一个节点，只是重新算一遍数组。子节点很多或者要从接口取时，可以在第一次展开时再懒加载。

带勾选的树还要做联动。勾选一个节点，它的子孙要全部跟着变；父节点则要根据子节点重新算：全部选中就是选中，全部没选就是未选，部分选中就是半选。

要注意，半选只是显示状态，原生复选框的 indeterminate 只能用 JavaScript 设置，也不影响表单提交。无障碍方面要按 WAI-ARIA 的 tree 模式提供方向键操作；虚拟化后 DOM 里节点不全，还要给每个节点标上 aria-level、aria-setsize 和 aria-posinset。

为什么要把树拍平

嵌套数据最直接的渲染方式是递归组件：每个节点渲染自己，再渲染一个子节点列表。节点少时这样没问题，可是要做虚拟滚动就很难，因为虚拟列表需要知道“第 1000 行是谁”，递归结构回答不了这个问题。

所以换个思路：用户看到的始终是一行一行的列表。只要从根开始深度优先遍历，遇到展开的节点才继续进入它的子节点，把经过的节点依次放进数组，就得到了当前可见的所有行。每一项带上 level，渲染时用 padding-left: level * 缩进宽度 就能显示出层级。

下面的例子实现了拍平和勾选联动，看两点：拍平只收集展开路径上的节点；勾选一个子节点后，父节点会变成半选。

const tree = [
  {
    id: 'a',
    label: '研发部',
    children: [
      { id: 'a1', label: '前端组' },
      { id: 'a2', label: '后端组' },
    ],
  },
  { id: 'b', label: '市场部', children: [{ id: 'b1', label: '品牌组' }] },
];

// 建一次父节点索引，向上联动时不用每次重新遍历整棵树。
const parentOf = new Map();
const nodeOf = new Map();
function index(nodes, parent) {
  for (const node of nodes) {
    nodeOf.set(node.id, node);
    parentOf.set(node.id, parent);
    if (node.children) index(node.children, node);
  }
}
index(tree, null);

function flatten(nodes, expanded, level = 0, rows = []) {
  for (const node of nodes) {
    rows.push({ id: node.id, label: node.label, level });
    if (node.children && expanded.has(node.id)) {
      flatten(node.children, expanded, level + 1, rows);
    }
  }
  return rows;
}

const checked = new Set();
function setChecked(node, value) {
  // 向下：子孙全部设成同一状态。
  if (value) checked.add(node.id);
  else checked.delete(node.id);
  for (const child of node.children ?? []) setChecked(child, value);
  // 向上：按子节点重新计算父节点。
  for (let p = parentOf.get(node.id); p; p = parentOf.get(p.id)) {
    if (p.children.every((c) => checked.has(c.id))) checked.add(p.id);
    else checked.delete(p.id);
  }
}

function stateOf(node) {
  if (checked.has(node.id)) return 'checked';
  const leaves = [];
  (function collect(n) {
    if (!n.children) leaves.push(n);
    else n.children.forEach(collect);
  })(node);
  return leaves.some((leaf) => checked.has(leaf.id)) ? 'mixed' : 'unchecked';
}

const rows = flatten(tree, new Set(['a']));
console.log(rows.map((r) => '  '.repeat(r.level) + r.label).join('|')); // 研发部|  前端组|  后端组|市场部

setChecked(nodeOf.get('a1'), true);
console.log(stateOf(nodeOf.get('a'))); // mixed
setChecked(nodeOf.get('a2'), true);
console.log(stateOf(nodeOf.get('a'))); // checked
setChecked(nodeOf.get('a'), false);
console.log(checked.size); // 0

只展开了“研发部”，所以“品牌组”没有出现在结果里。展开或收起一个节点时，只需要改 expanded 这个集合，再调用一次 flatten，拿到的新数组直接交给列表渲染。

虚拟树怎样实现

拍平以后的数组就是虚拟列表的数据源。行高固定时，根据 scrollTop 算出起止下标，只渲染这一段，外层用一个总高度等于“行数 × 行高”的容器撑出滚动条。这部分和普通虚拟列表完全一样，详见《定高虚拟列表怎样手写？怎样根据 scrollTop 算出要渲染哪几行？》；如果节点里有多行文字导致高度不固定，见《动态高度的虚拟列表怎样处理测量、滚动锚点和焦点？》。

节点有几十万时，每次展开都从根重新遍历会变慢。可以只处理变化的部分：展开一个节点，就把它的可见子孙插到数组中它的后面；收起时删掉它后面所有 level 比它大的连续行。

子节点怎样懒加载

数据量大或者要从接口取时，节点上只放一个“有子节点”的标记，用户第一次展开时再请求。这时要处理几个状态：请求中显示加载提示，失败了允许重试，已经加载过的不要重复请求。

懒加载还会影响勾选联动。父节点被勾选时子节点还没加载回来，加载完成后要让新子节点继承父节点的选中状态。同理，没加载的子树无法算半选，所以“选中了哪些节点”通常要同时保存显式勾选的父节点，而不是只存叶子。

勾选联动为什么分向下和向上

勾选一个节点，用户的意思是“这一整支都要”，所以要向下把子孙全部设成同一状态。父节点的状态则不是用户直接点的，而是由子节点推出来的，所以要沿着父链向上逐层重算。例子里先建了一个 parentOf 索引，向上找父节点就不用每次遍历整棵树。

半选只是一种显示。MDN 说明，原生复选框的 indeterminate 只能通过 JavaScript 的 input.indeterminate = true 设置，没有对应的 HTML 属性；它只改变外观，表单提交时看的仍然是 checked。所以在数据里，半选状态应该每次由子节点算出来，不要把它当成一个独立存储的值。

如果不用原生复选框，而是自己画一个，就要用 role="checkbox" 加 aria-checked="mixed" 告诉辅助技术这是半选。MDN 写明，mixed 值只被 checkbox 和 menuitemcheckbox 这类三态角色支持。

无障碍要做什么

WAI-ARIA 的 Tree View 模式规定了角色和键盘行为。整个容器是 tree，每个节点是 treeitem，父节点的子节点放在 group 里；父节点用 aria-expanded 标出展开或收起，叶子节点不要加这个属性，否则会被当成父节点。

键盘上，上下方向键在可见节点间移动焦点；右方向键展开收起的节点，已展开时移到第一个子节点；左方向键收起展开的节点，否则回到父节点；Home 和 End 跳到第一个和最后一个节点。

虚拟化后，DOM 里只有可视区域的节点，屏幕阅读器没法自己数出层级和位置。APG 要求这种情况下给每个节点都标上 aria-level、aria-setsize 和 aria-posinset。拍平时顺手把层级、兄弟总数和自己的序号算出来放在每一行上就行。

常见追问

父节点勾选后，提交给后端的应该是哪些 ID？

看业务。权限树之类通常只要叶子节点；按部门圈人时，提交父节点更省也更能表达“以后新增的成员也算”。组件可以提供一个选项决定返回全部、只返回叶子，还是在整支选中时只返回最上层的父节点。

树组件的搜索怎样做？

在原始数据上找出匹配的节点，再把它们的所有祖先加入展开集合，最后照常拍平。不匹配且没有匹配子孙的节点直接过滤掉，这样用户能看到每个结果所在的路径。