【079】利用“剪叶子”算法实现树形结构的搜索功能,用Vue.js实现
业务场景工作中碰到这样的一个场景:需要对一个树形结构进行搜索,凡是匹配的节点都要保留。如果这个匹配的节点存在父节点,那么不论这个父节点是否匹配搜索内容,都要保留,并按照树形结构展示出来。如果一个节点既不匹配搜索内容,同时也没有匹配搜索内容的子节点,那么该节点就不再保留。效果如下面这个gif动画所示:数据结构场景中的数据结构类似这种形式:export default func
·
业务场景
工作中碰到这样的一个场景:需要对一个树形结构进行搜索,凡是匹配的节点都要保留。如果这个匹配的节点存在父节点,那么不论这个父节点是否匹配搜索内容,都要保留,并按照树形结构展示出来。如果一个节点既不匹配搜索内容,同时也没有匹配搜索内容的子节点,那么该节点就不再保留。
效果如下面这个gif动画所示:
数据结构
场景中的数据结构类似这种形式:
export default function(){
let arr =[
{
name:'学习',
children:[
{ name: "杂志" },
{ name: "纸质书" },
{
name:'电子书',
children:[
{
name:'文学',
children:[
{name:'茶馆'},
{name:'红与黑'},
{name: "傅雷家书"}
]
}
]
}
]
},
{
name:'电影',
children:[
{ name:'美国电影' },
{ name:'日本电影' }
]
}
]
return arr;
} // end function
算法思路
- 利用树的遍历算法,找到每个叶子节点及其父节点。
- 判断叶子节点是否匹配搜索内容,如果匹配则保留;如果不匹配,就把这个叶子节点从它的父节点 children 数组中删除。
- 这么做,一次只能搜索一层叶子节点,如果数据结构里有多层节点没有匹配,就需要重复步骤 1 和步骤 2 。重复的次数应该是树的深度减去1。要减一是因为根节点没有父节点,自然也不能执行【从父节点 children 数组中删除】的操作。
- 最后对根节点做判断,如果根节点有子节点,那么什么也不做。如果树形结构只有一个根节点,若根节点不匹配,则删除;若根节点匹配,则保留。
下面的图片演示了算法的过程:
代码实现
我用一个项目做了个Demo。项目名称是blog079。大家可以在 https://git.oschina.net/zhangchao19890805/csdnBlog 中看到此项目。
项目文件结构如下:
blog079
├─ src
│ ├─App.vue
│ ├─data.js
│ ├─home.vue
│ ├─main.js
│ ├─router.js
│ └─treeNode.vue
│
├─.babelrc
├─index.template.html
├─package.json
├─webpack.config.js
└─yarn.lock
本文只说明一些主要代码。
数据来源:data.js
export default function(){
let arr =[
{
name:'学习',
children:[
{
name: "杂志",
children:[
{
name:"电脑杂志",
children:[
{name:"大众软件"}
]
}
]
},
{
name: "纸质书"
},
{
name:'电子书',
children:[
{
name:'文学',
children:[
{
name:'茶馆'
},
{
name:'红与黑'
},
{
name: "傅雷家书"
}
]
}
]
}
]
},
{
name:'电影',
children:[
{
name:'美国电影3'
},
{
name:'日本电影'
},
{
name:"23"
}
]
}
]
return arr;
} // end function
展示树形结构的组件 treeNode.vue
<template>
<li>
<!-- 显示当前节点名称 -->
<span v-html="nodeName"></span>
<!-- 如果存在孩子节点,循环子节点数组,并递归调用本组件。 -->
<ul v-if="isHasChildren">
<tree-node v-for="(item,index) in node.children" :key="index" :node="item"
:search-text="searchText">
</tree-node>
</ul>
</li>
</template>
<script>
export default {
name:"tree-node",
props:["node", "searchText"],
// data(){
// return {};
// }
computed:{
// 判断当前节点是否存在孩子节点
isHasChildren(){
let flag = false;
if (this.node.children && this.node.children.length > 0) {
flag = true;
}
return flag;
},
// 如果当前节点名称,有文字和搜索内容匹配,就把匹配的文字标红。
// 反之,则正常显示节点名称。
nodeName(){
if (this.searchText == undefined || this.searchText == "" || this.searchText == null) {
return this.node.name;
}
if (this.node.name.indexOf(this.searchText) <= -1) {
return this.node.name;
}
return this.replaceAll(this.node.name, this.searchText,
"<span style='color:red;'>" + this.searchText + "</span>");
}
},
methods:{
/**
* 替换掉原字符串中所有的子字符串。不使用正则表达式的实现。
* 当遇到特殊字符的时候,不用输入适应正则的转义。
* @param String str 原字符串
* @param String substr 要被替换的子串
* @param String replacement 新的子串
*/
replaceAll(str, substr, replacement){
if (!str) {
return "";
}
return str.split(substr).join(replacement);
}
}
};
</script>
<style lang="scss" rel="stylesheet/scss" scoped></style>
主页面 home.vue。包含搜索功能。
<template>
<!--
功能:
1.利用递归组件展示树形结构。
2.利用“剪叶子”的算法搜索树的节点。
作者:张超
-->
<div>
<p>这里是首页</p>
<p><input type="text" placeholder="搜索" @keyup.enter="search($event)"></p>
<ul v-if="nodeList && nodeList.length > 0">
<tree-node v-for="(item,index) in nodeList" :key="index" :node="item"
:search-text="searchText"></tree-node>
</ul>
<div v-else>没有搜索到相应结果</div>
</div>
</template>
<script>
import nodeListFunc from "./data.js";
import treeNode from "./treeNode.vue";
export default {
data(){
let list = nodeListFunc();
return {
nodeList: list,
searchText: ""
};
},
components:{
treeNode
},
methods:{
// 对子节点进行搜索。
searchEach(node, value){
let depth = this.getTreeDepth(node);
let self = this;
for (let i = 0; i < depth - 1; i++) {
// 记录【删除不匹配搜索内容的叶子节点】操作的次数。
// 如果这个变量记录的操作次数为0,表示树形结构中,所有的
// 叶子节点(不包含只有根节点的情况)都匹配搜索内容。那么就没有必要再
// 在循环体里面遍历树了.
let spliceCounter = 0;
// 遍历树形结构
this.traverseTree(node, n=>{
if (self.isHasChildren(n)) {
let children = n.children;
let length = children.length;
// 找到不匹配搜索内容的叶子节点并删除。为了避免要删除的元素在数组中的索引改变,从后向前循环,
// 找到匹配的元素就删除。
for (let j = length - 1; j >= 0; j--) {
let e3 = children[j];
if (!self.isHasChildren(e3) && e3.name.indexOf(value) <= -1) {
children.splice(j,1);
spliceCounter++;
}
} // end for (let j = length - 1; j >= 0; j--)
}
}); // end this.traverseTree(node, n=>{
// 所有的叶子节点都匹配搜索内容,没必要再执行循环体了。
if (spliceCounter == 0) {
break;
}
}
},
// 搜索框回车事件响应
search(e){
let self = this;
// 把树形结构还原成搜索以前的。
this.nodeList = nodeListFunc();
if (e.target.value=="") {
this.searchText = "";
return;
}
if (this.nodeList && this.nodeList.length > 0) {
this.nodeList.forEach((n,i,a)=>{
self.searchEach(n, e.target.value);
});
// 没有叶子节点的根节点也要清理掉
let length = this.nodeList.length;
for (let i = length - 1; i >= 0; i--) {
let e2 = this.nodeList[i];
if (!this.isHasChildren(e2) && e2.name.indexOf(e.target.value) <= -1) {
this.nodeList.splice(i, 1);
}
}
this.searchText = e.target.value;
}
},
// 判断树形结构中的一个节点是否具有孩子节点
isHasChildren(node){
let flag = false;
if (node.children && node.children.length > 0) {
flag = true;
}
return flag;
},
// 通过传入根节点获得树的深度,是 calDepth 的调用者。
getTreeDepth(node){
if (undefined == node || null == node) {
return 0;
}
// 返回结果
let r = 0;
// 树中当前层节点的集合。
let currentLevelNodes = [node];
// 判断当前层是否有节点
while(currentLevelNodes.length > 0){
// 当前层有节点,深度可以加一。
r++;
// 下一层节点的集合。
let nextLevelNodes = new Array();
// 找到树中所有的下一层节点,并把这些节点放到 nextLevelNodes 中。
for(let i = 0; i < currentLevelNodes.length; i++) {
let e = currentLevelNodes[i];
if (this.isHasChildren(e)) {
nextLevelNodes = nextLevelNodes.concat(e.children);
}
}
// 令当前层节点集合的引用指向下一层节点的集合。
currentLevelNodes = nextLevelNodes;
}
return r;
},
// 非递归遍历树
// 作者:张超
traverseTree(node, callback) {
if (!node) {
return;
}
var stack = [];
stack.push(node);
var tmpNode;
while (stack.length > 0) {
tmpNode = stack.pop();
callback(tmpNode);
if (tmpNode.children && tmpNode.children.length > 0) {
for (let i = tmpNode.children.length - 1; i >= 0; i--) {
stack.push(tmpNode.children[i]);
}
}
}
}
}
};
</script>
<style lang="scss" rel="stylesheet/scss" scoped>
</style>
更多推荐
已为社区贡献12条内容
所有评论(0)