I looked up this basic format for a tree structure in javascript:

function Tree(parent, child, data) {
    this.parent = parent;
    this.children = child || [];
    this.data = data;
    this.addNode ...
    this.addChild ...
}

the problem I have is making a tree that is "long" with this. The data I'm using is a list of streets on a trail that is almost one straight path, but there are a couple of small splits in the trail, the data would look something like:

A -> 
B -> 
C -> 
D -> E,F   
E -> 
G -> 
H    
F -> I  
I -> J  
J -> K,L   
K ->
M -> 
N
L -> O
O -> P

I'd like to avoid code that looks like:

tree.children[0].children[0].children[0].addNode("E");
tree.children[0].children[0].children[0].push("F");

so one of my questions is how to traverse the tree, simply by saying?

node = tree;
while(node.children != null)
    node = node.children[0];

if you could help me out, I'd appreciate it, thanks,

mathacka

I looked up this basic format for a tree structure in javascript:

function Tree(parent, child, data) {
    this.parent = parent;
    this.children = child || [];
    this.data = data;
    this.addNode ...
    this.addChild ...
}

the problem I have is making a tree that is "long" with this. The data I'm using is a list of streets on a trail that is almost one straight path, but there are a couple of small splits in the trail, the data would look something like:

A -> 
B -> 
C -> 
D -> E,F   
E -> 
G -> 
H    
F -> I  
I -> J  
J -> K,L   
K ->
M -> 
N
L -> O
O -> P

I'd like to avoid code that looks like:

tree.children[0].children[0].children[0].addNode("E");
tree.children[0].children[0].children[0].push("F");

so one of my questions is how to traverse the tree, simply by saying?

node = tree;
while(node.children != null)
    node = node.children[0];

if you could help me out, I'd appreciate it, thanks,

mathacka

• javascript
• data-structures
• tree

• Have you tried your code? – Evan Davis Commented Jul 19, 2013 at 16:06

4 Answers 4

The most managable approach for this structure is IMHO to use linked lists.

function Node(parentNode)
{
    this.Parent=parentNode;
    this.FirstChild=null;
    this.LastChild=null;
    this.PreviousSibling=null;
    this.NextSibling=null;
}
Node.prototype.AddChild=function(child)
{
    child.Parent = this;
    child.PreviousSibling = this.LastChild;
    if (this.LastChild != null)
        this.LastChild.NextSibling = child;
    this.LastChild = child;
    if (this.FirstChild == null)
        this.FirstChild = child;
}

To loop through children, do something like this:

function GetChildren(node)
{
    var result=new Array();
    var child=node.FirstChild;
    while(child)
    {
        result.push(child);
        child=child.NextSibling;
    }
    return result;
}

(edit) The "Node"-object is just an example and it should have meaningful properties added to it. Using this as a base for all objects in your tree, it may have any depth without making it more plex. You can add more functions, like GetChildByName, RemoveChild, and so on.

var Tree = function () {
    Tree.obj = {};
    return Tree;
};

// Parent Will be object
Tree.AddChild = function (parent, child) {

    if (parent === null) {
        if (Tree.obj.hasOwnProperty(child)) {
            return Tree.obj[child];
        } else {
            Tree.obj[child] = {};
            return Tree.obj[child];
        }
    } else {
        parent[child] = {};
        return parent[child];
    }
};


// Uses

// Inserting - 
var t = Tree();
var twoDoor = t.AddChild(null, "2 Door");
var fdoor = t.AddChild(null, "4 Door");
t.AddChild(fdoor, "manual");
t.AddChild(twoDoor, "automatic");
var man = t.AddChild(twoDoor, "manual");
t.AddChild(man, "Extended Cab");
console.log(t.obj);

Have a look at this approach on how to create tree structures from SQL queries:

http://blog.tcs.de/creating-trees-from-sql-queries-in-javascript/

If you want to do some calculation at every node in the tree then you could add a traverse function to your tree nodes, something like:

Tree.prototype.traverse = function( operation ){
    // call the operation function and pass in the current node
    operation( this )

    // call traverse on every child of this node
    for( var i=0; i<this.children.length; i++ )
        this.children[i].traverse( operation )
}

// an example operation that finds all the leaf nodes
var leaves = []
myTree.traverse( function( node ){
    if( !node.children.length )
        leaves.push(node)
}

Alternatively if you're doing something more specific such as manipulating the tree or finding a particular node then you may want to look at the Visitor Design Pattern.