扁平树状数据处理及多层关键字搜索实现

4,230 阅读3分钟

一、问题背景及需求

1.需求

  • 实现多层关键字模糊搜索;
  • 搜索整颗树节点,包括非子节点和子节点,命中时自动展开其父节点;
  • 非子节点命中时,其子节点全部保留;
  • 节点命中关键字高亮。

[搜索前树状展示]

[搜索关键字"测试"]

2.存在问题

  • 后端返回的数据为扁平化数据,展示需要转成树状结构。
  • 数据量大,共4000+数据,为性能考虑,实现搜索功能时需要减少遍历次数。

二、实现原理

1.扁平数据转化树状结构实现

原理

  • 将散乱扁平化的节点构造成以id为索引的对象据

  • 遍历扁平化节点,逐一寻找其父节点,并插入。

    同时判断是否根节点,若是直接抽出根节点。

代码实现

需要遍历两次数据:构造以id为索引的对象、寻找父节点据

(根节点parent === '0')

/**
 * 扁平结构转成树状结构
 * @param category 扁平数据
 */
formateTree = (category) => {
  const treeMap = {} // 以id为索引的对象
  const tree = [] // 最后树状结果
  
  category.forEach((o) => {
    treeMap[o.id] = Object.assign(o, { children: [] }
  })
  
  category.forEach((o) => {
    if (o.parent !== '0') {
      treeMap[o.parent].children.push(treeMap[o.id])
    } else if (o.parent === '0') {
      tree.push(treeMap[o.id])
    }
  })
  return tree
}

2.实现多层关键字模糊搜索

准备

  • 树状结构
  • 以id为索引的对象
  • 存放各路径下第一个命中节点的数组 filterNode[]
  • 存放最终结果的数组 treeData[]

原理

1.【递归】根据关键字遍历树状结构寻找各路径下第一命中节点 findTargetNode() ,并插入filterNode[],将节点parent 插入expandedList[]。

命中标记:⭐

2.【递归】展开非子节点下包含关键字节点的路径 findExpandedNode() ,将命中节点parent 插入expandedLish[]。

⚠️ 注意,如中间有两层以上没有命中关键字,则无法展开,最后需要根据expandedList[] 中的节点向上补齐 insertNodeParent() 。

3.【递归】寻找命中节点的父节点,拼接成树 findParend() 。

4.expandedList[] 去重。

【递归】根据filterNode[] 中的节点向上补齐已展开节点的各级父节点,用到索引对象 insertNodeParent()。

5.原理同3

6.expandedList[] 去重。

代码实现

  • findTargetNode()

    第一命中节点为末节点时:插入(将该节点push 进filterNode[] ),展开(并将其父id push 到expandedList[] )。

    第一命中节点为非子节点时:插入,并需要遍历该路径继续寻找剩余命中节点 findExpandedNode() 。

const findTargetNode = (val, tree, filterNode, expandedList) => {
  tree.forEach((item) => {
    if (item.title.indexOf(val) > -1) {
      if (!item.children.length) {
        filterNode.push(item);
        expandedList.push(item.parent);
      } else {
        filterNode.push(item);
        expandedList.push(item.parent);
        findExpandedNode(val, tree, expandedList);
      }
    } else {
      findTargetNode(val, item.children, filterNode, expandedList);
    }
  })
}

  • findExpandedNode()

    末节点包含关键字:展开;不包含:不处理。

    非末节点包含关键字:展开,继续递归;不包含:继续递归。

const findExpandedNode = (val, tree, expandedList) => {
  tree.forEach((item) => {
    if (!item.children.length && item.title.indexOf(val) > -1) {
      expandedList.push(item.parent);
    } else if (item.children.length && item.title.indexOf(val) > -1) { 
      expandedList.push(item.parent);
      findExpandedNode(val, item.children, expandedList)
    } else if (item.children.length && item.title.indexOf(val) === -1) {
      findExpandedNode(val, item.children, expandedList)
    }
  })
}

  • findParend()

    父节点不是根节点

      目前对象树中父节点是否已包含该节点,包含:不梳理;未包含:插入父节点。(避免重复)
    

    父节点为根节点

      目前结果中,是否已包含该根节点,包含:不处理;未包含:插入结果中。 
    
const findParend = (item, treeMap, treeData, expandedList) => {
  if (item.parent !== '0') {
    const ids = treeMap[item.parent].children.map(o => o.id);
    if (!ids.includes(item.id)) {
      treeMap[item.parent].children.push(item);
      expandedList.push(item.parent);
      findParend(treeMap[item.parent], treeMap, treeData, expandedList);
    }
  } else {
    const ids = treeData.map(o => o.id);
    if (!ids.includes(item.id)) {
      treeData.push(item);
      expandedList.push(item.id)
    }
  }
}

  • expandedList[] 去重

    Es6 set数据结构

expandedList = [...new Set(expandedList)]

  • insertNodeParent()

    当前节点为非根节点时,插入该节点父id

    当前节点为根节点时,返回

const insertNodeParent = (key, expandedList, treeMap) => {
  if (key === '0') {
    return 
  }
  const { parent } = treeMap[key]
  expandedList.push(parent)
  if (parent !== '0') {
    insertNodeParent(parent, expandedList, treeMap)
  }
}