树是一种非散列数据结构,和非散列表一样,它对于存储需要快速查找的数据非常有用。
树是一种分层数据的抽象模型。现实生活中最常见的树的例子是家谱,或是公司的组织架构
本文将讲述一个实例,构造一棵树来实现数组和tree的相互转换,这在前端树结构中是经常遇到的。
将数组转化树结构,并将树结构转化为数组
const list= [
{ id: 1001, parentId: 0, name: 'AA' },
{ id: 1002, parentId: 1001, name: 'BB' },
{ id: 1009, parentId: 1005, name: 'II' },
{ id: 1003, parentId: 1001, name: 'CC' },
{ id: 1004, parentId: 1003, name: 'DD' },
{ id: 1005, parentId: 1003, name: 'EE' },
{ id: 1006, parentId: 1002, name: 'FF' },
{ id: 1007, parentId: 1002, name: 'GG' },
{ id: 1008, parentId: 1004, name: 'HH' },
];
数组list是无规则排序的,不过分析过后,可以看到是一个通过parentId关联的树,那么如何实现呢?
树结构是一个对象,有一个root节点,并且有一系列的方法,比如插入节点,删除节点,获取节点,获取深度等等。
节点也是一个对象,有一定的属性,而且节点的属性也可能是其他的树。
那么我们可以先构造一个节点对象Node,每个Node有id, parentId, name, childNodes属性
构造一棵树listTree,先在数组中找到根节点(parentId === 0)
再给listTree添加list数组中的元素,直到添加完毕,就得到了树结构
class Node {
constructor(options){
let { id, parentId, name } = options
this.id = id || null;
this.parentId = parentId;
this.name = name || null;
this.childNodes = []
}
getId(){
return this.id;
}
...
}
创建listTree时,初始化this.root,生成this.root(generateRoot)
由于在root上添加节点,所以增加了insertNode方法,插入时要找到root中对用的parentId
代码如下:
class listTree{
constructor(arr){
this.root = new Node(arr.find(item => item.parentId === 0))
this.generateRoot(arr)
}
generateRoot(arr){
// ...
}
getNodeById(id){
// ...
}
insertNode(node, id){
let targetNode = this.getNodeById(id)
// ...
}
// ...
}
getNodeById(id):遍历this.root,找到对应元素,这里采取横向遍历,减少计算量
insertNode实现:根据要插入节点的parentId,找到父节点,然后把要插入的节点加入到父节点数组中
generateRoot:每次向listTree树加入节点后,在目标数组中删除该元素,直到目标数组为空
代码如下:
class listTree{
constructor(arr){
this.root = new Node(arr.find(item => item.parentId === 0))
this.generateRoot(arr)
}
generateRoot(arr){
let arrRest = arr;
let self = this;
let rootIndex = arr.findIndex(item => item.parentId === 0)
arrRest.splice(rootIndex,1)
reduceArrRest()
function reduceArrRest(){
arrRest.forEach((node,index) => {
let result = self.insertNode(new Node(node),node.parentId)
if(result){
arrRest.splice(index,1)
}
})
// 有剩余的元素没有插入到树结构, 继续循环插入
if(arrRest.length > 0){
reduceArrRest()
}
}
}
getNodeById(id){
if(this.root && this.root.id === id){
return this.root
}
let targetNode = null;
compareNodeId(id,this.root.childNodes)
return targetNode;
function compareNodeId(id, NodeList){
// 在遍历下一个节点时,先判断是否已经找到targetNode
if(targetNode){
return targetNode
}
// 先遍历NodeList数组(采取的广度遍历)
for ( let node of NodeList){
if(node.id === id){
targetNode = node
break
}
}
// NodeList数组中没找到,再到NodeList每个node的child中查找
if(!targetNode){
for ( let node of NodeList){
if(node.childNodes.length>0){
compareNodeId(id,node.childNodes)
}
}
}
return targetNode
}
}
insertNode(node, id){
let targetNode = this.getNodeById(id)
if(targetNode){
targetNode.childNodes.push(node)
return true
} else {
return false
}
}
}
递归遍历树结构
class listTree{
constructor(arr){
this.root = new Node(arr.find(item => item.parentId === 0))
}
// ...
toArray(){
let list = [];
pushNode(this.root)
function pushNode(node){
let { id, parentId, name } = node;
list.push({id, parentId, name})
if(node.childNodes.length>0){
for ( let nodeItem of node.childNodes){
pushNode(nodeItem)
}
}
}
return list
}
}
以上就实现了基本的功能
function listToTree(arr){
let ListTree = new listTree(arr)
console.log(JSON.stringify(ListTree.root,null, 2))
console.log(JSON.stringify(ListTree.toArray(),null,2))
}
listToTree(list)
树结构:
{
"id": 1001,
"parentId": 0,
"name": "AA",
"childNodes": [
{
"id": 1002,
"parentId": 1001,
"name": "BB",
"childNodes": [
{
"id": 1007,
"parentId": 1002,
"name": "GG",
"childNodes": []
},
{
"id": 1006,
"parentId": 1002,
"name": "FF",
"childNodes": []
}
]
},
{
"id": 1003,
"parentId": 1001,
"name": "CC",
"childNodes": [
{
"id": 1005,
"parentId": 1003,
"name": "EE",
"childNodes": [
{
"id": 1009,
"parentId": 1005,
"name": "II",
"childNodes": []
}
]
},
{
"id": 1004,
"parentId": 1003,
"name": "DD",
"childNodes": [
{
"id": 1008,
"parentId": 1004,
"name": "HH",
"childNodes": []
}
]
}
]
}
]
}
数组:
[
{
"id": 1001,
"parentId": 0,
"name": "AA"
},
{
"id": 1002,
"parentId": 1001,
"name": "BB"
},
{
"id": 1007,
"parentId": 1002,
"name": "GG"
},
{
"id": 1006,
"parentId": 1002,
"name": "FF"
},
{
"id": 1003,
"parentId": 1001,
"name": "CC"
},
{
"id": 1005,
"parentId": 1003,
"name": "EE"
},
{
"id": 1009,
"parentId": 1005,
"name": "II"
},
{
"id": 1004,
"parentId": 1003,
"name": "DD"
},
{
"id": 1008,
"parentId": 1004,
"name": "HH"
}
]
总结:树结构的形式有很多,不过还是会归结到树节点,树方法上。
文章浏览阅读445次,点赞7次,收藏7次。交通信号控制对于通过调节红绿灯相位来优化道路网络的效率至关重要。现有的研究主要集中在基于启发式或强化学习(RL)的方法上,这些方法往往缺乏在不同交通场景中的可转移性,并且具有较差的可解释性。本文介绍了一种利用大型语言模型(LLM)执行交通信号控制任务的新方法LLMLight。通过利用LLM令人印象深刻的泛化和零样本推理能力,LLMLight执行了一个人性化的决策过程,以实现高效的交通管理。具体来说,该框架首先将任务描述、当前交通状况和先验知识组合到提示中。_llmlight: large language models as traffic signal controlagents 译文
文章浏览阅读508次,点赞8次,收藏7次。GNU工程的目标,是构建一个包括内核在内的操作系统生态。GNU工程也在开发一个操作系统内核,叫hurd,但是开发不是很顺利,后来Linus Torvalds编写一个类似Unix的内核(Linux) ,这样,整个操作系统的组件就齐全了,GNU/Linux操作系统就发布了。GNU工程一个巨大的工程:开发一整套操作系统,包括内核、编译器、调试器、开发工具、应用软件等,绝非一个人或一个团队所能完成的,因此在1985年10月,成立了自由软件基金会,它初期用来给GNU募集资金。GNU与GNU Linux。_linux和gnu
文章浏览阅读8.7k次,点赞2次,收藏6次。visio studio code port` is ignored with the 'dlv-dap'解决方法:在配置文件中加上, "debugAdapter":"legacy",参考博文:https://gitee.com/snow2zhou/vscode-go/blob/master/docs/dlv-dap.md_couldn't start dlv dap
文章浏览阅读4.1k次,点赞5次,收藏10次。转载声明:商业转载请联系作者获得授权,非商业转载请注明出处.原文来自 呆萌钟【JavaSe必知必会】27-二维数组定义详解 二维数组概述二维数组其实就是一个元素为一维数组的数组。二维数组定义格式格式1数据类型[][] 变量名 = new 数据类型[m][n]; m表示这个二维数组有多少个一维数组 n表示每一个一维数组的元素个数 举例: int[][] arr =..._java二维数组的定义
文章浏览阅读643次。这是武散人著《自拍教程》(自动化测试Python教程)系列第60篇文章。重要提醒:本案例涉及220v危险电压上电下电测试,存在安全风险,请切勿随意尝试!!!案例故事 很多移动终端都不带电池,都是直接电源插头供电,比如Android电视机(220v),小米小爱同学智能音箱(220v转5v的电源转换器),智能后视镜(12v)等智能终端设备,Android家庭信息机平板(5v),还有电饭煲,微波炉,空调..._python实现继电器对android手机进行上下电
文章浏览阅读8.5k次,点赞5次,收藏9次。分享几个强大的网站:1、电子世家电子世家汇总了大量电子、嵌入式等网站、论坛。网址如下:http://www.dianzishijia.com/2、极客导航极客导航汇总了大量的技术、产品、设计、运营、职能等方面的内容。网址如下:https://www.gogeeks.cn/nav3、在线工具-程序员的工具箱这个网站有大量的在线工具可以使用,工具包含开发类、站长类、极客类、..._电子世家
文章浏览阅读1.7w次,点赞18次,收藏41次。1.简单来说,jar包是对写好的类进行了打包。我们可以通过将jar包放到lib目录下来使用这些jar包中的类、属性和方法。2.专业解释,JAR文件是Java Archive File-java档案文件的简称,是与平台无关的文件格式,基于zip文件格式将许多文件合成一个压缩文件.jar,区别是比zip多了一个包含了一个 META-INF/MANIFEST.MF 文件,这个文件是在生成 JAR 文件的时候自动创建的。3.作用JAR 文件不仅用于压缩和发布,而且还用于部署和封装库、组件和插件程序,并可_java中jar包到底是干嘛的
文章浏览阅读9.8k次。如何查找指定文件被删除的记录?首先要记录到个人最好是在域环境内;在文件服务器运行输入gpedit.msc2.依次选择“计算机配置”—“Windows设置”—“安全设置”—“高级审核策略配置”—“系统审核策略”—“对象访问”—“文件审核系统”双击“审核文件系统”,勾选“成功”前往需要审核的文件夹,右键选择“属性”—“安全”—“高级”—“审核”—“添加”一般来说这里选择domain..._服务器文件被删怎么查记录
文章浏览阅读1.2w次,点赞3次,收藏7次。其实很多人应该早知道了,但是我今天才知道其实这个功能很实用,就像图层一样用过cg软件之类的人应该清楚当场景物体很多的时候需要有些物体可见调整视觉效果,但是不希望它们被选中影响其他物体所以希望一些物体在不同的“层”这个功能也正是unity中的层来控制的_unity hierarchy view 固定某个场景
文章浏览阅读1.3w次,点赞15次,收藏125次。S.G. Narasimhan and S.K. Nayar, 多幅图像(同一场景不同时间、天气)去雾 主页NASA, Retinex理论增强,主页。 Ana Belén Petro总结了NASA的Retinex理论,源代码,不过不是matlab版本的。Kopf,Deep Photo: Model-Based Photograph Enhancement and Viewing,3D场景去雾,没..._图像去雾免费代码网站
文章浏览阅读1.1w次,点赞6次,收藏33次。使用TensorFlow模块时,弹出错误Your CPU supports instructions that this TensorFlow binary was not compiled to use: AVX AVX2原因是下载TensorFlow的版本不支持cpu的AVX2编译。可能是因为安装时使用的pip install tensorflow ,这样默认会下载X86_64的SIMD版本。有两种解决办法:1.忽略这个警告,不看它! 1 2 3 4_your cpu supports instructions that this tensorflow binary was not compiled
文章浏览阅读4.1w次,点赞7次,收藏26次。ipv4和6都没访问权限怎么办?其实这个问题很大一部分原因是因为我们的路由器设置出现了问题,我们只需要进入路由器官网重新设置一下就可以搞定了,今天我就来为各位老铁介绍一下,ipv4连接无internet访问权限解决方法吧。1、打开控制面板2、打开网络和Internet3、在网络和Internet页面中,选择网络和共享中心4、选择右边的本地连接,进入到本地连接后,点击查看详情。5、在这里我们查看一下..._ipv4无网络访问权限怎么解决