I need to create a custom tree data-structure using JavaScript

data-structures, javascript, tree

Solution

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 complex. You can add more functions, like GetChildByName, RemoveChild, and so on.

Problem

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

Original source