关闭

js多叉树结构的数据,parent表示法转成children表示法

时间: 2018-11-12阅读: 2303标签: 算法

最近碰到的问题,有个数组,数组元素是对象,该对象的结构就如树的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
                }
            }
        }
    }
]


原文来源:https://www.cnblogs.com/LQ996/archive/2018/11/11/9942545.html


站长推荐

1.云服务推荐: 国内主流云服务商,各类云产品的最新活动,优惠券领取。地址:阿里云腾讯云华为云

链接: http://www.fly63.com/article/detial/1323

算法工程师的危机

AI概念在2015年起就红得发紫,不论是送外卖,搞团购,卖车,或是推荐莆田医院的,是个公司都会标榜自己是搞人工智能的。在21世纪的第二个十年,计算机专业相关的学生不说自己是搞AI算法的,同学聚会都抬不起头,相亲机会都变少了

PHP 迁移 Mcrypt 至 OpenSSL 加密算法详解

对称加解密算法中,当前最为安全的是 AES 加密算法(以前应该是是 DES 加密算法),PHP 提供了两个可以用于 AES 加密算法的函数簇:Mcrypt 和 OpenSSL。其中 Mcrypt 在 PHP 7.1.0 中被 Deprecated,在 PHP 7.2.0 中被移除,所以即可起你应该使用 OpenSSL 来实现 AES 的数据加解密。

轻松搞定时间复杂度

通过学习本文,你可以掌握以下三点内容:为什么需要时间复杂度;时间复杂度怎么表示;怎样分析一段代码的时间复杂度,相信认真阅读过本文,面对一些常见的算法复杂度分析,一定会游刃有余

Js算法:计算两数之和

给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和

Js常用的算法教程

Js常用的算法教程 深度广度、冒泡选择、防抖节流等,函数在调用倒计时n时间内没有重复调用,则执行函数,不然重新倒计时

Js找出数组中出现次数最多的元素

给定一个数组,找出数组中出现次数最多的元素。给定数组 nums = [3,1,2,1,3,4,3,5,3,6,3], 函数应该返回: 次数最多的元素为:3, 次数为:5

一道有意思的面试算法题

给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。这道题第一眼看过去,思路挺简单的,我们只需要维护一个对象来记录每一个元素出现的次数,使用元素的值作为key,元素出现的次数作为value。

现在算法是新锐前端框架成功的重要因素

随着前端MVVM的流行,小型框架现在越来越难存活了!react, angular等打着大公司旗号的框架占了半壁江山,而avalon以其良好兼容性在国内份额不断上升。前端也与后端一样,遵循马太效应,强者愈强,弱者愈弱。最后只剩下两种框架

js实现链表_javascript中的链表结构

很多编程语言中数组的长度是固定的,就是定义数组的时候需要定义数组的长度,所以当数组已经被数据填满的时候,需要再加入新的元素就很困难。只能说在部分变成语言中会有这种情况,在javascript中和php中数组的长度是可以任意增加的。avascript中有一个很方便的方法splice()方法很方便的就可以添加或删除元素。

JavaScript数据结构与算法-String

给定一个字符串,你需要反转字符串中每个单词的字符顺序,同时仍保留空格和单词的初始顺序。主要就是用到了数组的 split 、 reverse 、 join 、 map 方法,原理:就是把字符串变成数组

点击更多...

内容以共享、参考、研究为目的,不存在任何商业目的。其版权属原作者所有,如有侵权或违规,请与小编联系!情况属实本人将予以删除!