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

Question

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

Have you tried your code?

Evan Davis
– Evan Davis

2013-07-19 16:06:45 +00:00
Commented Jul 19, 2013 at 16:06 — Evan Davis
– Evan Davis, Commented Jul 19, 2013 at 16:06

Mongolojdo · Accepted Answer · 2013-07-19 16:48:39Z

7

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.

edited Jul 19, 2013 at 16:48

answered Jul 19, 2013 at 16:36

Mongolojdo

986 bronze badges

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

2 Comments

jaypowers Over a year ago

I realize I could put 2 children in a linked list, do you have any suggestions on how to traverse a multi-child list?

Mongolojdo Over a year ago

The code above would let you traverse unlimited number of children. Each child could have unlimited number of grand children, and so on. Try it out. The code pattern is called Linked List.

vivekfyi · Accepted Answer · 2015-07-13 07:38:27Z

2

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

answered Jul 13, 2015 at 7:38

vivekfyi

2,5151 gold badge27 silver badges30 bronze badges

Comments

Smrchy · Accepted Answer · 2013-10-31 18:10:00Z

1

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/

answered Oct 31, 2013 at 18:10

Smrchy

831 silver badge4 bronze badges

1 Comment

Steve Westbrook Over a year ago

Could you add a description of how the linked approach solves the problem?

Splendiferous · Accepted Answer · 2013-07-19 16:34:43Z

0

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.

answered Jul 19, 2013 at 16:34

Splendiferous

7632 gold badges6 silver badges17 bronze badges

1 Comment

jaypowers Over a year ago

thank you, I did find this as well drdobbs.com/database/ternary-search-trees/184410528

Collectives™ on Stack Overflow

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

4 Answers 4

2 Comments

Comments

1 Comment

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

2 Comments

Comments

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related