I need to create a custom tree data structure using JavaScript

Question

I looked at 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 to create a tree that is “long” with this. The data I use is a list of streets on the trail, which is almost one straight path, but there are a few small gaps in the trail, the data will look something like this:

 A -> B -> C -> D -> E,FE -> G -> HF -> II -> JJ -> K,LK -> M -> N L -> O O -> P 

I would like to avoid code that looks like this:

 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 get through the tree, simply saying:

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

If you could help me, I would appreciate it, thanks,

mathacka

Answer 1

The most manageable approach for this structure is IMHO for using 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 iterate over children, follow these steps:

 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 the basis for all the objects in your tree, it can have any depth without making it more complicated. You can add more features like GetChildByName, RemoveChild, etc.

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

Answer 3

Take 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/

Answer 4

If you want to do some calculations on each node in the tree, then you can add the traverse function to your tree nodes, for example:

 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 are doing something more specific, such as manipulating a tree or searching for a specific node, then you can see the visitor design template .