Generic tree implementation in Javascript

Question

Is anyone aware of a generic tree (nodes may have multiple children) implementation for JavaScript?

It should be able to do atleast these things,

1. get parent node.
2. get children nodes.
3. get all the descendants.
4. remove all the descendants.
5. remove children nodes.

Some implementation similar to Adjacency List Model.

Background: I needed JavaScript based hierarchical data storing for my webpage i could not find a good JavaScript implementation of generic trees so what i did is i used ajax to store hierarchical data into database using Adjacency List Model and php. The problem comes when the user is opening the same page in two tabs of same browser or opened the page in two different browsers because both the instances are writing to same table reading from same table which is causing me problems any possible work around for this also answers my question.

Edit: Performance is really not my constraint at any point of time i will not have more than 50 entries.

Answer 1

You can try this: https://github.com/afiore/arboreal

Or this: https://github.com/mauriciosantos/buckets/ (only Binary Searched Trees, but olso other data structures)

If you need anything more sophisticated, you will need to write your own library (or at least one object with all methods you desribed).

EDIT:

This is my simple code to achieve tree functionality. Remove all descendants and remove all children is in fact the same... so:

function Node(value) {

    this.value = value;
    this.children = [];
    this.parent = null;

    this.setParentNode = function(node) {
        this.parent = node;
    }

    this.getParentNode = function() {
        return this.parent;
    }

    this.addChild = function(node) {
        node.setParentNode(this);
        this.children[this.children.length] = node;
    }

    this.getChildren = function() {
        return this.children;
    }

    this.removeChildren = function() {
        this.children = [];
    }
}

var root = new Node('root');
root.addChild(new Node('child 0'));
root.addChild(new Node('child 1'));
var children = root.getChildren();
for(var i = 0; i < children.length; i++) {
    for(var j = 0; j < 5; j++) {
        children[i].addChild(new Node('second level child ' + j));
    }
}
console.log(root);
children[0].removeChildren();
console.log(root);
console.log(root.getParentNode());
console.log(children[1].getParentNode());

Run it in Chrome (or other browser which supports console).

Answer 2

Although you did say "generic tree", what your specific requirement sounds simple enough for an already built-in DOMParser.

I respect other programmers' opinions, but still I think you can give DOM a try and see if it fits you.

Here's an simple illustration on how it works:

var tXML="<root><fruit><name>apple</name><color>red</color></fruit><fruit><name>pear</name><color>yellow</color></fruit></root>";
var tree=(new DOMParser).parseFromString(tXML,"text/xml");
//get descendants
var childs=tree.documentElement.childNodes;
for(var i=0;i<childs.length;i++)
{
 if(childs[i].nodeName=="fruit")
 {
  document.write(childs[i].getElementsByTagName("name")[0].textContent);
  document.write(": ");
  document.write(childs[i].getElementsByTagName("color")[0].textContent);
  document.write("<br />");
 }
}
//get child node
var appl=tree.documentElement.getElementsByTagName("fruit")[0];
document.write(appl.getElementsByTagName("name")[0].textContent+"<br />");
//get parent node
document.write(appl.parentNode.nodeName);
document.write("<br />");
//remove child node
if(tree.documentElement.getElementsByTagName("color").length>1)
{
 var clr=tree.documentElement.getElementsByTagName("color")[1];
 clr.parentNode.removeChild(clr);
}
document.write("<textarea>"+(new XMLSerializer).serializeToString(tree)+"</textarea><br />");
//remove descendants
while(tree.documentElement.childNodes.length>0)
{
 tree.documentElement.removeChild(tree.documentElement.childNodes[0]);
}
document.write("<textarea>"+(new XMLSerializer).serializeToString(tree)+"</textarea>");

I didn't "simplified" those long function names, so you may get a better idea.