s.aslan s.aslan - 6 months ago 38
Javascript Question

Create tree from js array

I'm trying to create tree from a list . My data is like ;

A-->B-->C-->D-->E..
A-->B-->C-->D-->F..
A-->F-->C-->D-->E..
.
.
.


I have all possible data path in array.I want to show this like

A
-B
-C
-D
-E
-F
-F
-C
-D
-E


How can i create and check with javascript ? I need createTreeFunction :)

function parseData(data)
{


$.each(data, function (i, p) {
var arr = p.split("--->");

createTreeFunction(p);

});

};
function parseData(data)
{


$.each(data, function (i, p) {
var arr = p.split("--->");

createTreeFunction(p);

});

};

Answer

Basically you can use at least two different structures for the children for building a tree, one with an array (Solution A) or with an object (Solution B).

The advantage of an array over an object is the direct iteration over the children. With an object, you need to get the keys first and then is an iteration possible.

Otherwise if you know one child, then the access over the key is faster. This is also true for inserting new nodes to the tree.

With a children array you need a function getChild for testing if a child is present.

A note, the supplied data does not keep the identifier unique.

Solution A with arrays for children:

function Node(id) {
    this.id = id;
    this.children = []; // array
}

Node.prototype.getChild = function (id) {
    var node;
    this.children.some(function (n) {
        if (n.id === id) {
            node = n;
            return true;
        }
    });
    return node;
};

var path = ['A-->B-->C-->D-->E', 'A-->B-->C-->D-->F', 'A-->F-->C-->D-->E'],
    tree = new Node('root');

path.forEach(function (a) {
    var parts = a.split('-->');
    parts.reduce(function (r, b) {
        var node = r.getChild(b);
        if (!node) {
            node = new Node(b);
            r.children.push(node);
        }
        return node;
    }, tree);
});

document.getElementById('out').innerHTML = JSON.stringify(tree, 0, 4);
<pre id="out"></pre>

Solution B with objects for children:

function Node(id) {
    this.id = id;
    this.children = {}; // object
}

var path = ['A-->B-->C-->D-->E', 'A-->B-->C-->D-->F', 'A-->F-->C-->D-->E'],
    tree = new Node('root');

path.forEach(function (a) {
    var parts = a.split('-->');
    parts.reduce(function (r, b) {
        if (!r.children[b]) {
            r.children[b] = new Node(b);
        }
        return r.children[b];
    }, tree);
});

document.getElementById('out').innerHTML = JSON.stringify(tree, 0, 4);
<pre id="out"></pre>

Both proposals uses Array#forEach and Array#reduce for iterating the given strings and for returning the reference to the actual id. If an id is not found, a new instance of node is taken and added to the array or object. The reference is returned for the next id check.