Trees Structure - Javascript - Parents?

Question

Simply put

I have a tree structure made of objects.

Is it possible to build that tree and add to each object a reference to their parent ?

I know referencing works with objects, but i'm not sure if it would in that case?

I would like to be able to write something like this

currentLevel = this.getParent();

another exemple would be

this.getChildList().addChild({name: test,parent: this})

Without having copies and creating multiple tree from the first one.

2nd question

How would referencing works with array? Are they considered objects or does it depends on their content?

3nd question

Would saving the tree in the browser's cache, via string-JSON serialisation destroy the references?

Remember Objects are stored ByRef and not ByVal, so you won't create new instances just using an =. — Paul S.
– Paul S., Commented Jun 14, 2013 at 15:04
Actually I have my models done, I can create my tree, but before implementing search function and moving functions ( planned to do it with a stack), I want to check on the referencing part? What code do you need ? — Fawar
– Fawar, Commented Jun 14, 2013 at 15:05
You can't serialise this data structure to JSON by an inbuilt method because it has circular references, you'd have to write your own serealisation. — Paul S.
– Paul S., Commented Jun 14, 2013 at 15:19

Naftali · Accepted Answer · 2013-06-14 16:00:34Z

2

You can do this be creating a "TreeNode" class:

var TreeNode = (function(){

    //keep track of parent node
    TreeNode.prototype.parent = null;
    //keep track of children
    TreeNode.prototype.children = [];

    function TreeNode(parent) {
        if(parent !== undefined) {
            if(this.setParent(parent)) {
                this.parent.addChild(this);
            }
        }
        //...
    }

    TreeNode.prototype.setParent = function(parent) {
        //add some sort of check to make sure it is a `TreeNode`
        if(parent instanceof TreeNode) {
            this.parent = parent;
            return true;
        }
        return false;
    }

    TreeNode.prototype.addChild = function(child) {
        //add some sort of check to make sure it is a `TreeNode`
        if(child instanceof TreeNode) {
            this.children.push(child);
            child.setParent(this);
        }
    }

    TreeNode.prototype.getParent = function(){
        return this.parent;
    }

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

    return TreeNode;

})();

And then you can expand from that.

Example Code:

var node_a = new TreeNode();
var node_b = new TreeNode(node_a);
var node_c = new TreeNode(node_a);

console.log(node_a.getParent(), node_c.get_parent()); //null , node_a        
console.log(node_a.getChildren()); //[node_b, node_c]

This is just a start, it needs waaaaaaaaaay more expansion :-)

edited Jun 14, 2013 at 16:00

answered Jun 14, 2013 at 15:06

Naftali

147k41 gold badges247 silver badges304 bronze badges

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

8 Comments

Paul S. Over a year ago

Node already exists if you're using a browser, it's a bad idea to shadow it.

Fawar Over a year ago

with this structure you would create new node by sending the parent has an argument is that it?

Naftali Over a year ago

@PaulS. I changed the name to TreeNode

Fawar Over a year ago

@Neal, my sentence was not clear enough but with the exemple you added, it's exactly what I asked :) If you add my 2nd question's answer I will accept your answer.

Naftali Over a year ago

@Fawar I added the ability for an element to see all of it's children. :-)

|

Community · Accepted Answer · 2017-05-23 11:44:42Z

Okay, so there are most likely frameworks out there, but I wrote a quick thing which supports JSON serialisation and the reverse (via it's own methods). I took base inspiration from Neal's answer. Example

var a = new MyTreeNode('a'), // make some nodes
    b = new MyTreeNode('b'),
    c = new MyTreeNode('c');

a.addChild(b).addChild(c); // a parent of b parent of c

c.getParent() === b; // true

var str = a.toJSON(); // "{"nodeName":"a","childNodes":[{"nodeName":"b","childNodes":[{"nodeName":"c","childNodes":[]}]}]}"

MyTreeNode.parseJSON(str); // MyTreeNode (same structure as before)

Full code

/* MyTreeNode(String nodeName)
Instance Properties
 - nodeName,   String
 - childNodes, Array of MyTreeNodes
 - parentNode, MyTreeNode
Instance Methods
 - addChild(MyTreeNode node),    child MyTreeNode
 - removeChild(MyTreeNode node), child MyTreeNode
 - getParent,                    parent MyTreeNode
 - getChildList,                 Array of MyTreeNodes
 - serialise,                    JSON-safe Object
 - toJSON,                       String
Constructor Methods
 - deserialise(Object serialised), MyTreeNode
 - parseJSON(String JSONString),   MyTreeNode
*/
var MyTreeNode = (function () {
    function MyTreeNode(nodeName) {
        nodeName && (this.nodeName = nodeName);
        this.childNodes = [];
    }

    MyTreeNode.prototype.parentNode = null;
    MyTreeNode.prototype.childNodes = [];
    MyTreeNode.prototype.nodeName = '';

    // getters
    MyTreeNode.prototype.getChildList = function () {
        return this.childNodes = [];
    };
    MyTreeNode.prototype.getParent = function () {
        return this.parentNode;
    };

    // add/remove
    MyTreeNode.prototype.removeChild = function (node) {
        var i = this.childNodes.indexOf(node);
        if (node.parentNode !== this || i == -1)
            throw new ReferenceError('node is not a child of this');
        this.childNodes.splice(i, 1);
        node.parentNode = null;
        return node;
    };
    MyTreeNode.prototype.addChild = function (node) {
        if (node.parentNode) node.parentNode.removeChild(node);
        node.parentNode = this;
        this.childNodes.push(node);
        return node;
    };

    // JSON
    MyTreeNode.prototype.serialise = function () {
        var o = {
            nodeName: this.nodeName,
            childNodes: []
        }, i;
        for (i = 0; i < this.childNodes.length; ++i) {
            o.childNodes.push(this.childNodes[i].serialise());
        }
        return o;
    };
    MyTreeNode.prototype.toJSON = function () {
        return JSON.stringify(this.serialise());
    };
    MyTreeNode.deserialise = function (o) {
        var p = new MyTreeNode(o.nodeName), i;
        for (i = 0; i < o.childNodes.length; ++i) {
            p.addChild(MyTreeNode.deserialise(o.childNodes[i]));
        }
        return p;
    };
    MyTreeNode.parseJSON = function (str) {
        var o = JSON.parse(str);
        return MyTreeNode.deserialise(o);
    };
    return MyTreeNode;
}());

It seems as if you expanded on my code :-P looks good though :-D
@Neal yup, I wanted to add loads of things way more than a comment could enable

basilikum · Accepted Answer · 2013-06-14 15:31:14Z

You could traverse your object and add parent properties to every subobject:

function addParents(obj) {
    var name;
    for (name in obj) {
        if (typeof obj[name] === "object") {
            addParents(obj[name]);
            obj[name].parent = obj;
        }
    }
}

var obj = {
    g: {
        k: [
            {
                r : 1
            },
            {
                r : 1
            }
        ],
        j: {
            h: 1
        }
    }
};

addParents(obj);

console.log(obj.g.parent === obj); //true
console.log(obj.g.k.parent === obj.g); //true
console.log(obj.g.k[1].parent === obj.g.k); //true
console.log(obj.g.j.parent === obj.g); //true

And if you want to add objects later on, you could use something like this:

function addChild(obj, child, name){
    obj[name] = child;
    child.parent = obj;
}

addChild(obj.g, {t:1}, "xy");

console.log(obj.g.xy.parent === obj.g); //true

FIDDLE

Collectives™ on Stack Overflow

Trees Structure - Javascript - Parents?

3 Answers 3

8 Comments

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

8 Comments

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related