Javascript дерево построения иерархии

Question

var array = [{"grandpa","father"}, {"father"}, {"grandpa","father","me"}];

Учитывая приведенный выше массив, я хочу создать объект java-script (JSON), как показано ниже, который имеет структуру типа parent-child.

{"id":"grandpa",
 "children":[
    {"id":"father",
     "children":[
        {"id":"me",
         "children":[]
        }]
    }]
}

Answer 1

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

function convertToHierarchy(arry /* array of array of strings */) 
{
    var item, path;

    // Discard duplicates and set up parent/child relationships
    var children = {};
    var hasParent = {};
    for (var i = 0; i < arry.length; i++) 
    {
        var path = arry[i];
        var parent = null;
        for (var j = 0; j < path.length; j++) 
        {
            var item = path[j];
            if (!children[item]) {
                children[item] = {};
            }
            if (parent) {
                children[parent][item] = true; /* dummy value */
                hasParent[item] = true;
            }
            parent = item;
        }
    }

    // Now build the hierarchy
    var result = [];
    for (item in children) {
        if (!hasParent[item]) {
            result.push(buildNodeRecursive(item, children));
        }
    }
    return result;
}

function buildNodeRecursive(item, children)
{
    var node = {id:item, children:[]};
    for (var child in children[item]) {
        node.children.push(buildNodeRecursive(child, children));
    }
    return node;
}

convertToHierarchy([["1","2"], ["1"], ["1","2","3"]]);

Edit:

Ваш вопрос все еще неоднозначен. Моя предыдущая версия предполагала эти две вещи:

1. Каждый идентификатор узла однозначно идентифицирует узел
2. Указанный путь иерархии может начинаться не с корневого узла

В этом примере я предполагаю следующее:

1. Идентификаторы узлов не являются уникальными, но они уникальны в пределах потомков определенного узла
2. Все пути иерархии начинаются с корневого узла дерева

Вот код:

function convertToHierarchy(arry /* array of array of strings */)
{
    // Build the node structure
    var rootNode = {id:"root", children:{}}
    for (var i = 0; i < arry.length; i++)
    {
        var path = arry[i];
        buildNodeRecursive(rootNode, path, 0);
    }
    return rootNode;
}

function buildNodeRecursive(node, path, idx)
{
    if (idx < path.length)
    {
        item = path[idx];
        if (!node.children[item])
        {
            node.children[item] = {id:item, children:{}};
        }
        buildNodeRecursive(node.children[item], path, idx + 1);
    }
}

Возвращается иерархическая структура, но формат немного другой. Тем не менее, вы должны получить картину.

Answer 2

Я думаю, что это должно работать. Я использую Firebug для отслеживания структуры вывода.

    var el =  {"name": "Level 1", "paths" : ["fruits"]};
    var el2 = {"name": "Level 3", "paths" : ["fruits", "apples", "fuji"]};
    var el3 = {"name": "Level 4", "paths" : ["fruits", "apples", "fuji", "red"]};
    var el4 = {"name": "Level 2", "paths" : ["fruits", "apples"]};

    var allEl = [el, el2, el3, el4];


    /* Define recursive function for setting the child */
    function setChild(parent, pos, arr, name)
    {
        if(pos < arr.length)
        {
            if(pos == arr.length-1) //last element of the paths
                parent.name = name;

            if(!parent.children){
                parent.children = [];
                parent.children[0] = new Object();
            }
            setChild(parent.children[0], pos + 1, arr, name);
        }
    }

    /* Test starts here */
    var root = new Object();

    for(var i=0; i<allEl.length; i++)
    {
        var el = allEl[i];
        setChild(root, 0, el.paths, el.name);
    }

    //Firefox debugging ...getfirebug.com
    console.debug(root);

Answer 3

Если вы хотите кодировать JSON, просто используйте библиотеку JSON.

Не пытайтесь свернуть свое собственное.