[javascript] 자바 스크립트의 플랫 배열에서 트리 배열 빌드

Program / 글쓴이

나중에 트리를 만들기 위해 계층 구조로 만들기 위해 자바 스크립트로 처리해야하는 복잡한 json 파일이 있습니다. json의 모든 항목에는 다음이 있습니다.

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
            }
        }

    ]
}

답변

지도 조회를 사용하는 경우 효율적인 솔루션이 있습니다. 부모가 항상 자녀보다 먼저 오는 경우 두 개의 for 루프를 병합 할 수 있습니다. 여러 뿌리를 지원합니다. 매달린 가지에 오류가 발생하지만 무시하도록 수정할 수 있습니다. 타사 라이브러리가 필요하지 않습니다. 내가 말할 수있는 한 가장 빠른 솔루션입니다.

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)이며 큰 데이터 세트의 경우 문제가 될 수 있습니다.

답변

@Sander에서 언급했듯이 @Halcyon의 대답 은 사전 정렬 된 배열을 가정하지만 다음은 그렇지 않습니다. (하지만 underscore.js를로드했다고 가정합니다. 바닐라 자바 ​​스크립트로 작성할 수 있습니다.)

암호

// 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 인 요소가 있어야합니다. 그렇지 않으면 빈 배열이 반환됩니다. 고아 요소와 그 하위 요소가 ‘손실’됨

http://jsfiddle.net/LkkwH/1/

답변

(보너스 1 : 노드 주문 가능 여부)

(보너스 2 : 제 3 자 라이브러리 필요 없음, 일반 JS)

(BONUS3 : 사용자 “Elias Rabl”이 이것이 가장 빠른 솔루션이라고 말합니다. 아래 답변을 참조하십시오.)

여기있어:

const createDataTree = dataset => {
    let hashTable = Object.create(null)
    dataset.forEach( aData => hashTable[aData.ID] = { ...aData, childNodes : [] } )
    let 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', () => {

    let dataSet = [
        {
            "ID": 1,
            "Phone": "(403) 125-2552",
            "City": "Coevorden",
            "Name": "Grady"
        },
        {
            "ID": 2,
            "parentID": 1,
            "Phone": "(979) 486-1932",
            "City": "Chełm",
            "Name": "Scarlet"
        }
    ]

    let 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)
});

답변

같은 문제가 있었지만 데이터가 정렬 되었는지 여부를 확신 할 수 없었습니다 . 제 3 자 라이브러리를 사용할 수 없었기 때문에 이것은 단지 바닐라 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 바이올린

플랫 배열에서 트리로

답변

이 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)
)

스 니펫 확장

답변

더 간단한 함수 목록-트리 라이트

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;
}

jsfiddle

답변

두 줄로 코딩하면이 질문을 처리 할 수 ​​있습니다.

_(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와 같은 수행 메서드 => 개체 및 컬렉션을 조작하기위한 자바 스크립트 라이브러리) Lodash

2- 아래와 같은 flatArray :

    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 님, 감사합니다.

행운을 빕니다