最近碰到的问题,有个数组,数组元素是对象,该对象的结构就如树的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
有一个数组,我们需要通过js对数组的元素进行随机排序,然后输出,这其实就是洗牌算法,首页需要从元素中随机取一个和第一元进行交换,然后依次类推,直到最后一个元素。
程序员必须知道的10大算法:快速排序算法、堆排序算法、归并排序、二分查找算法、BFPRT(线性查找算法)、DFS(深度优先搜索)、BFS(广度优先搜索)、Dijkstra算法、动态规划算法、朴素贝叶斯分类算法
使用原生js将一维数组中,包含连续的数字分成一个二维数组,这篇文章分2种情况介绍如何实现?1、过滤单个数字;2、包含单个数字。
给定一个无序的整数序列, 找最长的连续数字序列。例如:给定[100, 4, 200, 1, 3, 2],最长的连续数字序列是[1, 2, 3, 4]。此方法不会改变传入的数组,会返回一个包含最大序列的新数组。
racking.js 是一个独立的JavaScript库,实现多人同时检测人脸并将区域限定范围内的人脸标识出来,并保存为图片格式,跟踪的数据既可以是颜色,也可以是人,也就是说我们可以通过检测到某特定颜色,或者检测一个人体/脸的出现与移动,来触发JavaScript 事件。
JS常见算法题目:xiaoshuo-ss-sfff-fe 变为驼峰xiaoshuoSsSfffFe、数组去重、统计字符串中出现最多的字母、字符串反序、深拷贝、合并多个有序数组、约瑟夫环问题
这篇文章主要是针对一种最常见的非对称加密算法——RSA算法进行讲解。其实也就是对私钥和公钥产生的一种方式进行描述,RSA算法的核心就是欧拉定理,根据它我们才能得到私钥,从而保证整个通信的安全。
PageRank,网页排名,又称网页级别、Google左侧排名或佩奇排名,是一种由 根据网页之间相互的超链接计算的技术,而作为网页排名的要素之一,以Google公司创办人拉里·佩奇(Larry Page)之姓来命名。
什么是回文字符串?即字符串从前往后读和从后往前读字符顺序是一致的。例如:字符串aba,从前往后读是a-b-a;从后往前读也是a-b-a
将一个整数中的数字进行颠倒,当颠倒后的整数溢出时,返回 0 ;当尾数为0时候需要进行舍去。解法:转字符串 再转数组进行操作,看到有人用四则运算+遍历反转整数。
内容以共享、参考、研究为目的,不存在任何商业目的。其版权属原作者所有,如有侵权或违规,请与小编联系!情况属实本人将予以删除!