Javascript递归算法
一、首先来一道开胃菜，css方面问题
在前端方面，渲染列表数据的时候，可能会更改第一个或者最后一个的样式，又或者其中第几个的样式，怎么做呢？
其实很简单，便是使用last-child选择器相关知识。
问题是，有时候，我们使用last-child会出现失效的问题。
先来个实际场景：
目的：给最后一个class=”invalid”的元素添加背景色。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
<h1>这样是无效的，也就是last-child失效了</h1> <div class="question"> <div class="invalid">111111</div> <div class="invalid">222222</div> <div class="invalid">333333</div> <div class="invalid">444444</div> <div class="invalid">555555</div> <div class="invalid">666666</div> <div class="disturb">777777</div> </div> <style lang="scss" scoped> .question { .invalid:last-child { background-color: cornflowerblue; } } </style> |
为啥会失效？主要问题就是最后有个class=”disturb”的元素。
使用last-child选择器必须要有个容器包裹，否则就会失效，把上面class=”invalid”元素再用一个div包裹起来便可以了。
改成以下便可以了
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
<div class="question"> <div> <div class="invalid">111111</div> <div class="invalid">222222</div> <div class="invalid">333333</div> <div class="invalid">444444</div> <div class="invalid">555555</div> <div class="invalid">666666</div> </div> <div> <div class="invalid">111111</div> <div class="invalid">222222</div> <div class="invalid">333333</div> <div class="invalid">444444</div> <div class="invalid">555555</div> <div class="invalid test">666666</div> <!-- 这样也是可以的 --> </div> <div class="disturb">777777</div> </div> |
二、重点来了
list转树型数据
关于这一点，个人觉得前端一般不需要这么做，毕竟前端主要负责进行数据渲染，以及用户交互。
但将list转为树型数据，里面涉及到的算法，我们还是要了解一下的。
将list转为树型数据，一般用到的是递归跟多次遍历方法。
其他的方法便不多做介绍了。在此介绍掌握最高效的方法，一次遍历即可。
list数据
|
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 |
[ { id: 1, pid: 0, name: "一级数据1" }, { id: 2, pid: 0, name: "一级数据2" }, { id: 3, pid: 0, name: "一级数据3" }, { id: 4, pid: 1, name: "二级数据2-1" }, { id: 5, pid: 1, name: "二级数据2-2" }, { id: 6, pid: 1, name: "二级数据2-3" }, { id: 7, pid: 3, name: "三级数据3-1" }, { id: 8, pid: 3, name: "二级数据3-2" }, { id: 9, pid: 8, name: "三级数据3-1" } ] |
树型数据
|
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 |
[{ id: 1, pid: 0, name: "一级数据1", children: [{ id: 4, pid: 1, name: "二级数据2-1" }, { id: 5, pid: 1, name: "二级数据2-2" }, { id: 6, pid: 1, name: "二级数据2-3" } ] }, { id: 2, pid: 0, name: "一级数据2" }, { id: 3, pid: 0, name: "一级数据3", children: [{ id: 7, pid: 3, name: "三级数据3-1" }, { id: 8, pid: 3, name: "二级数据3-2", children: [{ id: 9, pid: 8, name: "三级数据3-1" }] }, ] } ] |
为了实现这个目的，我们需要了解很多的知识点。
1、基本的原理
每条数据都要有相应的id跟pid
id指的是这条数据的主键（就这么理解吧），一定要是唯一的。
pid指的是这条数据的上级数据的主键id，（相当于组织机构中，上级组织机构的主键id）。
当每条数据满足具有id跟pid的时候，那便可以将数据转为树型结构。
2、JavaScript是弱类型语言。举个例子：
|
1 2 |
var o={};// 申明一个o空对象变量（里面没有任何的属性，不是null） o.children=[];// 给o变量添加一个数组类型的变量children。这便是与强类型的区别。强类型语言必须要在一个class里面将变量都定义好。 |
3、引用类型（这个便是重中之重了，也是为啥一次遍历便能够实现想要的结果的原因）
引用类型，变量存储的是地址，而地址对应的是值，我们需要做的是改变值，但这个变量名称是不变的，也就是地址是不变的，值是改变的。
通过定义一个变量itemMap，动态地给itemMap添加id属性值，而itemMap属性的值为list中的一个数组对象，并且循环遍历的时候，不断给itemMap属性值添加相应的children。
详细代码如下：
|
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 |
// list转树型数据 function listToTree(data, mapping) { let listData = JSON.parse(JSON.stringify(data)); let idMap = 'id'; let pidMap = 'pid'; if (mapping) { idMap = mapping.id; pidMap = mapping.pid; } // 以上部分主要是针对list的id跟parentid字段，万一不是id跟pid的。 listData.sort((a, b) => { return Number(a[idMap]) - Number(b[idMap]) });// 如果没有排序的话，生成的树形数据会出问题 let result = [];// 存储最终的结果 let itemMap = {};// 这个对象变量便是最核心的地方 for (let item of listData) { // for-of遍历 let id = item[idMap]; // 获取id let pid = item[pidMap]; // 获取pid itemMap[id] = item;// 开始给itemMap变量赋值 let parentData = itemMap[pid];// 浅拷贝 父亲节点 if (!parentData) { result.push(itemMap[id]); continue; // 结束当前循环，继续下一个循环 } if (!parentData.children) { parentData.children = [];//这样做的话，给有子集的项添加children属性，没子集的话，便没有children属性 } parentData.children.push(item); } return result; } |
树型数据转list（倒过来）
这个，暂时没想到什么更好的方法，便用递归实现了。
递归，有个很形象的说法，一层一层地拨开你的心！！！
|
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 |
// 树型数据转list function treeToList(tree, mapping) { var list = []; let childrenName = 'children'; if (mapping) { childrenName = mapping.children; } handleTreeToList(tree, list, childrenName); return list; } // 递归方法 function handleTreeToList(tree, list, childrenName) { if (!tree || !tree.length) { return; } for (let item of tree) {// 遍历 let temp = JSON.parse(JSON.stringify(item));// 深拷贝 if (item[childrenName]) { delete temp[childrenName];// 删除子项 } list.push(temp); if (item[childrenName]) { handleTreeToList(item[childrenName], list, childrenName);// 递归调用 } } } |
三、扩展（递归的使用，巩固递归算法）
给树型数据每项添加额外的数据
|
1 2 3 4 5 6 7 8 9 10 |
// 给树型数据每项添加flag属性 function addDataTree(tree, childrenName) { if (childrenName == undefined) childrenName = 'children'; for (let item of tree) { item.flag = false;// 添加flag属性 if (item[childrenName]) addDataTree(item[childrenName], childrenName);// 递归调用 } } |
四、总结
递归算法，还是很有必要掌握的，在树型结构方面经常会用到。
希望疫情早点结束！！！