반응형
javascript에서 평면 배열에서 트리 배열 만들기
나중에 트리를 구축하기 위해 javascript로 처리해야 하는 복잡한 json 파일이 있습니다.json의 모든 엔트리는 : id : id : unique id, parentId : 부모 노드의 ID (노드가 트리의 루트인 경우 0)레벨 : 트리의 깊이 레벨을 가집니다.
json 데이터가 이미 "순서 지정"되었습니다.즉, 엔트리는 그 위에 부모 노드 또는 형제 노드가 있고 그 아래에 자녀 노드 또는 형제 노드가 있습니다.
입력:
{
"People": [
{
"id": "12",
"parentId": "0",
"text": "Man",
"level": "1",
"children": null
},
{
"id": "6",
"parentId": "12",
"text": "Boy",
"level": "2",
"children": null
},
{
"id": "7",
"parentId": "12",
"text": "Other",
"level": "2",
"children": null
},
{
"id": "9",
"parentId": "0",
"text": "Woman",
"level": "1",
"children": null
},
{
"id": "11",
"parentId": "9",
"text": "Girl",
"level": "2",
"children": null
}
],
"Animals": [
{
"id": "5",
"parentId": "0",
"text": "Dog",
"level": "1",
"children": null
},
{
"id": "8",
"parentId": "5",
"text": "Puppy",
"level": "2",
"children": null
},
{
"id": "10",
"parentId": "13",
"text": "Cat",
"level": "1",
"children": null
},
{
"id": "14",
"parentId": "13",
"text": "Kitten",
"level": "2",
"children": null
},
]
}
예상되는 출력:
{
"People": [
{
"id": "12",
"parentId": "0",
"text": "Man",
"level": "1",
"children": [
{
"id": "6",
"parentId": "12",
"text": "Boy",
"level": "2",
"children": null
},
{
"id": "7",
"parentId": "12",
"text": "Other",
"level": "2",
"children": null
}
]
},
{
"id": "9",
"parentId": "0",
"text": "Woman",
"level": "1",
"children":
{
"id": "11",
"parentId": "9",
"text": "Girl",
"level": "2",
"children": null
}
}
],
"Animals": [
{
"id": "5",
"parentId": "0",
"text": "Dog",
"level": "1",
"children":
{
"id": "8",
"parentId": "5",
"text": "Puppy",
"level": "2",
"children": null
}
},
{
"id": "10",
"parentId": "13",
"text": "Cat",
"level": "1",
"children":
{
"id": "14",
"parentId": "13",
"text": "Kitten",
"level": "2",
"children": null
}
}
]
}
지도 검색을 사용하면 효율적인 솔루션이 있습니다.부모가 항상 자식보다 앞서 간다면 두 가지 일을 합칠 수 있다.여러 루트를 지원합니다.매달린 가지에 오류가 발생하지만 이를 무시하도록 수정할 수 있습니다.서드파티 라이브러리는 필요 없습니다.제가 아는 한 그게 가장 빠른 해결책입니다.
function list_to_tree(list) {
var map = {}, node, roots = [], i;
for (i = 0; i < list.length; i += 1) {
map[list[i].id] = i; // initialize the map
list[i].children = []; // initialize the children
}
for (i = 0; i < list.length; i += 1) {
node = list[i];
if (node.parentId !== "0") {
// if you have dangling branches check that map[node.parentId] exists
list[map[node.parentId]].children.push(node);
} else {
roots.push(node);
}
}
return roots;
}
var entries = [{
"id": "12",
"parentId": "0",
"text": "Man",
"level": "1",
"children": null
},
{
"id": "6",
"parentId": "12",
"text": "Boy",
"level": "2",
"children": null
},
{
"id": "7",
"parentId": "12",
"text": "Other",
"level": "2",
"children": null
},
{
"id": "9",
"parentId": "0",
"text": "Woman",
"level": "1",
"children": null
},
{
"id": "11",
"parentId": "9",
"text": "Girl",
"level": "2",
"children": null
}
];
console.log(list_to_tree(entries));복잡도 이론에 관심이 있다면 이 해법은 δ(n log(n))입니다.재귀 필터 솔루션은 대규모 데이터 세트에 문제가 될 수 있는 δ(n^2)입니다.
(Bonus1: 노드가 주문되거나 주문되지 않을 수 있습니다.)
(보너스2: 서드파티 라이브러리는 불필요, 플레인 JS )
(BONS3: 사용자 "Elias Rabl"은 이것이 가장 퍼포먼스 높은 솔루션이라고 말합니다.다음 답변 참조).
여기 있습니다.
const createDataTree = dataset => {
const hashTable = Object.create(null);
dataset.forEach(aData => hashTable[aData.ID] = {...aData, childNodes: []});
const dataTree = [];
dataset.forEach(aData => {
if(aData.parentID) hashTable[aData.parentID].childNodes.push(hashTable[aData.ID])
else dataTree.push(hashTable[aData.ID])
});
return dataTree;
};
다음은 테스트입니다.솔루션의 구조를 이해하는 데 도움이 될 수 있습니다.
it('creates a correct shape of dataTree', () => {
const dataSet = [{
"ID": 1,
"Phone": "(403) 125-2552",
"City": "Coevorden",
"Name": "Grady"
}, {
"ID": 2,
"parentID": 1,
"Phone": "(979) 486-1932",
"City": "Chełm",
"Name": "Scarlet"
}];
const expectedDataTree = [{
"ID": 1,
"Phone": "(403) 125-2552",
"City": "Coevorden",
"Name": "Grady",
childNodes: [{
"ID": 2,
"parentID": 1,
"Phone": "(979) 486-1932",
"City": "Chełm",
"Name": "Scarlet",
childNodes : []
}]
}];
expect(createDataTree(dataSet)).toEqual(expectedDataTree);
});
@Sander에서 설명한 바와 같이 @Halcyon의 답변은 사전 정렬된 배열을 상정하고 있지만, 다음은 그렇지 않습니다(단, underscore.js를 로드했다고 가정합니다만, 바닐라 Javascript로 기술할 수 있습니다).
코드
// Example usage
var arr = [
{'id':1 ,'parentid' : 0},
{'id':2 ,'parentid' : 1},
{'id':3 ,'parentid' : 1},
{'id':4 ,'parentid' : 2},
{'id':5 ,'parentid' : 0},
{'id':6 ,'parentid' : 0},
{'id':7 ,'parentid' : 4}
];
unflatten = function( array, parent, tree ){
tree = typeof tree !== 'undefined' ? tree : [];
parent = typeof parent !== 'undefined' ? parent : { id: 0 };
var children = _.filter( array, function(child){ return child.parentid == parent.id; });
if( !_.isEmpty( children ) ){
if( parent.id == 0 ){
tree = children;
}else{
parent['children'] = children
}
_.each( children, function( child ){ unflatten( array, child ) } );
}
return tree;
}
tree = unflatten( arr );
document.body.innerHTML = "<pre>" + (JSON.stringify(tree, null, " "))<script src="https://cdnjs.cloudflare.com/ajax/libs/underscore.js/1.9.1/underscore-min.js"></script>요구 사항들
속성 'id'와 'parentid'는 각각 ID와 부모 ID를 나타내는 것으로 가정합니다.부모 ID가 0인 요소가 있어야 합니다.그렇지 않으면 빈 어레이가 반환됩니다.고립된 요소와 그 후손이 '잃어버린' 상태입니다.
이 ES6 어프로치를 사용합니다.매력적으로 작용하다
// Data Set
// One top level comment
const comments = [{
id: 1,
parent_id: null
}, {
id: 2,
parent_id: 1
}, {
id: 3,
parent_id: 1
}, {
id: 4,
parent_id: 2
}, {
id: 5,
parent_id: 4
}];
const nest = (items, id = null, link = 'parent_id') =>
items
.filter(item => item[link] === id)
.map(item => ({ ...item, children: nest(items, item.id) }));
console.log(
nest(comments)
)같은 문제가 있었습니다만, 데이터가 정렬되어 있는지 아닌지는 확신할 수 없었습니다.서드파티 라이브러리를 사용할 수 없기 때문에 이것은 바닐라 Js입니다.입력 데이터는 @Stephen의 예에서 가져올 수 있습니다.
var arr = [
{'id':1 ,'parentid' : 0},
{'id':4 ,'parentid' : 2},
{'id':3 ,'parentid' : 1},
{'id':5 ,'parentid' : 0},
{'id':6 ,'parentid' : 0},
{'id':2 ,'parentid' : 1},
{'id':7 ,'parentid' : 4},
{'id':8 ,'parentid' : 1}
];
function unflatten(arr) {
var tree = [],
mappedArr = {},
arrElem,
mappedElem;
// First map the nodes of the array to an object -> create a hash table.
for(var i = 0, len = arr.length; i < len; i++) {
arrElem = arr[i];
mappedArr[arrElem.id] = arrElem;
mappedArr[arrElem.id]['children'] = [];
}
for (var id in mappedArr) {
if (mappedArr.hasOwnProperty(id)) {
mappedElem = mappedArr[id];
// If the element is not at the root level, add it to its parent array of children.
if (mappedElem.parentid) {
mappedArr[mappedElem['parentid']]['children'].push(mappedElem);
}
// If the element is at the root level, add it to first level elements array.
else {
tree.push(mappedElem);
}
}
}
return tree;
}
var tree = unflatten(arr);
document.body.innerHTML = "<pre>" + (JSON.stringify(tree, null, " "))JS 바이올린
보다 심플한 함수 리스트 투 트리 라이트
npm install list-to-tree-lite
listToTree(list)
출처:
function listToTree(data, options) {
options = options || {};
var ID_KEY = options.idKey || 'id';
var PARENT_KEY = options.parentKey || 'parent';
var CHILDREN_KEY = options.childrenKey || 'children';
var tree = [],
childrenOf = {};
var item, id, parentId;
for (var i = 0, length = data.length; i < length; i++) {
item = data[i];
id = item[ID_KEY];
parentId = item[PARENT_KEY] || 0;
// every item may have children
childrenOf[id] = childrenOf[id] || [];
// init its children
item[CHILDREN_KEY] = childrenOf[id];
if (parentId != 0) {
// init its parent's children object
childrenOf[parentId] = childrenOf[parentId] || [];
// push it into its parent's children object
childrenOf[parentId].push(item);
} else {
tree.push(item);
}
};
return tree;
}
이 문제는 다음 2개의 라인 코딩만으로 해결할 수 있습니다.
_(flatArray).forEach(f=>
{f.nodes=_(flatArray).filter(g=>g.parentId==f.id).value();});
var resultArray=_(flatArray).filter(f=>f.parentId==null).value();
온라인 테스트(생성된 트리는 브라우저 콘솔 참조)
요건:
1- Lodash 4(C#의 Linq와 같이 오브젝트 및 컬렉션을 조작하기 위한 Javascript 라이브러리 =>)를 설치합니다.
2- 다음과 같은 플랫 어레이:
var flatArray=
[{
id:1,parentId:null,text:"parent1",nodes:[]
}
,{
id:2,parentId:null,text:"parent2",nodes:[]
}
,
{
id:3,parentId:1,text:"childId3Parent1",nodes:[]
}
,
{
id:4,parentId:1,text:"childId4Parent1",nodes:[]
}
,
{
id:5,parentId:2,text:"childId5Parent2",nodes:[]
}
,
{
id:6,parentId:2,text:"childId6Parent2",nodes:[]
}
,
{
id:7,parentId:3,text:"childId7Parent3",nodes:[]
}
,
{
id:8,parentId:5,text:"childId8Parent5",nodes:[]
}];
감사합니다 Bakhshabadi씨
행운을 빌어요
패키지 리스트 투 트리 설치가 도움이 될 수 있습니다.
bower install list-to-tree --save
또는
npm install list-to-tree --save
예를 들어 have list:
var list = [
{
id: 1,
parent: 0
}, {
id: 2,
parent: 1
}, {
id: 3,
parent: 1
}, {
id: 4,
parent: 2
}, {
id: 5,
parent: 2
}, {
id: 6,
parent: 0
}, {
id: 7,
parent: 0
}, {
id: 8,
parent: 7
}, {
id: 9,
parent: 8
}, {
id: 10,
parent: 0
}
];
패키지 리스트 투 트리 사용:
var ltt = new LTT(list, {
key_id: 'id',
key_parent: 'parent'
});
var tree = ltt.GetTree();
결과:
[{
"id": 1,
"parent": 0,
"child": [
{
"id": 2,
"parent": 1,
"child": [
{
"id": 4,
"parent": 2
}, {
"id": 5, "parent": 2
}
]
},
{
"id": 3,
"parent": 1
}
]
}, {
"id": 6,
"parent": 0
}, {
"id": 7,
"parent": 0,
"child": [
{
"id": 8,
"parent": 7,
"child": [
{
"id": 9,
"parent": 8
}
]
}
]
}, {
"id": 10,
"parent": 0
}];
사용자 Shekhardtu(답변 참조)와 FurkanO(답변 참조)가 제안한 가장 일반적인 두 솔루션(입력 내용을 미리 정렬할 필요가 없으며 코드는 서드파티 라이브러리에 의존하지 않음)의 성능을 평가하기 위한 테스트 스크립트를 작성했습니다.
http://playcode.io/316025?tabs=console&script.js&output
FurkanO의 솔루션이 가장 빠를 것 같습니다.
/*
** performance test for https://stackoverflow.com/questions/18017869/build-tree-array-from-flat-array-in-javascript
*/
// Data Set (e.g. nested comments)
var comments = [{
id: 1,
parent_id: null
}, {
id: 2,
parent_id: 1
}, {
id: 3,
parent_id: 4
}, {
id: 4,
parent_id: null
}, {
id: 5,
parent_id: 4
}];
// add some random entries
let maxParentId = 10000;
for (let i=6; i<=maxParentId; i++)
{
let randVal = Math.floor((Math.random() * maxParentId) + 1);
comments.push({
id: i,
parent_id: (randVal % 200 === 0 ? null : randVal)
});
}
// solution from user "shekhardtu" (https://stackoverflow.com/a/55241491/5135171)
const nest = (items, id = null, link = 'parent_id') =>
items
.filter(item => item[link] === id)
.map(item => ({ ...item, children: nest(items, item.id) }));
;
// solution from user "FurkanO" (https://stackoverflow.com/a/40732240/5135171)
const createDataTree = dataset => {
let hashTable = Object.create(null)
dataset.forEach( aData => hashTable[aData.id] = { ...aData, children : [] } )
let dataTree = []
dataset.forEach( aData => {
if( aData.parent_id ) hashTable[aData.parent_id].children.push(hashTable[aData.id])
else dataTree.push(hashTable[aData.id])
} )
return dataTree
};
/*
** lets evaluate the timing for both methods
*/
let t0 = performance.now();
let createDataTreeResult = createDataTree(comments);
let t1 = performance.now();
console.log("Call to createDataTree took " + Math.floor(t1 - t0) + " milliseconds.");
t0 = performance.now();
let nestResult = nest(comments);
t1 = performance.now();
console.log("Call to nest took " + Math.floor(t1 - t0) + " milliseconds.");
//console.log(nestResult);
//console.log(createDataTreeResult);
// bad, but simple way of comparing object equality
console.log(JSON.stringify(nestResult)===JSON.stringify(createDataTreeResult));업데이트 2022
주문되지 않은 상품에 대한 제안입니다.는 단일 및 하여 동작하며 합니다.id루트 노드가 발견되면 개체가 결과 배열에 추가됩니다.
const
getTree = (data, root) => {
const t = {};
data.forEach(o => ((t[o.parentId] ??= {}).children ??= []).push(Object.assign(t[o.id] ??= {}, o)));
return t[root].children;
},
data = { People: [{ id: "12", parentId: "0", text: "Man", level: "1", children: null }, { id: "6", parentId: "12", text: "Boy", level: "2", children: null }, { id: "7", parentId: "12", text: "Other", level: "2", children: null }, { id: "9", parentId: "0", text: "Woman", level: "1", children: null }, { id: "11", parentId: "9", text: "Girl", level: "2", children: null }], Animals: [{ id: "5", parentId: "0", text: "Dog", level: "1", children: null }, { id: "8", parentId: "5", text: "Puppy", level: "2", children: null }, { id: "10", parentId: "13", text: "Cat", level: "1", children: null }, { id: "14", parentId: "13", text: "Kitten", level: "2", children: null }] },
result = Object.fromEntries(Object
.entries(data)
.map(([k, v]) => [k, getTree(v, '0')])
);
console.log(result);.as-console-wrapper { max-height: 100% !important; top: 0; }여러 번 시도한 끝에 이렇게 생각해냈다.
const arrayToTree = (arr, parent = 0) => arr .filter(item => item.parent === parent).map(child => ({ ...child, children: arrayToTree(arr, child.index) }));
const entries = [
{
index: 1,
parent: 0
},
{
index: 2,
parent: 1
},
{
index: 3,
parent: 2
},
{
index: 4,
parent: 2
},
{
index: 5,
parent: 4
},
{
index: 6,
parent: 5
},
{
index: 7,
parent: 6
},
{
index: 8,
parent: 7
},
{
index: 9,
parent: 8
},
{
index: 10,
parent: 9
},
{
index: 11,
parent: 7
},
{
index: 13,
parent: 11
},
{
index: 12,
parent: 0
}
];
const arrayToTree = (arr, parent = 0) => arr .filter(item => item.parent === parent) .map(child => ({ ...child, children: arrayToTree(arr, child.index) })); console.log(arrayToTree(entries));나는 @William을 좋아한다.Leung의 순수 JavaScript 솔루션이지만 객체를 참조하기 위해 기존 어레이를 변경해야 할 수 있습니다.
function listToTree(data, options) {
options = options || {};
var ID_KEY = options.idKey || 'id';
var PARENT_KEY = options.parentKey || 'parent';
var CHILDREN_KEY = options.childrenKey || 'children';
var item, id, parentId;
var map = {};
for(var i = 0; i < data.length; i++ ) { // make cache
if(data[i][ID_KEY]){
map[data[i][ID_KEY]] = data[i];
data[i][CHILDREN_KEY] = [];
}
}
for (var i = 0; i < data.length; i++) {
if(data[i][PARENT_KEY]) { // is a child
if(map[data[i][PARENT_KEY]]) // for dirty data
{
map[data[i][PARENT_KEY]][CHILDREN_KEY].push(data[i]); // add child to parent
data.splice( i, 1 ); // remove from root
i--; // iterator correction
} else {
data[i][PARENT_KEY] = 0; // clean dirty data
}
}
};
return data;
}
예: https://jsfiddle.net/kqw1qsf0/17/
노드 어레이를 트리로 변환
노드 배열(부모 ID에 의해 관련됨)을 트리 구조로 변환하는 ES6 함수:
/**
* Convert nodes list related by parent ID - to tree.
* @syntax getTree(nodesArray [, rootID [, propertyName]])
*
* @param {Array} arr Array of nodes
* @param {integer} id Defaults to 0
* @param {string} p Property name. Defaults to "parent_id"
* @returns {Object} Nodes tree
*/
const getTree = (arr, p = "parent_id") => arr.reduce((o, n) => {
if (!o[n.id]) o[n.id] = {};
if (!o[n[p]]) o[n[p]] = {};
if (!o[n[p]].nodes) o[n[p]].nodes= [];
if (o[n.id].nodes) n.nodes= o[n.id].nodes;
o[n[p]].nodes.push(n);
o[n.id] = n;
return o;
}, {});
노드에서 HTML 목록 생성 트리
트리를 배치하고 UL > LI 요소를 작성하는 재귀 함수를 다음에 나타냅니다.
/**
* Convert Tree structure to UL>LI and append to Element
* @syntax getTree(treeArray [, TargetElement [, onLICreatedCallback ]])
*
* @param {Array} tree Tree array of nodes
* @param {Element} el HTMLElement to insert into
* @param {function} cb Callback function called on every LI creation
*/
const treeToHTML = (tree, el, cb) => el.append(tree.reduce((ul, n) => {
const li = document.createElement('li');
if (cb) cb.call(li, n);
if (n.nodes?.length) treeToHTML(n.nodes, li, cb);
ul.append(li);
return ul;
}, document.createElement('ul')));
데모 타임
다음은 노드의 선형 어레이를 사용하여 위의 두 함수를 모두 사용하는 예입니다.
const getTree = (arr, p = "parent_id") => arr.reduce((o, n) => {
if (!o[n.id]) o[n.id] = {};
if (!o[n[p]]) o[n[p]] = {};
if (!o[n[p]].nodes) o[n[p]].nodes = [];
if (o[n.id].nodes) n.nodes = o[n.id].nodes;
o[n[p]].nodes.push(n);
o[n.id] = n;
return o;
}, {});
const treeToHTML = (tree, el, cb) => el.append(tree.reduce((ul, n) => {
const li = document.createElement('li');
if (cb) cb.call(li, n);
if (n.nodes?.length) treeToHTML(n.nodes, li, cb);
ul.append(li);
return ul;
}, document.createElement('ul')));
// DEMO TIME:
const nodesList = [
{id: 10, parent_id: 4, text: "Item 10"}, // PS: Order does not matters
{id: 1, parent_id: 0, text: "Item 1"},
{id: 4, parent_id: 0, text: "Item 4"},
{id: 3, parent_id: 5, text: "Item 3"},
{id: 5, parent_id: 4, text: "Item 5"},
{id: 2, parent_id: 1, text: "Item 2"},
];
const myTree = getTree(nodesList)[0].nodes; // Get nodes of Root (0)
treeToHTML(myTree, document.querySelector("#tree"), function(node) {
this.textContent = `(${node.parent_id} ${node.id}) ${node.text}`;
this._node = node;
this.addEventListener('click', clickHandler);
});
function clickHandler(ev) {
if (ev.target !== this) return;
console.clear();
console.log(this._node.id);
};<div id="tree"></div>var data = [{"country":"india","gender":"male","type":"lower","class":"X"},
{"country":"china","gender":"female","type":"upper"},
{"country":"india","gender":"female","type":"lower"},
{"country":"india","gender":"female","type":"upper"}];
var seq = ["country","type","gender","class"];
var treeData = createHieArr(data,seq);
console.log(treeData)
function createHieArr(data,seq){
var hieObj = createHieobj(data,seq,0),
hieArr = convertToHieArr(hieObj,"Top Level");
return [{"name": "Top Level", "parent": "null",
"children" : hieArr}]
function convertToHieArr(eachObj,parent){
var arr = [];
for(var i in eachObj){
arr.push({"name":i,"parent":parent,"children":convertToHieArr(eachObj[i],i)})
}
return arr;
}
function createHieobj(data,seq,ind){
var s = seq[ind];
if(s == undefined){
return [];
}
var childObj = {};
for(var ele of data){
if(ele[s] != undefined){
if(childObj[ele[s]] == undefined){
childObj[ele[s]] = [];
}
childObj[ele[s]].push(ele);
}
}
ind = ind+1;
for(var ch in childObj){
childObj[ch] = createHieobj(childObj[ch],seq,ind)
}
return childObj;
}
}리액트 프로젝트에서 사용한 것입니다.
// ListToTree.js
import _filter from 'lodash/filter';
import _map from 'lodash/map';
export default (arr, parentIdKey) => _map(_filter(arr, ar => !ar[parentIdKey]), ar => ({
...ar,
children: _filter(arr, { [parentIdKey]: ar.id }),
}));
사용방법:
// somewhere.js
import ListToTree from '../Transforms/ListToTree';
const arr = [
{
"id":"Bci6XhCLZKPXZMUztm1R",
"name":"Sith"
},
{
"id":"C3D71CMmASiR6FfDPlEy",
"name":"Luke",
"parentCategoryId":"ltatOlEkHdVPf49ACCMc"
},
{
"id":"aS8Ag1BQqxkO6iWBFnsf",
"name":"Obi Wan",
"parentCategoryId":"ltatOlEkHdVPf49ACCMc"
},
{
"id":"ltatOlEkHdVPf49ACCMc",
"name":"Jedi"
},
{
"id":"pw3CNdNhnbuxhPar6nOP",
"name":"Palpatine",
"parentCategoryId":"Bci6XhCLZKPXZMUztm1R"
}
];
const response = ListToTree(arr, 'parentCategoryId');
출력:
[
{
"id":"Bci6XhCLZKPXZMUztm1R",
"name":"Sith",
"children":[
{
"id":"pw3CNdNhnbuxhPar6nOP",
"name":"Palpatine",
"parentCategoryId":"Bci6XhCLZKPXZMUztm1R"
}
]
},
{
"id":"ltatOlEkHdVPf49ACCMc",
"name":"Jedi",
"children":[
{
"id":"C3D71CMmASiR6FfDPlEy",
"name":"Luke",
"parentCategoryId":"ltatOlEkHdVPf49ACCMc"
},
{
"id":"aS8Ag1BQqxkO6iWBFnsf",
"name":"Obi Wan",
"parentCategoryId":"ltatOlEkHdVPf49ACCMc"
}
]
}
]```
며칠 전 플랫 어레이에서 폴더 트리를 표시해야 할 때도 비슷한 문제가 있었습니다.여기 TypeScript에는 아무런 솔루션이 없기 때문에 도움이 되었으면 합니다.
제 경우 메인 부모만 1개였고 rawData 배열도 정렬할 필요가 없습니다. object object음 solutions solutions음 、 음음 、 음음 、 like object 、 like object like like like 。{parentId: [child1, child2, ...] }
원시 데이터 예제
const flatData: any[] = Folder.ofCollection([
{id: '1', title: 'some title' },
{id: '2', title: 'some title', parentId: 1 },
{id: '3', title: 'some title', parentId: 7 },
{id: '4', title: 'some title', parentId: 1 },
{id: '5', title: 'some title', parentId: 2 },
{id: '6', title: 'some title', parentId: 5 },
{id: '7', title: 'some title', parentId: 5 },
]);
폴더 정의
export default class Folder {
public static of(data: any): Folder {
return new Folder(data);
}
public static ofCollection(objects: any[] = []): Folder[] {
return objects.map((obj) => new Folder(obj));
}
public id: string;
public parentId: string | null;
public title: string;
public children: Folder[];
constructor(data: any = {}) {
this.id = data.id;
this.parentId = data.parentId || null;
this.title = data.title;
this.children = data.children || [];
}
}
솔루션: 플랫 인수의 트리 구조를 반환하는 함수
public getTree(flatData: any[]): Folder[] {
const addChildren = (item: Folder) => {
item.children = tempChild[item.id] || [];
if (item.children.length) {
item.children.forEach((child: Folder) => {
addChildren(child);
});
}
};
const tempChild: any = {};
flatData.forEach((item: Folder) => {
const parentId = item.parentId || 0;
Array.isArray(tempChild[parentId]) ? tempChild[parentId].push(item) : (tempChild[parentId] = [item]);
});
const tree: Folder[] = tempChild[0];
tree.forEach((base: Folder) => {
addChildren(base);
});
return tree;
}
@Halcyon 답변을 바탕으로 ES6 버전을 작성했습니다.
const array = [
{
id: '12',
parentId: '0',
text: 'one-1'
},
{
id: '6',
parentId: '12',
text: 'one-1-6'
},
{
id: '7',
parentId: '12',
text: 'one-1-7'
},
{
id: '9',
parentId: '0',
text: 'one-2'
},
{
id: '11',
parentId: '9',
text: 'one-2-11'
}
];
// Prevent changes to the original data
const arrayCopy = array.map(item => ({ ...item }));
const listToTree = list => {
const map = {};
const roots = [];
list.forEach((v, i) => {
map[v.id] = i;
list[i].children = [];
});
list.forEach(v => (v.parentId !== '0' ? list[map[v.parentId]].children.push(v) : roots.push(v)));
return roots;
};
console.log(listToTree(arrayCopy));
이 알고리즘의 원리는 "맵"을 사용하여 인덱스 관계를 설정하는 것입니다."parentId"에 의해 목록에서 "항목"을 찾고 각 "항목"에 "자녀"를 추가하는 것은 쉽습니다. "목록"은 참조 관계이므로 "root"은 트리 전체와 관계를 구축합니다.
@FurkanO의 답변을 바탕으로 원본 데이터를 변환하지 않는 다른 버전(@Dac0d3r requested 등)을 작성했습니다.@shekhardtu의 답변은 매우 마음에 들었지만, 여러 번 데이터를 걸러내야 한다는 것을 깨달았습니다.FurkanO의 답변을 먼저 복사하여 사용하는 것이 해결책이라고 생각했습니다.jsperf로 내 버전을 시험해 봤는데, 아쉽게도 (매우) 암울한 결과가...받아들여진 답변이 정말 좋은 답변인 것 같아요!제 버전은 설정이 가능하고 Fail Safe이기 때문에 여러분들과 공유하겠습니다.제 공헌은 다음과 같습니다.
function unflat(data, options = {}) {
const { id, parentId, childrenKey } = {
id: "id",
parentId: "parentId",
childrenKey: "children",
...options
};
const copiesById = data.reduce(
(copies, datum) => ((copies[datum[id]] = datum) && copies),
{}
);
return Object.values(copiesById).reduce(
(root, datum) => {
if ( datum[parentId] && copiesById[datum[parentId]] ) {
copiesById[datum[parentId]][childrenKey] = [ ...copiesById[datum[parentId]][childrenKey], datum ];
} else {
root = [ ...root, datum ];
}
return root
}, []
);
}
const data = [
{
"account": "10",
"name": "Konto 10",
"parentAccount": null
},{
"account": "1010",
"name": "Konto 1010",
"parentAccount": "10"
},{
"account": "10101",
"name": "Konto 10101",
"parentAccount": "1010"
},{
"account": "10102",
"name": "Konto 10102",
"parentAccount": "1010"
},{
"account": "10103",
"name": "Konto 10103",
"parentAccount": "1010"
},{
"account": "20",
"name": "Konto 20",
"parentAccount": null
},{
"account": "2020",
"name": "Konto 2020",
"parentAccount": "20"
},{
"account": "20201",
"name": "Konto 20201",
"parentAccount": "2020"
},{
"account": "20202",
"name": "Konto 20202",
"parentAccount": "2020"
}
];
const options = {
id: "account",
parentId: "parentAccount",
childrenKey: "children"
};
console.log(
"Hierarchical tree",
unflat(data, options)
);
options 파라미터를 사용하면 ID 또는 부모 ID로 사용할 속성을 설정할 수 있습니다.원하는 경우 자식 속성의 이름을 구성할 수도 있습니다."childNodes": []뭐 그런 거.
OP는 기본 옵션을 사용할 수 있습니다.
input.People = unflat(input.People);
부모 ID가 가짜인 경우(null,undefined또는 다른 거짓 값) 또는 부모 개체가 존재하지 않는 경우 해당 개체를 루트 노드로 간주합니다.
다중 부모에게 필요한 경우.여러 부모를 가진 ID 2를 참조합니다.
const dataSet = [{
"ID": 1,
"Phone": "(403) 125-2552",
"City": "Coevorden",
"Name": "Grady"
},
{"ID": 2,
"Phone": "(403) 125-2552",
"City": "Coevorden",
"Name": "Grady"
},
{
"ID": 3,
"parentID": [1,2],
"Phone": "(979) 486-1932",
"City": "Chełm",
"Name": "Scarlet"
}];
const expectedDataTree = [
{
"ID":1,
"Phone":"(403) 125-2552",
"City":"Coevorden",
"Name":"Grady",
"childNodes":[{
"ID":2,
"parentID":[1,3],
"Phone":"(979) 486-1932",
"City":"Chełm",
"Name":"Scarlet",
"childNodes":[]
}]
},
{
"ID":3,
"parentID":[],
"Phone":"(403) 125-2552",
"City":"Coevorden",
"Name":"Grady",
"childNodes":[
{
"ID":2,
"parentID":[1,3],
"Phone":"(979) 486-1932",
"City":"Chełm",
"Name":"Scarlet",
"childNodes":[]
}
]
}
];
const createDataTree = dataset => {
const hashTable = Object.create(null);
dataset.forEach(aData => hashTable[aData.ID] = {...aData, childNodes: []});
const dataTree = [];
dataset.forEach(Datae => {
if (Datae.parentID && Datae.parentID.length > 0) {
Datae.parentID.forEach( aData => {
hashTable[aData].childNodes.push(hashTable[Datae.ID])
});
}
else{
dataTree.push(hashTable[Datae.ID])
}
});
return dataTree;
};
window.alert(JSON.stringify(createDataTree(dataSet)));다음은 Babel 환경에 맞게 위의 답변을 본떠 만든 간단한 도우미 기능입니다.
import { isEmpty } from 'lodash'
export default function unflattenEntities(entities, parent = {id: null}, tree = []) {
let children = entities.filter( entity => entity.parent_id == parent.id)
if (!isEmpty( children )) {
if ( parent.id == null ) {
tree = children
} else {
parent['children'] = children
}
children.map( child => unflattenEntities( entities, child ) )
}
return tree
}
또한 lodashj(v4.x)를 사용하여 실행한다.
function buildTree(arr){
var a=_.keyBy(arr, 'id')
return _
.chain(arr)
.groupBy('parentId')
.forEach(function(v,k){
k!='0' && (a[k].children=(a[k].children||[]).concat(v));
})
.result('0')
.value();
}
여기 Steven Harris의 수정 버전이 있습니다.일반 ES5로 최상위 수준과 하위 수준 모두에서 노드 배열을 반환하지 않고 ID에 키를 입력한 개체를 반환합니다.
unflattenToObject = function(array, parent) {
var tree = {};
parent = typeof parent !== 'undefined' ? parent : {id: 0};
var childrenArray = array.filter(function(child) {
return child.parentid == parent.id;
});
if (childrenArray.length > 0) {
var childrenObject = {};
// Transform children into a hash/object keyed on token
childrenArray.forEach(function(child) {
childrenObject[child.id] = child;
});
if (parent.id == 0) {
tree = childrenObject;
} else {
parent['children'] = childrenObject;
}
childrenArray.forEach(function(child) {
unflattenToObject(array, child);
})
}
return tree;
};
var arr = [
{'id':1 ,'parentid': 0},
{'id':2 ,'parentid': 1},
{'id':3 ,'parentid': 1},
{'id':4 ,'parentid': 2},
{'id':5 ,'parentid': 0},
{'id':6 ,'parentid': 0},
{'id':7 ,'parentid': 4}
];
tree = unflattenToObject(arr);
이것은 위의 여러 루트 항목과 함께 작동하는 수정 버전입니다. 저는 ID와 parentId에 GUID를 사용하므로 이를 생성하는 UI에서 루트 항목을 0000000-00000-TREE-ROOT-ITEM과 같은 것으로 하드 코드합니다.
var tree = unflaten("트리-ROOT-ITEM");
function unflatten(records, rootCategoryId, parent, tree){
if(!_.isArray(tree)){
tree = [];
_.each(records, function(rec){
if(rec.parentId.indexOf(rootCategoryId)>=0){ // change this line to compare a root id
//if(rec.parentId == 0 || rec.parentId == null){ // example for 0 or null
var tmp = angular.copy(rec);
tmp.children = _.filter(records, function(r){
return r.parentId == tmp.id;
});
tree.push(tmp);
//console.log(tree);
_.each(tmp.children, function(child){
return unflatten(records, rootCategoryId, child, tree);
});
}
});
}
else{
if(parent){
parent.children = _.filter(records, function(r){
return r.parentId == parent.id;
});
_.each(parent.children, function(child){
return unflatten(records, rootCategoryId, child, tree);
});
}
}
return tree;
}
인터넷 http://jsfiddle.net/stywell/k9x2a3g6/에서 복사.
function list2tree(data, opt) {
opt = opt || {};
var KEY_ID = opt.key_id || 'ID';
var KEY_PARENT = opt.key_parent || 'FatherID';
var KEY_CHILD = opt.key_child || 'children';
var EMPTY_CHILDREN = opt.empty_children;
var ROOT_ID = opt.root_id || 0;
var MAP = opt.map || {};
function getNode(id) {
var node = []
for (var i = 0; i < data.length; i++) {
if (data[i][KEY_PARENT] == id) {
for (var k in MAP) {
data[i][k] = data[i][MAP[k]];
}
if (getNode(data[i][KEY_ID]) !== undefined) {
data[i][KEY_CHILD] = getNode(data[i][KEY_ID]);
} else {
if (EMPTY_CHILDREN === null) {
data[i][KEY_CHILD] = null;
} else if (JSON.stringify(EMPTY_CHILDREN) === '[]') {
data[i][KEY_CHILD] = [];
}
}
node.push(data[i]);
}
}
if (node.length == 0) {
return;
} else {
return node;
}
}
return getNode(ROOT_ID)
}
var opt = {
"key_id": "ID", //节点的ID
"key_parent": "FatherID", //节点的父级ID
"key_child": "children", //子节点的名称
"empty_children": [], //子节点为空时,填充的值 //这个参数为空时,没有子元素的元素不带key_child属性;还可以为null或者[],同理
"root_id": 0, //根节点的父级ID
"map": { //在节点内映射一些值 //对象的键是节点的新属性; 对象的值是节点的老属性,会赋值给新属性
"value": "ID",
"label": "TypeName",
}
};
npm package array-to-tree https://github.com/alferov/array-to-tree 를 사용할 수 있습니다.부모 노드에 대한 포인터가 있는 노드의 플레인 어레이를 중첩된 데이터 구조로 변환합니다.
검색된 데이터를 데이터베이스 집합에서 중첩된 데이터 구조(예: 탐색 트리)로 변환하여 문제를 해결합니다.
사용방법:
var arrayToTree = require('array-to-tree');
var dataOne = [
{
id: 1,
name: 'Portfolio',
parent_id: undefined
},
{
id: 2,
name: 'Web Development',
parent_id: 1
},
{
id: 3,
name: 'Recent Works',
parent_id: 2
},
{
id: 4,
name: 'About Me',
parent_id: undefined
}
];
arrayToTree(dataOne);
/*
* Output:
*
* Portfolio
* Web Development
* Recent Works
* About Me
*/
이 Github의 "treeify" 패키지는 여기 또는 NPM에서 사용할 수 있습니다.
설치:
$ npm install --save-dev treeify-js
내 타이프스크립트 솔루션은 다음과 같은 도움이 될 수 있습니다.
type ITreeItem<T> = T & {
children: ITreeItem<T>[],
};
type IItemKey = string | number;
function createTree<T>(
flatList: T[],
idKey: IItemKey,
parentKey: IItemKey,
): ITreeItem<T>[] {
const tree: ITreeItem<T>[] = [];
// hash table.
const mappedArr = {};
flatList.forEach(el => {
const elId: IItemKey = el[idKey];
mappedArr[elId] = el;
mappedArr[elId].children = [];
});
// also you can use Object.values(mappedArr).forEach(...
// but if you have element which was nested more than one time
// you should iterate flatList again:
flatList.forEach((elem: ITreeItem<T>) => {
const mappedElem = mappedArr[elem[idKey]];
if (elem[parentKey]) {
mappedArr[elem[parentKey]].children.push(elem);
} else {
tree.push(mappedElem);
}
});
return tree;
}
사용 예:
createTree(yourListData, 'id', 'parentId');
유사한 질문에 대한 답변:
https://stackoverflow.com/a/61575152/7388356
갱신하다
하시면 됩니다.MapES6를 사용하다기본적으로 어레이를 다시 반복하여 상위 항목을 찾는 대신 어레이의 상위 항목을 인덱스로 가져오듯이 상위 항목을 상위 ID로 가져옵니다.
다음으로 간단한 예를 제시하겠습니다.
const people = [
{
id: "12",
parentId: "0",
text: "Man",
level: "1",
children: null
},
{
id: "6",
parentId: "12",
text: "Boy",
level: "2",
children: null
},
{
id: "7",
parentId: "12",
text: "Other",
level: "2",
children: null
},
{
id: "9",
parentId: "0",
text: "Woman",
level: "1",
children: null
},
{
id: "11",
parentId: "9",
text: "Girl",
level: "2",
children: null
}
];
function toTree(arr) {
let arrMap = new Map(arr.map(item => [item.id, item]));
let tree = [];
for (let i = 0; i < arr.length; i++) {
let item = arr[i];
if (item.parentId !== "0") {
let parentItem = arrMap.get(item.parentId);
if (parentItem) {
let { children } = parentItem;
if (children) {
parentItem.children.push(item);
} else {
parentItem.children = [item];
}
}
} else {
tree.push(item);
}
}
return tree;
}
let tree = toTree(people);
console.log(tree);
솔루션:
- 양방향 매핑 가능(루트에서 탈퇴 및 탈퇴에서 루트로)
- 모든 노드, 루트 및 리프를 반환합니다.
- 1개의 데이터 패스로 매우 빠른 퍼포먼스
- 바닐라 자바스크립트
/**
*
* @param data items array
* @param idKey item's id key (e.g., item.id)
* @param parentIdKey item's key that points to parent (e.g., item.parentId)
* @param noParentValue item's parent value when root (e.g., item.parentId === noParentValue => item is root)
* @param bidirectional should parent reference be added
*/
function flatToTree(data, idKey, parentIdKey, noParentValue = null, bidirectional = true) {
const nodes = {}, roots = {}, leaves = {};
// iterate over all data items
for (const i of data) {
// add item as a node and possibly as a leaf
if (nodes[i[idKey]]) { // already seen this item when child was found first
// add all of the item's data and found children
nodes[i[idKey]] = Object.assign(nodes[i[idKey]], i);
} else { // never seen this item
// add to the nodes map
nodes[i[idKey]] = Object.assign({ $children: []}, i);
// assume it's a leaf for now
leaves[i[idKey]] = nodes[i[idKey]];
}
// put the item as a child in parent item and possibly as a root
if (i[parentIdKey] !== noParentValue) { // item has a parent
if (nodes[i[parentIdKey]]) { // parent already exist as a node
// add as a child
(nodes[i[parentIdKey]].$children || []).push( nodes[i[idKey]] );
} else { // parent wasn't seen yet
// add a "dummy" parent to the nodes map and put the item as its child
nodes[i[parentIdKey]] = { $children: [ nodes[i[idKey]] ] };
}
if (bidirectional) {
// link to the parent
nodes[i[idKey]].$parent = nodes[i[parentIdKey]];
}
// item is definitely not a leaf
delete leaves[i[parentIdKey]];
} else { // this is a root item
roots[i[idKey]] = nodes[i[idKey]];
}
}
return {roots, nodes, leaves};
}
사용 예:
const data = [{id: 2, parentId: 0}, {id: 1, parentId: 2} /*, ... */];
const { nodes, roots, leaves } = flatToTree(data, 'id', 'parentId', 0);
ES6 맵 버전:
getTreeData = (items) => {
if (items && items.length > 0) {
const data = [];
const map = {};
items.map((item) => {
const id = item.id; // custom id selector !!!
if (!map.hasOwnProperty(id)) {
// in case of duplicates
map[id] = {
...item,
children: [],
};
}
});
for (const id in map) {
if (map.hasOwnProperty(id)) {
let mappedElem = [];
mappedElem = map[id];
/// parentId : use custom id selector for parent
if (
mappedElem.parentId &&
typeof map[mappedElem.parentId] !== "undefined"
) {
map[mappedElem.parentId].children.push(mappedElem);
} else {
data.push(mappedElem);
}
}
}
return data;
}
return [];
};
/// use like this :
const treeData = getTreeData(flatList);
언급URL : https://stackoverflow.com/questions/18017869/build-tree-array-from-flat-array-in-javascript
반응형
'source' 카테고리의 다른 글
| python 다중 처리를 시도하는 Windows의 RuntimeError (0) | 2023.01.08 |
|---|---|
| 항아리가 장착되지 않았습니다.Servlet 사양 2.3, 섹션 9.7.2를 참조한다.문제 클래스: javax/servlet/Servlet.class (0) | 2023.01.08 |
| 데이터베이스 사용자도 mysql, information_schema 및 performance_schema 테이블에 액세스할 수 있어야 합니까? (0) | 2023.01.08 |
| Composer를 사용하지 않고 Composer PHP 패키지를 설치하려면 어떻게 해야 합니까? (0) | 2023.01.08 |
| C 프로그래밍:전달 변수 인수 목록 (0) | 2022.12.24 |