一、问题背景及需求
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)
}
}