记录JS如何使用广度遍历找到节点的所有父节点
- 2019 年 10 月 21 日
- 筆記
我们在实际的工作业务场景中经常遇到这样的场景，求取树数据中某个节点的父亲节点以及所有的父亲节点，这样的场景下不建议使用深度遍历，使用广度遍历可以更快找到。
1、案例解说
比如树的长相是这样的：
树的数据是这样的：
是我们常用的树的数据及长相。
2、业务要求
在【测试抽取5】后面新增一个节点，要求
1）接口要求传入当前节点的父节点；
2）新增后重新获取树数据，默认展开所有的父级
3、代码实现及说明
思路：
1）设定一个排队数组parentIdsQueue将树数据开始排队；
2）如果当前数据有孩子节点，将孩子节点倒序加入队列中，因为遍历的时候是从第一个数据开始的；
3）如果当前数据有孩子节点，在孩子加入队列前，把父亲节点的数据放到parentArr中；
4）如果找到了节点，如果是第一层的节点，直接获取即可；如果包括parentArr，则parentArr中的全是它的父级节点
多说无益，先上实现代码
// id 指的是当前点击的节点id; findParentNode (id) { // 初始化所需数据 this.firstParentObj = {}; // 记录直系父级的名称和id即接口要传的数据 this.parentIds = []; // 记录所有的父级ids this.parentIdsQueue = []; // 记录排队的 // 将树放到排队系列 this.parentIdsQueue = this.treeData; // 开始遍历排队的树 while (this.parentIdsQueue.length) { let item = this.parentIdsQueue.shift(); let { children } = item; if (item.id === id) { this.parentIds = []; // 第一层就找到了 if (!item.parentArr) { this.firstParentObj = { id: item.id, name: item.title }; this.parentIds = [item.id]; } else { // 获取当前节点的parentArr let len = item.parentArr.length; this.firstParentObj = item.parentArr[len - 1]; item.parentArr.forEach(a => { this.parentIds.push(a.id); }); this.parentIds.push(item.id); } // 结束遍历 this.parentIdsQueue = []; break; } else if (children && children.length) { let len = children.length; for (let i = len - 1; i >= 0; i--) { // 记录它的父亲节点 children[i].parentArr = []; // 把它的历史父亲节点们先放入 if (item.parentArr) { children[i].parentArr = children[i].parentArr.concat( item.parentArr ); } // 再放入当前的父亲节点 children[i].parentArr.push({ id: item.id, name: item.title }); this.parentIdsQueue.unshift(children[i]); } } } }5、结果演示
我们在文前举的例子中添加个节点，我们打印出所需的数据
console.log("测试抽取5的所有父亲",item.parentArr); console.log("接口所需的父亲节点数据",this.firstParentObj); console.log("设置树展开所需的所有父亲节点数据节点id", this.parentIds);
