用JavaScript从平面数组构建树形数组

Question

用JavaScript从平面数组构建树形数组

222

我有一个复杂的JSON文件需要在JavaScript中处理，以使其成为分层结构，以便稍后构建一棵树。每个json条目都具有: id：唯一标识符， parentId：父节点的id（如果节点是树的根，则为0） level：树的深度级别

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

    ]
}

- Franck

2

有几种方法可以做到这一点，你尝试过什么了吗？ - bfavaretto

我假设 parentId 的值为 0 表示没有父级 ID，应该是顶层。 - Donnie D'Amato

2

通常这些任务需要对对象有广泛的工作知识。好问题。 - Buddybear

34个回答

132

(奖励1:节点可以有序也可以无序)

(奖励2:不需要第三方库，使用普通JS即可)

(奖励3:用户“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);
});

- FurkanO

3

如果只在需要时添加childNodes，这样做是否更准确？可以通过将它们从第一个forEach中删除并将其移到第二个forEach内部来实现吗？ - arpl

@FurkanO 的解决方案非常好，但是使用函数式编程（无变异）是否有可能达到这种性能？ - Dac0d3r

如果有人想让一个子项拥有多个父项，请参考 -> https://dev59.com/CWMl5IYBdhLWcg3w7qlq#65626153 - natrayan

我可以获取特定项目的子项吗？ - rendom

很棒的解决方案，但是你应该记得考虑parentId为零的情况，否则这个条件将无法正常工作：“if(aData.parentID)” - Amir

显示剩余2条评论

80

正如@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的元素，否则将返回一个空数组。孤立的元素及其后代将被忽略。

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

- Stephen Harris

5

你可以在第一个 if 语句后面添加 else { parent['children'] = []; } 来确保每个节点都有一个 children 属性（如果节点是叶子节点，则为空）。 - Christopher

2

你的代码片段完美地运行了，谢谢！唯一的问题是：在递归调用函数时，tree从未作为参数传递，因此我认为可以将 tree = typeof tree !== 'undefined' ? tree : []; 这一行替换为 let tree = [];。 - Oscar Calderon

2

请注意，上面的答案使用了两个循环，因此可以进行改进。由于我找不到一个实现O(n)解决方案的npm模块，所以我创建了以下这个（经过单元测试，100%代码覆盖率，仅0.5 kb大小并包含类型定义）。也许它能帮助某些人：npmjs.com/package/performant-array-to-tree - Philip Stanislaus

链接：用只有两行代码来处理这个问题 - Iman Bahrampour

5

对于任何感兴趣的人，这段代码可以很容易地转换为普通的 JavaScript：http://jsfiddle.net/LkkwH/853/。 - xec

显示剩余5条评论

71

使用这个 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)
)

- shekhardtu

7

我认为最简短且最好的答案是： - bekliev

6

相对于FurkanO的回答，速度非常慢。 - Geza Turi

2

如果数组有多个空的parentId，则不起作用。 - Amjad Mehmood

是的，有没有办法使其适用于多个空父ID？ - chovy

38

我有同样的问题，但我不能确定数据是否已经排序。我不能使用第三方库，所以这只是使用原始的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 Fiddle

将平面数组转换为树形结构

- alexandru.pausan

在某些情况下，mappedArr[mappedElem['parentid']]['children'] 会失败，因为无法访问未定义的 children。 - Al-Mothafar

我该如何从父ID为1开始？ - vinni

18

一个更简单的函数list-to-tree-lite

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

- William Leung

17

你只需要两行代码就可以处理这个问题。

flatArray.forEach(f=>
       {f.nodes=flatArray.filter(g=>g.parentId===f.id)});
var resultArray=flatArray.filter(f=>f.parentId==null);

var flatArray =
    [{
        id: 1, parentId: null, text: "parent1"
    }
        , {
        id: 2, parentId: null, text: "parent2"
    }
        ,
    {
        id: 3, parentId: 1, text: "childId3Parent1"
    }
        ,
    {
        id: 4, parentId: 1, text: "childId4Parent1"
    }
        ,
    {
        id: 5, parentId: 2, text: "childId5Parent2"
    }
        ,
    {
        id: 6, parentId: 2, text: "childId6Parent2"
    }
        ,
    {
        id: 7, parentId: 3, text: "childId7Parent3"
    }
        ,
    {
        id: 8, parentId: 5, text: "childId8Parent5"
    }];
    flatArray.forEach(f=>
           {f.nodes=flatArray.filter(g=>g.parentId===f.id)});

        var resultArray=flatArray.filter(f=>f.parentId==null);
    console.log(resultArray)

现在不需要使用lodash库了：@Abed abuSalah

祝你好运

- Iman Bahrampour

这个解决方案的时间复杂度为 O(n^2)。 - cbr

那是好的还是不好的？ - chovy

你的解决方案没有使用 lodash 也能正常工作。 - Abed abuSalah

7

我编写了一个测试脚本来评估两个最常见的解决方案（即输入不需要事先排序且代码不依赖第三方库），这两个方案是由用户shekhardtu（请参阅答案）和FurkanO（请参阅答案）提出的。 http://playcode.io/316025?tabs=console&script.js&output FurkanO的解决方案似乎是最快的。

/*
** performance test for https://dev59.com/CWMl5IYBdhLWcg3w7qlq
*/

// 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://dev59.com/CWMl5IYBdhLWcg3w7qlq#55241491)
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://dev59.com/CWMl5IYBdhLWcg3w7qlq#40732240)
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));

- Elias Rabl

playcode.io 出现了错误提示 "error: Uncaught ReferenceError: global is not defined"；但是将代码直接粘贴到浏览器中运行却没有问题；对于所有的开发者来说，createDataTree 的速度比另一个方法快15-16倍。 - ddruganov

是的，这应该是被接受的答案，尽管我不明白它如何在没有递归的情况下工作。 - chovy

7

经过多次尝试，我想到了这个:

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

- Daniel Bellmas

2

（item.parent ?? 0）添加此项以处理父级为空的情况。 - dungtv

通常父级会在那里，因为我们是从后端获取数据。我尝试查看代码是否会在没有父级或为空时失败，但它仍然保持不变。可能是我没有完全理解你的意思吗？ - Daniel Bellmas

7

这是一个有用的包：list-to-tree。安装方法：

bower install list-to-tree --save

或者

npm install list-to-tree --save

例如，有一个列表：

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

使用list-to-tree包：

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

- DenQ

2

请注意，仅链接答案是不被鼓励的，SO答案应该是寻找解决方案的终点（而不是另一个参考站点，随着时间的推移往往会变得陈旧）。请考虑在此处添加独立的摘要，将链接作为参考。 - kleopatra

我不明白为什么要用-1，我认为这是一个好的解决方案，但不幸的是我在GitHub或其他公共存储库中找不到该软件包。 - oriaj

感谢您关注这个软件包。我计划以后扩展它。这是一个指向存储库的链接 https://github.com/DenQ/list-to-tree - DenQ

@oriaj，我很高兴这个项目有所收益。还有一些想法的计划。 - DenQ

工作得很好，谢谢 @DenQ。不过希望它有更多的测试覆盖率！ - IliasT

写作时，我看到这个解决方案有两个问题：1.它不是自包含的；它向全局范围添加了更多内容而不仅仅是“LTT”。2：实现值得商榷。我相信它是正确的，但在内部对列表进行排序（我认为这是不必要的），在构建映射时效率低下（pluck + unique），并且在大量输入时使用函数调用使其变慢。 - Halcyon

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Halcyon · Accepted Answer

如果您使用地图查找，就有一个高效的解决方案。如果父母总是在他们的孩子之前，您可以合并两个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），对于大型数据集可能会有问题。