Javascript: построение иерархического дерева

Мои данные имеют следующие свойства:

Каждая запись имеет уникальный идентификатор (Id)
У каждого есть родительское поле, которое указывает на Id родителя.
Узел может иметь несколько дочерних элементов, но только один родительский элемент.

Моя первая попытка построить дерево ниже. Это глючит, поскольку рекурсия вызывает бесконечный цикл. Даже если я решу это, я не уверен, есть ли лучший подход для этого. В настоящее время я делаю это в 2 прохода.

Я хотел бы, чтобы он был максимально эффективным, поскольку у меня есть приличный объем данных. Также необходимо динамически перестроить дерево (корнем может быть любой узел)

Ниже приведены примеры данных в программе:

 arry = [{"Id":"1", "Name":"abc", "Parent":""}, {"Id":"2", "Name":"abc", "Parent":"1"},
    {"Id":"3", "Name":"abc", "Parent":"2"},{"Id":"4", "Name":"abc", "Parent":"2"}]//for testing

Я надеялся, что выходные данные будут (это может быть неправильная вложенная структура, как я ее написал вручную. Но я надеюсь, что это допустимая структура JSON с узлом в качестве поля "значение" и дочерними в виде массива.)

{
 "value": {"Id":"1", "Name":"abc", "Parent":""},
 "children": [
  {
   "value": {"Id":"2", "Name":"abc", "Parent":"1"},
   "children": [
    {
     "value": {"Id":"3", "Name":"abc", "Parent":"2"},
     "children": []
     },
     {
     "value": {"Id":"4", "Name":"abc", "Parent":"2"},
     "children": []
     }
   ]
..
}

Пример программы:

function convertToHierarchy(arry, root) 
{
//root can be treated a special case, as the id is known
    arry = [{"Id":"1", "Name":"abc", "Parent":""}, {"Id":"2", "Name":"abc", "Parent":"1"},
    {"Id":"3", "Name":"abc", "Parent":"2"},{"Id":"4", "Name":"abc", "Parent":"2"}]//for testing


    var mapping = {}; // parent : [children]
    for (var i = 0; i < array.length; i++) 
    {
        var node = arry[i];

    if (!mapping[node.Id]) { 
          mapping[node.Id] = {value: node, children:[] } ;
        }else{
      mapping[node.Id] = {value: node} //children is already set    
    }

    if (!mapping[node.Parent]) { //TODO what if parent does not exist.
                mapping[node.Parent] =  {value: undefined, children:[ {value: node,children:[]} ]};
        }else {//parent is already in the list
        mapping[node.Parent].children.push({value: node,children:[]} )
    }

    }
    //by now we will have an index with all nodes and their children.

    //Now, recursively add children for root element.

    var root = mapping[1]  //hardcoded for testing, but a function argument
    recurse(root, root, mapping)
    console.log(root)

    //json dump
}

function recurse(root, node, mapping)
{
    var nodeChildren = mapping[node.value.Id].children;
    root.children.push({value:node.value, children:nodeChildren})
   for (var i = 0; i < nodeChildren.length; i++) {
        recurse(root, nodeChildren[i], mapping);
    }
    return root;
}

Пока у меня есть 3 хороших решения, и надеюсь, что положительные отзывы предложат более идиоматическую и эффективную реализацию. Я не уверен, используя свойство моих данных, что в наборе входного массива будет только один корневой элемент, а также всегда задан корневой элемент, любая из этих реализаций может быть лучше. Я также должен научиться тестировать, так как мое требование - насколько эффективно (быстро/без большого количества памяти) дерево можно перестроить. Например, входные данные уже кэшированы (массив) и перестроить дерево, как

convertToHierarchy(parentid)
....
convertToHierarchy(parentid2)
...

Ответ 1

Здесь одно решение:

var items = [
    {"Id": "1", "Name": "abc", "Parent": "2"},
    {"Id": "2", "Name": "abc", "Parent": ""},
    {"Id": "3", "Name": "abc", "Parent": "5"},
    {"Id": "4", "Name": "abc", "Parent": "2"},
    {"Id": "5", "Name": "abc", "Parent": ""},
    {"Id": "6", "Name": "abc", "Parent": "2"},
    {"Id": "7", "Name": "abc", "Parent": "6"},
    {"Id": "8", "Name": "abc", "Parent": "6"}
];

function buildHierarchy(arry) {

    var roots = [], children = {};

    // find the top level nodes and hash the children based on parent
    for (var i = 0, len = arry.length; i < len; ++i) {
        var item = arry[i],
            p = item.Parent,
            target = !p ? roots : (children[p] || (children[p] = []));

        target.push({ value: item });
    }

    // function to recursively build the tree
    var findChildren = function(parent) {
        if (children[parent.value.Id]) {
            parent.children = children[parent.value.Id];
            for (var i = 0, len = parent.children.length; i < len; ++i) {
                findChildren(parent.children[i]);
            }
        }
    };

    // enumerate through to handle the case where there are multiple roots
    for (var i = 0, len = roots.length; i < len; ++i) {
        findChildren(roots[i]);
    }

    return roots;
}

console.log(buildHierarchy(items));

Ответ 2

Вот еще один. Это должно работать для нескольких корневых узлов:

function convertToHierarchy() { 

    var arry = [{ "Id": "1", "Name": "abc", "Parent": "" }, 
    { "Id": "2", "Name": "abc", "Parent": "1" },
    { "Id": "3", "Name": "abc", "Parent": "2" },
    { "Id": "4", "Name": "abc", "Parent": "2"}];

    var nodeObjects = createStructure(arry);

    for (var i = nodeObjects.length - 1; i >= 0; i--) {
        var currentNode = nodeObjects[i];

        //Skip over root node.
        if (currentNode.value.Parent == "") {
            continue;
        }

        var parent = getParent(currentNode, nodeObjects);

        if (parent == null) {
            continue;
        }

        parent.children.push(currentNode);
        nodeObjects.splice(i, 1);
    }

    //What remains in nodeObjects will be the root nodes.
    return nodeObjects;
}

function createStructure(nodes) {
    var objects = [];

    for (var i = 0; i < nodes.length; i++) {
        objects.push({ value: nodes[i], children: [] });
    }

    return objects;
}

function getParent(child, nodes) {
    var parent = null;

    for (var i = 0; i < nodes.length; i++) {
        if (nodes[i].value.Id == child.value.Parent) {
            return nodes[i];
        }
    }

    return parent;
}

Ответ 3

Я бы сделал что-то вроде этого. Он обрабатывает несколько корневых узлов и является достаточно читаемым IMO.

array = [{"Id":"1", "Name":"abc", "Parent":""}, 
    {"Id":"2", "Name":"abc", "Parent":"1"},
    {"Id":"3", "Name":"abc", "Parent":"2"},
    {"Id":"4", "Name":"abc", "Parent":"2"},
    {"Id":"5", "Name":"abc", "Parent":""},
    {"Id":"6", "Name":"abc", "Parent":"5"}];


function buildHierarchy(source)
{

    Array.prototype.insertChildAtId = function (strId, objChild)
    {
        // Beware, here there be recursion
        found = false;
        for (var i = 0; i < this.length ; i++)
        {
            if (this[i].value.Id == strId)
            {
                // Insert children
                this[i].children.push(objChild);
                return true;
            }
            else if (this[i].children)
            {
                // Has children, recurse!
                found = this[i].children.insertChildAtId(strId, objChild);
                if (found) return true;
            }
        }
        return false;
    };

    // Build the array according to requirements (object in value key, always has children array)
    var target = [];
    for (var i = 0 ; i < array.length ; i++)
        target.push ({ "value": source[i], "children": []});

    i = 0;
    while (target.length>i)
    {
        if (target[i].value.Parent)
        {
            // Call recursion to search for parent id
            target.insertChildAtId(target[i].value.Parent, target[i]); 
            // Remove node from array (it already been inserted at the proper place)
            target.splice(i, 1); 
        }
        else
        {
            // Just skip over root nodes, they're no fun
            i++; 
        }
    }
    return target;
}

console.log(buildHierarchy(array));

Ответ 4

Прочтите этот пост в блоге, чтобы понять, как это работает

Хотя вышеприведенные решения работают, я думаю, что они очень медленные, слишком много циклов и устаревших методов. Я рекомендую использовать приведенное ниже оптимизированное решение, которое даст вам повышение производительности.

const hierarchy = (data = [], { idKey = 'id', parentKey = 'parentId', childrenKey = 'children' } = {}) => {
    const tree = [];
    const childrenOf = {};
    data.forEach((item) => {
        const { [idKey]: id, [parentKey]: parentId = 0 } = item;
        childrenOf[id] = childrenOf[id] || [];
        item[childrenKey] = childrenOf[id];
        parentId ? (childrenOf[parentId] = childrenOf[parentId] || []).push(item) : tree.push(item);
    });
    return tree;
}

Как вы можете видеть в приведенном выше коде, существует только один цикл (.forEach) для всего набора данных!

Теперь для использования в указанном наборе данных:

const arry = [{"Id":"1", "Name":"abc", "Parent":""}, {"Id":"2", "Name":"abc", "Parent":"1"}, {"Id":"3", "Name":"abc", "Parent":"2"},{"Id":"4", "Name":"abc", "Parent":"2"}];


hierarchy(arry, { idKey: 'Id', parentKey: 'Parent' });

Выходные результаты будут выглядеть следующим образом:

"[
    {
        "Id": "1",
        "Name": "abc",
        "Parent": "",
        "children": [
            {
                "Id": "2",
                "Name": "abc",
                "Parent": "1",
                "children": [
                    {
                        "Id": "3",
                        "Name": "abc",
                        "Parent": "2",
                        "children": []
                    },
                    {
                        "Id": "4",
                        "Name": "abc",
                        "Parent": "2",
                        "children": []
                    }
                ]
            }
        ]
    }
]"

Если вы ищете версию без параметров и готовы изменить код, взгляните на следующие версии:

const hierarchy = (data) => {
    const tree = [];
    const childrenOf = {};
    data.forEach((item) => {
        const { Id, Parent } = item;
        childrenOf[Id] = childrenOf[Id] || [];
        item.children = childrenOf[Id];
        Parent ? (childrenOf[Parent] = childrenOf[Parent] || []).push(item) : tree.push(item);
    });
    return tree;
};

Вот некоторые результаты и сравнения между другими постерами

http://jsben.ch/ekTls

LOOP.0
  tree: [], 
  childrenOf: {}, 
  item: {"Id":"1","Name":"abc","Parent":""}
LOOP.1:
  tree: [{"Id":"1","Name":"abc","Parent":"","children":[]}],
  childrenOf: {"1":[]},
  item: {"Id":"2","Name":"abc","Parent":"1"}
LOOP.2: 
  tree: [{"Id":"1","Name":"abc","Parent":"","children":[{"Id":"2","Name":"abc","Parent":"1","children":[]}]}], 
  childrenOf: {
    "1":[{"Id":"2","Name":"abc","Parent":"1","children":[]}],
    "2":[]
  }, 
  item: {"Id":"3","Name":"abc","Parent":"2"}
LOOP.3: 
  tree: [{"Id":"1","Name":"abc","Parent":"","children":[{"Id":"2","Name":"abc","Parent":"1","children":[{"Id":"3","Name":"abc","Parent":"2","children":[]}]}]}], 
  childrenOf: {
    "1":[{"Id":"2","Name":"abc","Parent":"1","children":[{"Id":"3","Name":"abc","Parent":"2","children":[]}]}],
    "2":[{"Id":"3","Name":"abc","Parent":"2","children":[]}],
    "3":[]
  }, 
  item: {"Id":"4","Name":"abc","Parent":"2"}
}

Ответ 5

Реализовано в ES6 с простым вводом образца. Можно протестировать в консоли браузера

let array = [{ id: 'a', children: ['b', 'c'] }, { id: 'b', children: [] }, { id: 'c', children: ['b', 'd'] }, { id: 'd', children: ['b'] }],
  tree = (data) => {
      let nodes = Object.create(null),
          result = {};
      data.forEach((item) => {
        if (!nodes[item.id]) {
          nodes[item.id] = {id: item.id, children: []}
          result = nodes
        }
        item.children.forEach((child) => {
          nodes[child] = {id: child, children: []}
          nodes[item.id].children.push(nodes[child])
        })
      })
      return result
    }

console.log(tree(array))