Javascript building tree hierarchy - Stack Overflow

admin管理员组

文章数量:1312982

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

Given the above array, I want to product a java-script object(JSON) like below, that has the parent-child like structure.

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

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

Given the above array, I want to product a java-script object(JSON) like below, that has the parent-child like structure.

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

• javascript
• tree

Share Improve this question Follow edited Feb 18, 2010 at 4:49 Jacob 78.9k2424 gold badges156156 silver badges241241 bronze badges asked Feb 18, 2010 at 3:07 user275031user275031 16122 gold badges22 silver badges66 bronze badges 8

• Produce the javascript object based on the array – user275031 Commented Feb 18, 2010 at 3:12
• If you can't enunciate the problem clearly, it's going to be hard for us to help you to solve it. Are you trying to decode JSON? – Anon. Commented Feb 18, 2010 at 3:13
• 1 "[B]ased on the array": in what sense? How is the input related to the output? – Marcel Korpel Commented Feb 18, 2010 at 3:17
• The array is still invalid syntax. – SLaks Commented Feb 18, 2010 at 3:26
• Give a better description. Don't use so many of the same numbers, it makes it difficult for us to tell what is what. Try using non ambiguous words instead of numbers. Maybe even words that have natural hierarchy, like fruits => apples, oranges. Provide a valid javascript array. – goat Commented Feb 18, 2010 at 3:26

 |  Show 3 more ments

3 Answers 3

Sorted by: Reset to default 8

If you're asking how you would take a list of hierarchy paths and create a tree structure, here's how you could do it in 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:

Your question is still ambiguous. My previous version assumed these two things:

1. Each node ID uniquely identifies a node
2. A specified hierarchy path can start at other than the root node

In this sample, I'll assume the following:

1. Node IDs are not unique, but they are unique within the children of a particular node
2. All hierarchy paths start at the root node of the tree

Here's the code:

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

The hierarchy structure is returned, but the format's a bit different. However, you should get the picture.

I think this should work. I'm using firebug to track the structure of the output.

    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.
    console.debug(root);

If you want to encode JSON, just use a JSON library.

Don't try and roll your own.

本文标签： Javascript building tree hierarchyStack Overflow