我有一个复杂的json文件,我必须处理javascript使其分层,以便稍后构建树。 json的每个条目都有: Id:唯一的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
            }
        }

    ]
}

当前回答

下面是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);

其他回答

下面是我根据上面的答案创建的一个简单的帮助函数,为通天塔环境量身定制:

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

}

下面是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);

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

你可以使用npm包数组到树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
 */

我根据@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));

该算法的原理是利用“map”建立索引关系。通过“parentId”可以很容易地在列表中找到“item”,并为每个“item”添加“children”,因为“list”是一个引用关系,所以“roots”将与整个树建立关系。