手把手教你实现 Tree 组件搜索过滤功能，干货满满！

本文源于 Vue DevUI 开源组件库实践。

1 Tree 组件搜索过滤功能简介

树节点的搜索功能主要是为了方便用户能够快速查找到自己需要的节点。过滤功能不仅要满足搜索的特性，同时还需要隐藏掉与匹配节点同层级的其它未能匹配的节点。

搜索功能主要包括以下功能：

与搜索过滤字段匹配的节点需要进行标识，和普通节点进行区分
子节点匹配时，其所有父节点需要展开，方便用户查看层级关系
对于大数据量，采用虚拟滚动时，搜索过滤完成后滚动条需滚动至第一个匹配节点的位置

搜索会将匹配到的节点高亮：

过滤除了将匹配到的节点高亮之外，还会将不匹配的节点筛除掉：

2 组件交互逻辑分析

2.1 对于匹配节点的标识如何呈现？

通过将节点与搜索字段相匹配的 label 部分文字进行高亮加粗的方式进行标记。易于用户一眼就能够找到搜索到的节点。

2.2 用户如何调用 `tree` 组件的搜索过滤功能？

通过添加searchTree方法，用户通过ref的方式进行调用。并通过option参数配置区分搜索、过滤。

2.3 对于匹配的节点其父节点及兄弟节点如何获取及处理？

对于节点的获取及处理是搜索过滤功能的核心。尤其在大数据量的情况下，带来的性能消耗如何优化，将在实现原理中详情阐述。

3 实现原理和步骤

3.1 第一步：需要熟悉 `tree` 组件整个代码及逻辑组织方式

tree组件的文件结构：

tree
├── index.ts
├── src
|  ├── components
|  |  ├── tree-node.tsx
|  |  ├── ...
|  ├── composables
|  |  ├── use-check.ts
|  |  ├── use-core.ts
|  |  ├── use-disable.ts
|  |  ├── use-merge-nodes.ts
|  |  ├── use-operate.ts
|  |  ├── use-select.ts
|  |  ├── use-toggle.ts
|  |  ├── ...
|  ├── tree.scss
|  ├── tree.tsx
└── __tests__
   └── tree.spec.ts

可以看出，vue3.0中 composition-api 带来的便利。逻辑层之间的分离，方便代码组织及后续问题的定位。能够让开发者只专心于自己的特性，非常有利于后期维护。

添加文件use-search-filter.ts, 文件中定义searchTree方法。

import { Ref, ref } from 'vue';
import { trim } from 'lodash';
import { IInnerTreeNode, IUseCore, IUseSearchFilter, SearchFilterOption } from './use-tree-types';

export default function () {
  return function useSearchFilter(data: Ref, core: IUseCore): IUseSearchFilter {
    const searchTree = (target: string, option: SearchFilterOption): void => {
      // 搜索主逻辑
    };

    return {
      virtualListRef,
      searchTree,
    };
  }
}

SearchFilterOption的接口定义，matchKey 与 pattern的配置增添了搜索的匹配方式多样性。

export interface SearchFilterOption {
  isFilter: boolean; // 是否是过滤节点
  matchKey?: string; // node节点中匹配搜索过滤的字段名
  pattern?: RegExp; // 搜索过滤时匹配的正则表达式
}

在tree.tsx主文件中添加文件use-search-fliter.ts的引用, 并将searchTree方法暴露给第三方调用者。

import useSearchFilter from './composables/use-search-filter';

  setup(props: TreeProps, context: SetupContext) {
    const userPlugins = [useSelect(), useOperate(), useMergeNodes(), useSearchFilter()];
    const treeFactory = useTree(data.value, userPlugins, context);
    expose({
      treeFactory,
    });
  }

3.2 第二步：需要熟悉 `tree` 组件整个nodes数据结构是怎样的。nodes数据结构直接决定如何访问及处理匹配节点的父节点及兄弟节点

在use-core.ts文件中可以看出，整个数据结构采用的是扁平结构，并不是传统的树结构，所有的节点包含在一个一维的数组中。

const treeData = ref(generateInnerTree(tree));

// 内部数据结构使用扁平结构
export interface IInnerTreeNode extends ITreeNode {
  level: number;
  idType?: 'random';
  parentId?: string;
  isLeaf?: boolean;
  parentChildNodeCount?: number;
  currentIndex?: number;
  loading?: boolean; // 节点是否显示加载中
  childNodeCount?: number; // 该节点的子节点的数量

  // 搜索过滤
  isMatched?: boolean; // 搜索过滤时是否匹配该节点
  childrenMatched?: boolean; // 搜索过滤时是否有子节点存在匹配
  isHide?: boolean; // 过滤后是否不显示该节点
  matchedText?: string; // 节点匹配的文字（需要高亮显示）
}

3.3 第三步：处理匹配节点及其父节点的展开属性

节点中添加以下属性，用于标识匹配关系

  isMatched?: boolean; // 搜索过滤时是否匹配该节点
  childrenMatched?: boolean; // 搜索过滤时是否有子节点存在匹配
  matchedText?: string; // 节点匹配的文字（需要高亮显示）

通过 dealMatchedData 方法来处理所有节点关于搜索属性的设置。

它主要做了以下事情：

将用户传入的搜索字段进行大小写转换
循环所有节点，先处理自身节点是否与搜索字段匹配，匹配就设置 selfMatched = true。首先判断用户是否通过自定义字段进行搜索 ( matchKey 参数)，如果有，设置匹配属性为node中自定义属性，否则为默认 label 属性；然后判断是否进行正则匹配 ( pattern 参数)，如果有，就进行正则匹配，否则为默认的忽略大小写的模糊匹配。
如果自身节点匹配时, 设置节点 matchedText 属性值，用于高亮标识。
判断自身节点有无 parentId，无此属性值时，为根节点，无须处理父节点。有此属性时，需要进行内层循环处理父节点的搜索属性。利用set保存节点的 parentId , 依次向前查找，找到parent节点，判读是否该parent节点被处理过，如果没有，设置父节点的 childrenMatched 和 expanded 属性为true，再将parent节点的 parentId 属性加入set中，while循环重复这个操作，直到遇到第一个已经处理过的父节点或者直到根节点停止循环。
整个双层循环将所有节点处理完毕。

dealMatchedData核心代码如下：

const dealMatchedData = (target: string, matchKey: string | undefined, pattern: RegExp | undefined) => {
    const trimmedTarget = trim(target).toLocaleLowerCase();
    for (let i = 0; i < data.value.length; i++) {
        const key = matchKey ? data.value[i][matchKey] : data.value[i].label;
        const selfMatched = pattern ? pattern.test(key) : key.toLocaleLowerCase().includes(trimmedTarget);
        data.value[i].isMatched = selfMatched;
        // 需要向前找父节点，处理父节点的childrenMatched、expand参数(子节点匹配到时，父节点需要展开)
        if (selfMatched) {
            data.value[i].matchedText = matchKey ? data.value[i].label : trimmedTarget;
            if (!data.value[i].parentId) {
                // 没有parentId表示时根节点，不需要再向前遍历
                continue;
            }
            let L = i - 1;
            const set = new Set();
            set.add(data.value[i].parentId);
            // 没有parentId时，表示此节点的纵向parent已访问完毕
            // 没有父节点被处理过，表示时第一次向上处理当前纵向父节点
            while (L >= 0 && data.value[L].parentId && !hasDealParentNode(L, i, set)) {
                if (set.has(data.value[L].id)) {
                    data.value[L].childrenMatched = true;
                    data.value[L].expanded = true;
                    set.add(data.value[L].parentId);
                }
                L--;
            }
            // 循环结束时需要额外处理根节点一层
            if (L >= 0 && !data.value[L].parentId && set.has(data.value[L].id)) {
                data.value[L].childrenMatched = true;
                data.value[L].expanded = true;
            }
        }
    }
};

const hasDealParentNode = (pre: number, cur: number, parentIdSet: Set) => {
    // 当访问到同一层级前已经有匹配时前一个已经处理过父节点了，不需要继续访问
    // 当访问到第一父节点的childrenMatched为true的时，不再需要向上寻找，防止重复访问
    return (
    (data.value[pre].parentId === data.value[cur].parentId && data.value[pre].isMatched) ||
    (parentIdSet.has(data.value[pre].id) && data.value[pre].childrenMatched)
    );
};

3.4 第四步：如果是过滤功能时，需要将未匹配到的节点进行隐藏

节点中添加以下属性，用于标识节点是否隐藏。

  isHide?: boolean; // 过滤后是否不显示该节点

同3.3中核心处理逻辑大同小异，通过双层循环，节点的 isMatched 和 childrenMatched 以及父节点的 isMatched 设置自身节点是否显示。

核心代码如下：

const dealNodeHideProperty = () => {
  data.value.forEach((item, index) => {
    if (item.isMatched || item.childrenMatched) {
      item.isHide = false;
    } else {
      // 需要判断是否有父节点有匹配
      if (!item.parentId) {
        item.isHide = true;
        return;
      }
      let L = index - 1;
      const set = new Set();
      set.add(data.value[index].parentId);
      while (L >= 0 && data.value[L].parentId && !hasParentNodeMatched(L, index, set)) {
        if (set.has(data.value[L].id)) {
          set.add(data.value[L].parentId);
        }
        L--;
      }
      if (!data.value[L].parentId && !data.value[L].isMatched) {
        // 没有parentId, 说明已经访问到当前节点所在的根节点
        item.isHide = true;
      } else {
        item.isHide = false;
      }
    }
  });
};

const hasParentNodeMatched = (pre: number, cur: number, parentIdSet: Set) => {
    return parentIdSet.has(data.value[pre].id) && data.value[pre].isMatched;
};

3.5 第五步：处理匹配节点的高亮显示

如果该节点被匹配，将节点的label处理成[preMatchedText, matchedText, postMatchedText]格式的数组。 matchedText添加 span标签包裹，通过CSS样式显示高亮效果。

const matchedContents = computed(() => {
    const matchItem = data.value?.matchedText || '';
    const label = data.value?.label || '';
    const reg = (str: string) => str.replace(/[-[\]{}()*+?.,\\^$|#\s]/g, '\\$&');
    const regExp = new RegExp('(' + reg(matchItem) + ')', 'gi');
    return label.split(regExp);
});


    { !data.value?.matchedText && data.value?.label }
    {
      data.value?.matchedText
      && matchedContents.value.map((item: string, index: number) => (
        index % 2 === 0
        ? item
        : {item}
      ))
    }

3.6 第六步：tree组件采用虚拟列表时，需将滚动条滚动至第一个匹配的节点，方便用户查看

先得到目前整个树显示出来的节点，找到第一个匹配的节点下标。调用虚拟列表组件的 scrollTo 方法滚动至该匹配节点。

const getFirstMatchIndex = (): number => {
  let index = 0;
  const showTreeData = getExpendedTree().value;
  while (index <= showTreeData.length - 1 && !showTreeData[index].isMatched) {
      index++;
  }
  return index >= showTreeData.length ? 0 : index;
};

const scrollIndex = getFirstMatchIndex();
virtualListRef.value.scrollTo(scrollIndex);

通过 scrollTo 方法定位至第一个匹配项效果图：

原始树结构显示图：

过滤功能：

4 遇到的难点问题

4.1 搜索的核心在于对匹配节点的所有父节点的访问以及处理

整棵树数据结构就是一个一维数组，向上需要将匹配节点所有的父节点全部展开，向下需要知道有没有子节点存在匹配。传统tree组件的数据结构是树形结构，通过递归的方式完成节点的访问及处理。对于扁平的数据结构应该如何处理？

方案一：扁平数据结构 --> 树形结构 --> 递归处理 --> 扁平数据结构（NO）
方案二： node添加parent属性，保存该节点父级节点内容 --> 遍历节点处理自身节点及parent节点（No）
方案三：同过双层循环，第一层循环处理当前节点，第二层循环处理父节点（Yes）