多叉树结构的数据,parent表示法转成children表示法
2024-10-01 05:00:27
最近碰到的问题,有个数组,数组元素是对象,该对象的结构就如树的parent表示法的节点一样。形象点讲就是该数组存放了树的所有“叶子节点”,并且叶子节点内存有父节点,一直到根节点为止,就如存了一条从叶子节点到根节点路径。
现在有要求是将这个数组转成一个children表示法的对象,即从根节点开始,每个节点存有其子节点数组。转化效果如下(节点必须有个唯一标识符,以下id就是,并且转化前后其他属性保持不变,这里为了显示简洁没有加入其他属性。):
核心思想是使用递归,新建唯一的根节点开始,不断生长出子节点。并再插入子节点时判断子节点是否存在,存在的话不插入,反之插入。注意所有将子节点插入到父节点children数组的操作,都必须保证被插入父节点已经是“新建的唯一根节点”下的,这样才能实现不断生长的效果。以下通过递归返回父节点的方式确保,返回前是一次插入操作,这时已经判断出“插入新节点”和“未插入新节点”,根据这两种情况,递归返回值就可以判断,如果插入新节点则返回该新节点作为父节点,反之返回已存在于“唯一根节点上的”的“该节点”作为父节点。
var treeConverter = { result: null, //转化后的结果,是根节点,所有节点都是从根节点长出来的 attributeName: 'id', //节点唯一标识符 needFind: true, //是否查询节点在result中已经存在,为了优化效率 transform: function (node) { //转化递归函数,参数:一个待插入节点 if (node.parent != null) { //该节点有父节点 var newNode = this.transform(node.parent); //递归进入,返回值为一个节点,用作父节点,该父节点必然存在于result中,这点由下面的算法可以控制 if (this.needFind) { for (var i = 0; i < newNode.children.length; i++) { //查找要插入的node子节点是否在newNode这个父节点中存在 if (newNode.children[i][this.attributeName] === node[this.attributeName]) { return newNode.children[i]; //存在的话直接返回newNode父节点内的该子节点,该子节点必然存在于result中,作为返回值它将被用作上级递归的newNode,因此newNode必然存在于result中 } } } this.needFind = false; //不存在的话,关闭之后递归的循环判断,因为待插入node节点不存在于result中,故而它的子节点一定不存在于result中,不用再循环判断 delete node.parent; //删除该节点的parent属性,如果有的话 node.children = []; //因为确定是要新插入的节点,没有children:[]属性,故给该节点增加children:[]属性 newNode.children.push(node); //将该node节点push进newNode的子节点数组中 return node; //return该新插入节点,作为递归返回值给上层,用作newNode父节点,node存在于result中故newNode存在于result中 } else if (node.parent == null) { //该叶节点没有父节点,即为根节点 delete node.parent; //删除该节点的parent属性,如果有的话 if (this.result == null) { //根节点不存在 node.children = []; //给该节点增加children:[]属性 return this.result = node; //该节点赋给result,并return根节点,作为返回值它将被用作上级递归的newNode,因此newNode必然存在于result中 } else { return this.result // 直接return根节点,作为返回值它将被用作上级递归的newNode,因此newNode必然存在于result中 } } }, getSingle: function (node, attributeName) { //传入单个叶子节点,attributeName作为节点唯一标识符属性,返回单个转化结果 this.result = null; //重置根节点 this.needFind = true; //重置开启节点是否已存在判断 this.attributeName = attributeName == null ? 'id' : attributeName; //唯一标识符默认为“id” this.transform(JSON.parse(JSON.stringify(node))); //复制出一个新的节点对象作为参数,保证不改变原有数据 return this.result; //返回根节点 }, getWhole: function (nodes, attributeName) { //传入整个叶子节点数组,attributeName作为节点唯一标识符属性,返回整个转化结果 this.result = null; //重置根节点 this.attributeName = attributeName == null ? 'id' : attributeName; //唯一标识符默认为“id” nodes = JSON.parse(JSON.stringify(nodes)); //复制出一个新的节点对象作为参数,保证不改变原有数据 nodes.forEach(item => { //循环调用转化方法 this.needFind = true; //重置开启节点是否已存在判断,保证不插入重复节点 this.transform(item); }) return this.result; //返回根节点 } } var result = treeConverter.getWhole(nodes); //调用
模拟数据:
var nodes= [ { id: 2, parent: { id: 5, parent: { id: 3, parent: null } } }, { id: 1, parent: { id: 5, parent: { id: 3, parent: null } } }, { id: 4, parent: { id: 7, parent: { id: 3, parent: null } } }, { id: 14, parent: { id: 13, parent: { id: 9, parent: { id: 8, parent: { id: 7, parent: { id: 3, parent: null } } } } } }, { id: 6, parent: { id: 7, parent: { id: 3, parent: null } } }, { id: 10, parent: { id: 8, parent: { id: 7, parent: { id: 3, parent: null } } } } ]
最新文章
- windows 用默认软件打开文档
- liunx ln -s 软连接
- ehcache2拾遗之cache持久化
- php的public、protected、private三种访问控制模式的区别
- fill 函数
- locale------- linux字符集
- leetcode shttps://oj.leetcode.com/problems/surrounded-regions/
- 牛顿法与拟牛顿法,DFP法,BFGS法,L-BFGS法
- [Android] 获取WebView的页面标题(Title)-----WebChromeClient.onReceivedTitle()方法的重写
- OOP in JS - Inheritance
- 转 使用 HttpClient 4 进行文件上传
- spring持久类po或者javabean为什么常常实现序列化?
- java 对象、集合的非空判断
- VirboxLM许可管理平台,一站式软件保护解决方案
- java中读取资源文件的方法
- ABAP表抛FTP通用程序
- Java Hello World源代码notepad++版
- vivado各版本的区别
- ORB原理与源码解析
- Grapher - Change how graphs look
热门文章
- CF #323 DIV2 D题
- [Mini Program] 尺寸单位 rpx
- QueryString 地址栏参数
- tiny4412移植opencv2.4.7手记
- 【概念的辨异】—— ISO C 与 POSIX C(C standard library 与 C POSIX library)
- EOJ 1501/UVa The Blocks Problem
- 77.招聘信息管理 EXTJS 页面
- PCB 一键远程桌面+RDP文件生成
- getField();在TP5里成什么了?
- TCP排查常用命令