JavaScript将一维数组平面化为树 [英] JavaScript Flat one dimensional array to tree
本文介绍了JavaScript将一维数组平面化为树的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我将以下对象堆叠在一维数组中：
I have following objects stacked in a 1D array:
var colors = ["#FF0000", "#00FF00", "#0000FF", "#FF00FF", "#00FFFF"];
var array1D = [
{ level: 1, x: 0, y: 0 },
{ level: 1, x: 0, y: 1 },
{ level: 1, x: 1, y: 0 },
{ level: 4, x: 8, y: 8 },
{ level: 4, x: 8, y: 9 },
{ level: 5, x: 18, y: 16 },
{ level: 5, x: 18, y: 17 },
{ level: 5, x: 19, y: 16 },
{ level: 5, x: 19, y: 17 },
{ level: 5, x: 18, y: 18 },
{ level: 5, x: 18, y: 19 },
{ level: 5, x: 19, y: 18 },
{ level: 5, x: 19, y: 19 },
{ level: 4, x: 8, y: 10 },
{ level: 4, x: 8, y: 11 },
{ level: 5, x: 18, y: 20 },
{ level: 5, x: 18, y: 21 },
{ level: 5, x: 19, y: 20 },
{ level: 5, x: 19, y: 21 },
{ level: 4, x: 9, y: 11 },
{ level: 5, x: 20, y: 16 },
{ level: 5, x: 20, y: 17 },
{ level: 5, x: 21, y: 16 },
{ level: 5, x: 21, y: 17 },
{ level: 5, x: 20, y: 18 },
{ level: 5, x: 20, y: 19 },
{ level: 5, x: 21, y: 18 },
{ level: 5, x: 21, y: 19 },
{ level: 4, x: 11, y: 8 },
{ level: 5, x: 22, y: 18 },
{ level: 5, x: 22, y: 19 },
{ level: 5, x: 23, y: 18 },
{ level: 5, x: 23, y: 19 },
{ level: 5, x: 20, y: 20 },
{ level: 5, x: 20, y: 21 },
{ level: 5, x: 21, y: 20 },
{ level: 5, x: 21, y: 21 },
{ level: 4, x: 10, y: 11 },
{ level: 5, x: 22, y: 20 },
{ level: 5, x: 22, y: 21 },
{ level: 5, x: 23, y: 20 },
{ level: 5, x: 23, y: 21 },
{ level: 4, x: 11, y: 11 },
{ level: 2, x: 2, y: 3 },
{ level: 2, x: 3, y: 2 },
{ level: 2, x: 3, y: 3 }
];
它基本上是四叉树结构，因此不需要验证是否可以从
It's basically a quadtree structure, so you don't need to validate if you can build a tree from it or not.
在视觉上看起来像以下插图：
Visually it looks like following illustration:
viz的代码非常简单：
The code for viz is very simple:
quad.sort(function(a_, b_){ return a_.level - b_.level; })
var canvas = document.createElement("canvas");
document.body.appendChild(canvas)
canvas.width = 512;
canvas.height = 512;
var ctx = canvas.getContext("2d");
quad.forEach(function(node_){
ctx.fillStyle = colors[node_.level - 1];
var w = 256;
for(var i = 0; i < node_.level; i++) { w /= 2; }
var x = 256;
for(var i = 0; i < node_.level; i++) { x /= 2; }
x *= node_.x;
var y = 256;
for(var i = 0; i < node_.level; i++) { y /= 2; }
y *= node_.y;
ctx.fillRect(x + 1, y + 1, w - 2, w - 2);
});
任务是以最快的方式在这些节点上构建树，以获得类似
The task is to build a tree out of these nodes in a fastest way as possible to get something like this:
var result = [
{id: "0.1", children: null },
{id: "0.2", children: null },
{id: "0.3", children: null },
{id: "0.4", children: [
{ id: "0.1.1", children: [
...
] },
{ id: "0.1.2", children: [] },
{ id: "0.1.3", children: [] },
{ id: "0.1.4", children: [] },
] }
];
更新：
ID由此逻辑-左上为1，右上为2，左下为3，右下为4。
ID's are generating by this logic—top-left is 1, top-right is 2, bottom-left is 3, bottom-right is 4.
因此，即在底部是4.3，右边的邻居是4.4。第一个洋红色正方形为4.1.1。
So, i.e. left green square at the bottom is 4.3, its neighbour to the right is 4.4. The first magenta square is 4.1.1.
在初始一维数组级别中，x和y值负责定位和缩放分区，因此您始终可以获取其级别和父母的价值观。
In initial 1D array level, x and y values are in charge of positioning and scaling partitions, so you could always get its level and parents by these values.
我需要使用这些级别，x和y值将一维数组转换为二维树。
All I need to convert 1D array to 2D tree by using these level, x and y values.
推荐答案
我试图理解并构建它，我有一个可行的解决方案，但要求级别不要跳跃（即连续），因此在您的示例中，没有第3级，是否有效？我创建了一个略微简化的示例，以说明如何在连续级别上工作：
I am trying to understand and to build it, I have a solution that seems to work, but requires the levels not to "jump" (i.e. be continuous), so in your example, there is no level 3, is that valid? I created a slightly simplified example to show how this can work for continuous levels:
const colors = ["#FF0000", "#00FF00", "#0000FF", "#FF00FF", "#00FFFF"];
const array1D = [
{ level: 1, x: 0, y: 0 },
{ level: 1, x: 16, y: 0 },
{ level: 1, x: 0, y: 16 },
//*
//*
{ level: 3, x: 16, y: 16 },
{ level: 3, x: 20, y: 16 },
{ level: 3, x: 16, y: 20 },
{ level: 3, x: 20, y: 20 },
//*/
{ level: 2, x: 24, y: 16 },
{ level: 2, x: 16, y: 24 },
{ level: 2, x: 24, y: 24 }
//*
];
const arrayNested = createdNestedQuadTree(array1D);
console.log(arrayNested);
function createdNestedQuadTree(input, level) {
const nestedOutput = [];
//don't mutate input, call with shallow copy:
innerRecursive([...input], nestedOutput);
function innerRecursive(currArr, parentArr, level){
const currentLevel = level || 1;
const currentChildren = [];
const pointOfNesting = {};
for (let i of [1,2,3,4]){
const item = currArr[i-1];
//console.log(currentLevel, i, item);
if (currentLevel == item.level){
item.id = `${currentLevel}.${i}`;
item.children = null;
parentArr.push(item);
//console.log('output', nestedOutput);
}
else {
pointOfNesting.id = `${currentLevel}.${i}`;
pointOfNesting.children = [];
parentArr.push(pointOfNesting);
//console.log('parent', parentArr);
let child = currArr[i-1];
let j = i - 1;
let position = 1;
//console.log(child);
while (child && child.level > currentLevel){
//console.log('child', child);
currentChildren.push(child);
j +=1;
child = currArr[j];
}
currArr.splice(i-1, (j - (i-1) ) );
currArr.splice(i-1, 0, pointOfNesting);
//console.log('curr', currArr);
//console.log('parent', parentArr);
//console.log('children', currentChildren);
//console.log('output', nestedOutput);
innerRecursive([...currentChildren], pointOfNesting.children, currentLevel + 1)
}
}
}
return nestedOutput;
}
.as-console-wrapper { max-height: 100% !important; top: 0; }
输出：
[
{
"level": 1,
"x": 0,
"y": 0,
"id": "1.1",
"children": null
},
{
"level": 1,
"x": 16,
"y": 0,
"id": "1.2",
"children": null
},
{
"level": 1,
"x": 0,
"y": 16,
"id": "1.3",
"children": null
},
{
"id": "1.4",
"children": [
{
"id": "2.1",
"children": [
{
"level": 3,
"x": 16,
"y": 16,
"id": "3.1",
"children": null
},
{
"level": 3,
"x": 20,
"y": 16,
"id": "3.2",
"children": null
},
{
"level": 3,
"x": 16,
"y": 20,
"id": "3.3",
"children": null
},
{
"level": 3,
"x": 20,
"y": 20,
"id": "3.4",
"children": null
}
]
},
{
"level": 2,
"x": 24,
"y": 16,
"id": "2.2",
"children": null
},
{
"level": 2,
"x": 16,
"y": 24,
"id": "2.3",
"children": null
},
{
"level": 2,
"x": 24,
"y": 24,
"id": "2.4",
"children": null
}
]
}
]
对应于此四叉树（32 x 32）：
Corresponding to this quadtree (32 x 32):
这是一个更复杂的示例（但又是连续的）：
Here is a more complex example (but again continuous):
const colors = ["#FF0000", "#00FF00", "#0000FF", "#FF00FF", "#00FFFF"];
const array1D = [
{ level: 1, x: 0, y: 0 },
{ level: 1, x: 16, y: 0 },
{ level: 1, x: 0, y: 16 },
//* <level 2>
//* <level 3>
{ level: 3, x: 16, y: 16 },
//* <level 4>
{ level: 4, x: 20, y: 16 },
//* <level 5>
{ level: 5, x: 22, y: 16 },
{ level: 5, x: 23, y: 16 },
{ level: 5, x: 22, y: 17 },
{ level: 5, x: 23, y: 17 },
//*/ </level 5>
{ level: 4, x: 20, y: 18 },
{ level: 4, x: 22, y: 18 },
//*/ </level 4>
{ level: 3, x: 16, y: 20 },
{ level: 3, x: 20, y: 20 },
//*/ </level 3>
{ level: 2, x: 24, y: 16 },
{ level: 2, x: 16, y: 24 },
{ level: 2, x: 24, y: 24 }
//* </level 2>
];
const arrayNested = createdNestedQuadTree(array1D);
console.log(arrayNested);
function createdNestedQuadTree(input, level) {
const nestedOutput = [];
//don't mutate input, call with shallow copy:
innerRecursive([...input], nestedOutput);
function innerRecursive(currArr, parentArr, level){
const currentLevel = level || 1;
const currentChildren = [];
const pointOfNesting = {};
for (let i of [1,2,3,4]){
const item = currArr[i-1];
//console.log(currentLevel, i, item);
if (currentLevel == item.level){
item.id = `${currentLevel}.${i}`;
item.children = null;
parentArr.push(item);
//console.log('output', nestedOutput);
}
else {
pointOfNesting.id = `${currentLevel}.${i}`;
pointOfNesting.children = [];
parentArr.push(pointOfNesting);
//console.log('parent', parentArr);
let child = currArr[i-1];
let j = i - 1;
let position = 1;
//console.log(child);
while (child && child.level > currentLevel){
//console.log('child', child);
currentChildren.push(child);
j +=1;
child = currArr[j];
}
currArr.splice(i-1, (j - (i-1) ) );
currArr.splice(i-1, 0, pointOfNesting);
innerRecursive([...currentChildren], pointOfNesting.children, currentLevel + 1)
}
}
}
return nestedOutput;
}
.as-console-wrapper { max-height: 100% !important; top: 0; }
输出：
[
{
"level": 1,
"x": 0,
"y": 0,
"id": "1.1",
"children": null
},
{
"level": 1,
"x": 16,
"y": 0,
"id": "1.2",
"children": null
},
{
"level": 1,
"x": 0,
"y": 16,
"id": "1.3",
"children": null
},
{
"id": "1.4",
"children": [
{
"id": "2.1",
"children": [
{
"level": 3,
"x": 16,
"y": 16,
"id": "3.1",
"children": null
},
{
"id": "3.2",
"children": [
{
"level": 4,
"x": 20,
"y": 16,
"id": "4.1",
"children": null
},
{
"id": "4.2",
"children": [
{
"level": 5,
"x": 22,
"y": 16,
"id": "5.1",
"children": null
},
{
"level": 5,
"x": 23,
"y": 16,
"id": "5.2",
"children": null
},
{
"level": 5,
"x": 22,
"y": 17,
"id": "5.3",
"children": null
},
{
"level": 5,
"x": 23,
"y": 17,
"id": "5.4",
"children": null
}
]
},
{
"level": 4,
"x": 20,
"y": 18,
"id": "4.3",
"children": null
},
{
"level": 4,
"x": 22,
"y": 18,
"id": "4.4",
"children": null
}
]
},
{
"level": 3,
"x": 16,
"y": 20,
"id": "3.3",
"children": null
},
{
"level": 3,
"x": 20,
"y": 20,
"id": "3.4",
"children": null
}
]
},
{
"level": 2,
"x": 24,
"y": 16,
"id": "2.2",
"children": null
},
{
"level": 2,
"x": 16,
"y": 24,
"id": "2.3",
"children": null
},
{
"level": 2,
"x": 24,
"y": 24,
"id": "2.4",
"children": null
}
]
}
]
对应于此四叉树（32 x 32）：
Corresponding to this quadtree (32 x 32):
这篇关于JavaScript将一维数组平面化为树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
