如何将评论数据从扁平数组结构转为树形结构

蚊子前端博客
发布于 2022-02-28 10:09
以前的文章只讨论了下数据表的设计,这里我们主要讲解下如何从算法上把数组结构的数据转为树形结构

我们在之前的文章 如何实现一个楼中楼的评论系统,主要讲解了楼中楼评论系统的设计初衷、数据库表的结构,但没有讲解从数据库中拿到数据后,如何转成楼中楼的结构。

1. 定义下数据结构

我是使用的 mysql 数据库,mysql 数据库中是以为单位,来存储数据的。

我们从数据库中拿到的数据是一个数组结构,大致如下,我最初考虑楼中楼最多只嵌套一层,因此加了一个pid字段用来表示该评论在哪个评论里:

COPYJAVASCRIPT

/** * 从数据库中查询到一篇文章里的所有评论 * id: 当前评论的id * pid: 当前评论在哪个评论里,0表示是顶层评论 * replyid: 该评论回复的是哪个评论,0表示是顶层评论 * content: 内容 */ const list = [ { id: 1, pid: 0, replyid: 0, nick: '111', content: '' }, { id: 2, pid: 0, replyid: 0, nick: '222', content: '' }, { id: 3, pid: 2, replyid: 2, nick: '333', content: '' }, { id: 4, pid: 2, replyid: 3, nick: '444', content: '' }, { id: 5, pid: 2, replyid: 4, nick: '555', content: '' }, { id: 6, pid: 1, replyid: 1, nick: '666', content: '' }, { id: 7, pid: 2, replyid: 3, nick: '777', content: '' }, ];

接下来,让我们通过代码来实现下数组转为树(楼中楼)的结构。

2. 嵌套一层的楼中楼

我们先实现一个只嵌套一层的树结构。

我们要实现的结构是这样的,若直接回复上层的评论,则省略该评论回复的是谁,若回复的是楼中楼的评论,则展示出回复的是哪条:

COPYBASH

- 1 |- 6 - 2 |- 3 |- 4 -> 3 |- 5 -> 4 |- 7 -> 3

我们分析下 list 中数据的特点:

  • 每条数据都有个pidreplyid两个字段,指向他的父级,但若 pid 和 replyid 为 0 时,则表示该评论自己就是最顶层的评论;

  • 后一条评论回复之前的评论,pid 和 replyid 两个字段的值一定是存在的(不可能回复一条不存在的评论);

依托于 js 中的对象引用的特性:在不同的地方操作相同的对象,所有使用该对象的数据都会发生变化。其实这并不是一个好的特性,但在这里特别好使。我们可以直接把后面的数据添加到前面的数据字段中。

COPYJAVASCRIPT

const listToTree = (list) => { const newList = JSON.parse(JSON.stringify(list)); // 避免影响外层的数组 const map = new Map(); const result = []; newList.forEach((comment) => { map.set(comment.id, comment); if (comment.pid) { // 楼中楼的评论 const parentComment = map.get(comment.pid); // 回复的该评论,该评论是一定存在的 if (!parentComment.children) { parentComment.children = []; // 通过对象引用,可以直接修改之前的数据 } if (comment.pid !== comment.replyid) { comment.replyNick = map.get(comment.replyid).nick; } parentComment.children.push(comment); } else { result.push(comment); } }); return result; };

最终实现的效果的示意图:

list2tree-蚊子的前端博客

3. 不限制层数的树结构

若我们不限制树结构的层数,该怎么实现呢?

我们在这里把 list 数组的结构稍微改下,去掉 pid 的干扰,并再添加几条数据:

COPYJAVASCRIPT

/** * 从数据库中查询到一篇文章里的所有评论 * id: 当前评论的id * replyid: 该评论回复的是哪个评论,0表示是顶层评论 * content: 内容 */ const list = [ { id: 1, replyid: 0, nick: '111', content: '' }, { id: 2, replyid: 0, nick: '222', content: '' }, { id: 3, replyid: 2, nick: '333', content: '' }, { id: 4, replyid: 3, nick: '444', content: '' }, { id: 5, replyid: 4, nick: '555', content: '' }, { id: 6, replyid: 1, nick: '666', content: '' }, { id: 7, replyid: 3, nick: '777', content: '' }, { id: 8, replyid: 5, nick: '888', content: '' }, { id: 9, replyid: 8, nick: '999', content: '' }, { id: 10, replyid: 9, nick: 'aaa', content: '' }, { id: 11, replyid: 10, nick: 'bbb', content: '' }, ];

其实不限制树结构的层数,要比固定的层数简单一些,不用判断是否要折叠树结构,一直追加下去即可。

3.1 使用循环的方式

我们顺着上面循环的方式,来实现下不限制层数的树结构。

COPYJAVASCRIPT

const listToTreeDeep = (list) => { const newList = JSON.parse(JSON.stringify(list)); // 避免影响之前的数组 const map = new Map(); const result = []; newList.forEach((comment) => { map.set(comment.id, comment); if (comment.replyid) { // 楼中楼的评论 const parentComment = map.get(comment.replyid); // 回复的该评论,该评论是一定存在的 if (!parentComment.children) { parentComment.children = []; } // 这里按照层级来表示回复关系,不再获取要回复的哪个评论 // if (comment.pid !== comment.replyid) { // comment.replyNick = map.get(comment.replyid).nick; // } parentComment.children.push(comment); } else { result.push(comment); } }); return result; };

最终实现的效果示意图:

listToTreeDeep-蚊子的前端博客

具体效果可以查看实现的 demo:【 数组转树结构的自定义层数的循环实现方式 】。

3.2 使用递归的方式

无限嵌套的结构也可以使用递归的方式,但这并不是最好的方式,因为每次递归都要用当前 id 循环查找一次。

我们在这里用代码实现一次,但不推荐这种方式。

COPYJAVASCRIPT

/** * @param {any[]} list 评论列表 * @param {number} replyid 回复的那个评论的id **/ const listToTreeRecursion = (list, replyid = 0) => { const newList = JSON.parse(JSON.stringify(list)); // 避免影响之前的数组 const result = []; newList.forEach((comment) => { if (comment.replyid === replyid) { comment.children = listToTreeRecursion(list, comment.id); result.push(comment); } }); return result; };

递归中我们不使用额外的数据来存储数据,是因为每次的执行,都会从头循环一遍。

4 自定义层数的树结构

若再复杂一点,可以自定义层数 n,前 n-1 层一直向内嵌套,最后的第 n 层采用平铺的方式。即把前面的两种展示方式进行结合。

这里我们依然分成两部分来讲解。

4.1 使用循环的方式

上面不限制层数时,直接往其父级的 children 属性中追加即可。但现在可以自定义层数后,就要在循环时,判断当前节点的深度,若该节点的深度小于 设定的层数 n ,则添加到其父级的 children 中;否则就得添加到其深度为 n-1 的祖先节点的 children 里。

我在这里使用了两个字段来进行标记:

  1. deep: 当前节点的深度;

  2. pid: 该节点所属的父级节点是哪个;

具体的代码实现:

COPYJAVASCRIPT

/** * @param {any[]} list 评论列表 * @param {number} maxPath 自定义的层数 **/ const listToTreeSelf = (list, maxPath = 4) => { const newList = JSON.parse(JSON.stringify(list)); const map = new Map(); const result = []; newList.forEach((comment) => { map.set(comment.id, comment); if (comment.replyid) { // 楼中楼的评论 const parentComment = map.get(comment.replyid); comment.deep = parentComment.deep + 1; // 当前深度是父级节点的深度+1 if (comment.deep >= maxPath) { // 若当前节点的深度超过了设定的最大深度 // 则该节点不能挂载在其父节点了, // 通过父节点的pid查找父节点挂载在哪个节点上, // 该节点也挂载上面 const ancestorComment = map.get(parentComment.pid); comment.replyNick = parentComment.nick; if (!ancestorComment.children) { ancestorComment.children = []; } // 当前节点挂载的节点 comment.pid = ancestorComment.id; ancestorComment.children.push(comment); } else { // 没有超过设定的最大深度 // 挂载在其父节点上 if (!parentComment.children) { parentComment.children = []; } comment.pid = parentComment.id; parentComment.children.push(comment); } } else { comment.deep = 0; result.push(comment); } }); return result; };

假设我们设定的最大层数为 4,最终的效果是:

listToTreeSelf-蚊子的前端博客

4.2 使用递归的方式

在使用递归的方式来构建自定义层数的树形结构时,当深度达到设定的最大层级时,就需要转为循环了。然后开始查找该节点下所有的子节点和子孙节点。

注意:这里不要遗漏子孙节点。

COPYJAVASCRIPT

const listToTreeSelfRecursion = (list, maxPath = 4, replyid = 0) => { const newList = JSON.parse(JSON.stringify(list)); // 避免影响之前的数组 const result = []; newList.forEach((comment) => { if (maxPath <= 1) { // 到达最内层 // 查找最直接的子节点 if (comment.replyid === replyid) { result.push(comment); } else { // 查找所有的子孙节点 const child = result.find((child) => child.id === comment.replyid); if (child) { comment.replyNick = child.nick; result.push(comment); } } } else { // 还可以继续递归 if (comment.replyid === replyid) { comment.children = listToTreeSelfRecursion(list, maxPath - 1, comment.id); result.push(comment); } } }); return result; };

5. 不规则的数组

我们在上面所有的循环实现中,都默认了父节点在前面,毕竟对评论系统而言,肯定现有的父级评论,才能有当前评论。但比如我们把场景扩展到无限嵌套的部门列表中时,就不一定有序了。

最近新创建了一个中间部门,然后把下面所有的部门都归属到这个中间部门里。就会出现父级节点在后面的情况。

这里我们只以不限层数的循环实现方式为例,看下若父级节点在后面,如何实现:

COPYJAVASCRIPT

// 把数据调换下位置 const list = [ { id: 6, pid: 1, replyid: 1, nick: '666', content: '' }, { id: 7, pid: 2, replyid: 3, nick: '777', content: '' }, { id: 8, pid: 2, replyid: 5, nick: '888', content: '' }, { id: 9, pid: 2, replyid: 8, nick: '999', content: '' }, { id: 10, pid: 2, replyid: 9, nick: 'aaa', content: '' }, { id: 11, pid: 2, replyid: 10, nick: 'bbb', content: '' }, { id: 1, pid: 0, replyid: 0, nick: '111', content: '' }, { id: 2, pid: 0, replyid: 0, nick: '222', content: '' }, { id: 3, pid: 2, replyid: 2, nick: '333', content: '' }, { id: 4, pid: 2, replyid: 3, nick: '444', content: '' }, { id: 5, pid: 2, replyid: 4, nick: '555', content: '' }, ]; const listToTreeDeep = (list) => { const newList = JSON.parse(JSON.stringify(list)); // 避免影响之前的数组 const map = new Map(); const result = []; newList.forEach((comment) => { // 可能先把该节点的children存储起来 // 这里把之前存储的数据合并下,然后再存储起来 comment = { ...comment, ...map.get(comment.id) }; map.set(comment.id, comment); if (comment.replyid) { // 楼中楼的评论 const parentComment = map.get(comment.replyid) || {}; // 以空的Object兜底 if (!parentComment.children) { parentComment.children = []; } parentComment.children.push(comment); map.set(comment.replyid, parentComment); } else { result.push(comment); } }); return result; };

可见在乱序的情况下,逻辑就要多一些。在可行的情况,我们把父级节点放在前面,但若实现起来比较困难,上面的那种方式也是可行的。

6. 总结

我们从最开始的二层楼中楼结构,扩展到了无限层级,最终扩展到了可以自定义层级。就目前递归的实现方式来看,并没有循环的性能好,因为每次递归都要循环一遍数据,若在数组节点比较多时,递归的性能就会直线下降。

下一篇文章,我们再讨论下,如何把树形结构转成数组结构

标签:
阅读(296)

公众号:

qrcode

微信公众号:前端小茶馆

公众号:

qrcode

微信公众号:前端小茶馆