Create tree from js array

Question

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

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

                      });

   };

Javascript != Java, and it says that in countless places on this website. — Rabbit Guy
– Rabbit Guy, Commented May 20, 2016 at 15:55
please supply some data which are not invalid (tree wise), or create a loop. please use unique identifier. — Nina Scholz
– Nina Scholz, Commented May 20, 2016 at 16:29

Nina Scholz · Accepted Answer · 2016-05-21 20:39:39Z

3

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.

edited May 21, 2016 at 20:39

answered May 21, 2016 at 18:06

Nina Scholz

388k26 gold badges367 silver badges417 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Redu Over a year ago

I see that you are not satisfied with the console.log() and started using a cooler display method for the nested thingys. (+) for your solutions.

Nina Scholz Over a year ago

@Redu, yes, the area is to small to show bigger data structure.

Redu · Accepted Answer · 2016-05-24 08:53:26Z

For this use cases i had invented very useful two Object methods; namely Object.prototype.getNestedValue() and Object.prototype.setNestedValue(). By utilizing these methods this job is nothing more than a single liner JS code. See below...

Object.prototype.getNestedValue = function(...a) {
  return a.length > 1 ? (this[a[0]] !== void 0 && this[a[0]].getNestedValue(...a.slice(1))) : this[a[0]];
};
Object.prototype.setNestedValue = function(...a) {
  return a.length > 2 ? typeof this[a[0]] === "object" && this[a[0]] !== null ? this[a[0]].setNestedValue(...a.slice(1))
                                                                              : (this[a[0]] = typeof a[1] === "string" ? {} : new Array(a[1]),
                                                                                 this[a[0]].setNestedValue(...a.slice(1)))
                      : this[a[0]] = a[1];
};

var data = "A-->B-->C-->D-->E\nA-->B-->C-->D-->F\nA-->F-->C-->D-->E",
  datarr = data.split("\n").map(e => e.split("-->")), // get your list in an array
       o = {};
datarr.forEach(a => !o.getNestedValue(...a) && o.setNestedValue(...a,null));

console.log(JSON.stringify(o,null,2));

Collectives™ on Stack Overflow

Create tree from js array

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related