数组对象转换成树结构
时间: 2024-09-26 08:16:57 浏览: 10
将数组对象转换成树形结构通常是在数据处理中遇到的问题,特别是当数据有层级关系时。假设我们有一个二维数组,每个元素代表一个节点,包含父节点ID(或其他标识其所属上级的属性),我们可以按照递归的方式构建树:
例如,假设有这样的数组:
```javascript
[
{id: 1, pid: null}, // 根节点
{id: 2, pid: 1},
{id: 3, pid: 1},
{id: 4, pid: 2},
{id: 5, pid: 3}
]
```
可以先创建一个空的对象`tree`,然后遍历数组,对于每个节点,如果它的父ID已存在于`tree`中,就在该节点下添加当前节点;如果不存在,则表示这是根节点,直接将其添加到`tree`。
函数实现可能如下:
```javascript
function arrayToTree(arr) {
const tree = {};
arr.forEach(node => {
if (node.pid in tree) {
tree[node.pid].children.push(node);
} else {
tree[node.id] = { id: node.id, children: [node] };
}
});
return tree;
}
// 转换后的树状结构
const result = arrayToTree([...]); // 传入上述示例数组
```
相关问题
javaScript将数组转换成树
可以使用递归来将数组转换为树形结构。假设数组中每个元素都是一个具有 `id` 和 `parentId` 属性的对象,其中 `id` 表示该节点的唯一标识符,`parentId` 表示该节点的父节点的标识符,根节点的 `parentId` 为 `null`。
以下是一个示例函数来将数组转换为树形结构:
```javascript
function arrayToTree(arr) {
const map = {};
const roots = [];
// First pass: create a map of nodes keyed by their id
arr.forEach(node => {
map[node.id] = node;
node.children = [];
});
// Second pass: link each node to its parent
arr.forEach(node => {
const parent = map[node.parentId];
if (parent) {
parent.children.push(node);
} else {
roots.push(node);
}
});
return roots;
}
```
使用示例:
```javascript
const arr = [
{id: 1, parentId: null},
{id: 2, parentId: 1},
{id: 3, parentId: 1},
{id: 4, parentId: 2},
{id: 5, parentId: 2},
{id: 6, parentId: 3},
{id: 7, parentId: 3},
];
const tree = arrayToTree(arr);
console.log(tree);
```
输出结果:
```
[
{
"id": 1,
"parentId": null,
"children": [
{
"id": 2,
"parentId": 1,
"children": [
{"id": 4, "parentId": 2, "children": []},
{"id": 5, "parentId": 2, "children": []}
]
},
{
"id": 3,
"parentId": 1,
"children": [
{"id": 6, "parentId": 3, "children": []},
{"id": 7, "parentId": 3, "children": []}
]
}
]
}
]
```
这个函数的时间复杂度是 $O(n)$,其中 $n$ 是数组的长度。
写一个把扁平数组转成树结构的函数(可认为只存在一个根节点)
将扁平数组转换成树结构的函数通常需要一个额外的参数,比如每个节点的id和其父节点的id。下面是一个简单的示例,这个函数将根据扁平数组中的数据,递归地构建出树形结构:
```javascript
// 定义树节点构造函数
function TreeNode(id, children = []) {
this.id = id;
this.children = children;
}
// 将扁平数组转成树结构的函数
function buildTree(flatArray, idKey, parentIdKey, rootId) {
// 将数组转换为以 id 为键的对象,方便查找
const map = {};
for (const item of flatArray) {
map[item[idKey]] = new TreeNode(item[idKey]);
}
// 构建树
for (const item of flatArray) {
const node = map[item[idKey]];
// 如果存在父节点,就将其子节点添加到父节点的 children 数组中
if (item[parentIdKey] != null) {
if (!map[item[parentIdKey]]) {
map[item[parentIdKey]] = new TreeNode(item[parentIdKey]);
}
map[item[parentIdKey]].children.push(node);
}
}
// 返回根节点的子节点
return map[rootId].children;
}
// 示例数组
const flatArray = [
{ id: 1, parentId: null },
{ id: 2, parentId: 1 },
{ id: 3, parentId: 1 },
{ id: 4, parentId: 2 },
{ id: 5, parentId: 3 },
];
// 调用函数,idKey 和 parentIdKey 分别是'key'和'parentKey'
const tree = buildTree(flatArray, 'id', 'parentId', 1);
// 打印树结构
console.log(tree);
```
这段代码中,`buildTree`函数接受四个参数:扁平数组`flatArray`,节点id的键`idKey`,节点父id的键`parentIdKey`和根节点的id`rootId`。函数内部首先将扁平数组中的每个元素映射为一个树节点对象,并将其存储在一个以id为键的对象中以便快速访问。然后,通过遍历数组构建树形结构,最终返回根节点的子节点。