前言

最近遇到了一个需求，要将算法的标签品类数据以树形的形式回显到后台管理页面上。通过和后端的沟通，决定了通过 parentCode 和 categoryCode 来让前端组成树形结构。通过接口获取的数据是这样的：

1

其中当节点为 root 节点时，parentCode 为空字符串。知道数据长啥样，我们就可以构建着手构建树了。

格式化数据

树形结构

首先我们要先确定树中的 node 类型应该是长怎么样的，明显我们只需要将数据关联起来，而原数据我们希望原封不动保留，所以我们可以用 ts 来定义一下数据结构

1
2
3
export type Tree<T> = T & {
  children?: Tree<T>[];
};

知道数据结构长啥样就可以着手写一下函数了。

编写函数

在 js 中对象中，变量存储的是对象的引用（地址），我们利用这个特性，便可以通过一次遍历来构建出一颗树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
// tree.ts

type NodeMap<T> = Map<T[keyof T], Tree<T>>;

// 新建一个空node
const createEmptyNode = <T>() => {
  return {
    children: [],
  } as Tree<T>;
};

// 获取node
const getNode = <T>(map: NodeMap<T>, id: T[keyof T]): [Tree<T>, boolean] => {
  let node = map.get(id);
  const isExist = !!node;
  if (!node) {
    node = createEmptyNode<T>();
  }
  return [node, isExist];
};

// 定义一个将列表转换为树形结构的函数
export const listToTreeById = <T>(
  arr: T[],
  options: {
    parentIdKey: keyof T; // 父节点的键名
    idKey: keyof T; // 节点的键名
    rootId?: string; // 根节点的ID
  }
) => {
  // 从选项对象中解构出各个属性
  const { parentIdKey, idKey, rootId = '', sortKey, handleRootTree } = options;

  // 创建一个新的Map对象
  const map: NodeMap<T> = new Map();

  // 遍历输入的列表
  arr.forEach((item) => {
    // 获取当前元素的父节点ID和自身ID
    const parentId = item[parentIdKey];
    const id = item[idKey];

    // 获取或创建当前元素的节点
    const [child, isChildExist] = getNode(map, id);
    // 将当前元素的属性复制到节点上
    Object.assign(child, item);
    // 如果节点不存在，则将其添加到Map中
    if (!isChildExist) map.set(id, child);

    // 获取或创建父节点
    const [parent, isParentExist] = getNode(map, parentId);
    // 将当前节点添加到父节点的子节点列表中
    parent.children?.push(child);
    // 如果父节点不存在，则将其添加到Map中
    if (!isParentExist) map.set(parentId, parent);
  });

  // 获取root节点下的node
  const tree: Tree<T>[] = map.get(rootId as any)?.children || [];

  // 返回树形结构，如果树形结构为空，则返回空数组
  return tree || [];
};

注意一下Object.assign(child, item);这个操作，因为后端返回的数组不一定是有序的，也就是有可能先遍历到子节点而再遍历父节点，当遇到这种情况，父节点会提前先创建但没有数据，所以当遍历到父节点时，要通过Object.assign来浅拷贝一下。

自定义返回

有时候也会根据某个条件选取树，可以加一个传入函数来让用户灵活地使用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// tree.ts
export const listToTreeById = <T>(
  arr: T[],
  options: {
    parentIdKey: keyof T; // 父节点的键名
    idKey: keyof T; // 节点的键名
    rootId?: string; // 根节点的ID
+   handleRootTree?: (map: NodeMap<T>) => Tree<T>[];
  }
) => {

	...
	let tree: Tree<T>[] = [];
  if (Object.hasOwn(options, 'rootId')) {
    tree = map.get(rootId as any)?.children || [];
  } else if (handleRootTree) {
    tree = handleRootTree(map);
  }

  return tree || [];
}

排序

对于叶子结点来说，往往也是需要排序的，我们通过 sortkey 将已经创建好的树通过 bfs 来进行排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// tree.ts
const sort = <T>(a: Tree<T>, b: Tree<T>, sortKey: keyof T) => Number(a[sortKey] || '0') - Number(b[sortKey] || '0');

const treeSort = <T>(tree: Tree<T>[], sortKey: keyof T) => {
  const nodeList = [...tree].sort((a, b) => sort(a, b, sortKey));
  let i = 0;
  while (i < nodeList.length) {
    const node = nodeList[i];
    if (node.children) {
      node.children.sort((a, b) => sort(a, b, sortKey));
      nodeList.push(...node.children);
    }
    i += 1;
  }
};

export const listToTreeById = <T>(
  arr: T[],
  options: {
    parentIdKey: keyof T;
    idKey: keyof T;
    handleRootTree?: (map: NodeMap<T>) => Tree<T>[];
    rootId?: string;
    sortKey?: keyof T;
  }
) => {
	...
	let tree: Tree<T>[] = [];
  if (Object.hasOwn(options, 'rootId')) {
    tree = map.get(rootId as any)?.children || [];
  } else if (handleRootTree) {
    tree = handleRootTree(map);
  }
  if (sortKey) {
    treeSort(tree, sortKey);
  }

	return tree || [];
}

使用

在 vue 文件中直接使用

1
2
3
4
5
6
7
8
9
const treeList = shallowRef<TreeNode[]>([]);
const handleGetCategoryList = async () => {
  const { data } = await baseCategoryList();
  treeList.value = listToTreeById(
    data,
    { parentIdKey: 'parentCode', idKey: 'categoryCode', rootId: '' }
  );
  console.log(treeList.value);
};

2

组件编写

格式化成我们想要的数据后，接下来就是编写树形组件了。下面只会说一些重点的部分。

递归 or 平铺

对于展示树形，很多人第一个思路是递归组件，达到展示树形的结果。一开始我也是这么想的，直到我看了一下 elment ui 中的 tree v2 源码后才发现，其实可以将树形数据当成一个平铺 list 去处理，这样的好处有四个：

  • 减少了递归带来的复杂性和心智负担
  • 没有递归带来的栈溢出风险
  • 调试会比递归容易些
  • 能够使用虚拟列表来优化 tree

数据监听

在响应式编程中，对于数据 proxy，一般会使用ref来达成这样的效果，但是对于树形数据来说，全数据收集依赖会给性能带来影响，所以我们应该使用shallowRef来创建 proxy。

对于监听节点展开收起的重新渲染，我们可以维护一个 expandedKeySet 来达成目的。

1
const expandedKeySet = ref<Set<TreeKey>>(new Set(props.defaultExpandedKeys));

proxy 一个 Set 要比 proxy 整个 tree 的代价还要小得多。下面是具体实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// type.ts
export type TreeKey = string | number;

export type TreeNodeData = Record<string, any>;

export interface TreeNode {
  key: TreeKey;
  level: number;
  parent?: TreeNode;
  children?: TreeNode[];
  data: TreeNodeData;
  disabled?: boolean;
  label?: string;
  isLeaf?: boolean;
}

export interface Tree {
  treeNodeMap: Map<TreeKey, TreeNode>;
  levelTreeNodeMap: Map<number, TreeNode[]>;
  treeNodes: TreeNode[];
  maxLevel: number;
}

export interface TreeOptionProps {
  children?: string;
  label?: string;
  value?: string;
  disabled?: string;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// use-tree
const expandedKeySet = ref<Set<TreeKey>>(new Set(props.defaultExpandedKeys));

const flattenTree = computed(() => {
	const expandedKeys = expandedKeySet.value;

	const flattenNodes: TreeNode[] = [];
	const nodes = (tree.value && tree.value.treeNodes) || [];

	function traverse() {
	  const stack: TreeNode[] = [];
	  for (let i = nodes.length - 1; i >= 0; --i) {
	    stack.push(nodes[i]);
	  }
	  while (stack.length) {
	    const node = stack.pop();

	    if (node) {
	      flattenNodes.push(node);
	      if (expandedKeys.has(node.key)) {
	        const { children } = node;
	        if (children) {
	          const { length } = children;
	          for (let i = length - 1; i >= 0; --i) {
	            stack.push(children[i]);
	          }
	        }
	      }
	    }
	  }
	}
	traverse();
	return flattenNodes;
});

虚拟列表

直接使用@vueuse/core 的 useVirtualList 就可以了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
// tree.vue
<script lang="ts" setup>
import { useVirtualList } from '@vueuse/core';
import { treeProps } from './props';
import { useTree } from './use-tree';
import { treeEmits } from './emit';

const props = defineProps(treeProps);
const emit = defineEmits(treeEmits);

const { flattenTree, toggleExpand } = useTree(props, emit);

const { list, containerProps, wrapperProps } = useVirtualList(flattenTree, {
  itemHeight: 32,
});

</script>

<template>
  <div
    class="overflow-auto"
    v-bind="containerProps"
    :style="`height: ${height}px`"
  >
    <div v-bind="wrapperProps">
      <div
        class="tw-cursor-pointer"
        v-for="item in list"
        :key="item.data.key"
        :style="`height: ${itemHeight}px;margin-left: ${(item.data.level - 1) * props.indent}px;`"
        @click="toggleExpand(item.data)"
      >
        <slot
          :node="item.data"
          :rawData="item.data.data"
        />
      </div>
    </div>
  </div>
</template>

完整代码可以看这里。

性能表现

3

基本维持在 16.7ms 左右，也没用出现卡顿的情况。那么就可以愉快下班啦～

结语

学习源码的过程收获良多，最大的启发是对比较大的数据进行响应式渲染时，不妨想想能不能借响应一些相对简单的数据结构来达成，这样能减少响应时的性能问题。还有就是递归组件的情况，下次遇到时，是不是可以将它从平铺的角度去考虑，考虑对于 ui 层面上，父与子的关联性是什么，从而转换为相对简单的数据结构去渲染。

参考