Javascript data structures - the binary tree
Tuesday, 25 January 2011
Article Index
Javascript data structures - the binary tree
Tree relative
Depth first traversal

Tree relative

The implementation given above is very simple but this isn't the way that we usually want to use a tree. Normally tree operations are organised in terms of moving through the tree to the left or right child node of the current node. That is we need to implement some tree operations based on relative locations.

To do this we first need to store a current location in the tree and a way to re-initialise the current location to the root:

this.level=0;
this.node=0;
this.root=function(value){
this.level=0;
this.node=0;
if (value !== undefined) {
  this.Nodes[this.btSMF(this.level,
                      this.node)]=value;
}
return this.Nodes[this.btSMF(this.level,
                              this.node)];
}

The root function is a little more tricky than it needs to be because it does a little more. You can use it as a command;

tree.root();

to set the current position to the root. It also returns the value at the root;

rootvalue=tree.root();

and it can be used to set the value at the root:

tree.root(100);

This is a good way to write a function that does all of the jobs you need and the pattern will be used for other tree relative functions.

After a root function we need a leftChild and a rightChild function. The only problem here is working out how to change the current position in terms of level and node into the left or right child position in the same terms. A few moments thinking you should be able to see that if the current node is at level, node the left child is at level+1, node*2. This makes leftChild easy to write:

this.leftChild=function(value){
this.level++;
this.node=this.node*2;
if (value !== undefined) {
  this.Nodes[this.btSMF(this.level,
                       this.node)]=value;
}
return this.Nodes[this.btSMF(this.level,
                              this.node)];
}

And if you know that leftChild is at level+1, node*2 then right child has to be at level+1,node*2+1:

this.rightChild=function(value){
this.level++;
this.node=this.node*2+1;
if (value !== undefined) {
  this.Nodes[this.btSMF(this.level,
                        this.node)]=value;
}
return this.Nodes[this.btSMF(this.level,
                              this.node)];
}

Now you have enough methods to walk the tree in a number of different ways. However it would be nice to have a parent function that moves the location to the parent node of the current node. Again this is just a matter of working out how to change the current level and node values. Again it should be obvious that the parent is at level-1, node/2 where the division is integer division. It is easier to use the right shift to implement integer division so we have:

this.parent=function(value){
this.level--;
this.node=this.node>>1;
if (value !== undefined) {
  this.Nodes[this.btSMF(this.level,
                        this.node)]=value;
}
return this.Nodes[this.btSMF(this.level,
                              this.node)];
}

New Set and Get

Now we really do have all we need - but perhaps the set and get functions could do with a small update so that they set or get the current position if a position isn't specified:

this.setNode=function(value,level,node){
 if(level===undefined){
  this.Nodes[this.btSMF(this.level,
                        this.node)]=value;    
 }else{
  this.Nodes[this.btSMF(level,
                             node)]=value;
}
}

this.getNode=function(level,node){
 if (level === undefined) {
  return this.Nodes[this.btSMF(this.level,
                              this.node)];
}else {
  return this.Nodes[this.btSMF(level,
                                   node)];
}
}
 

Banner

<ASIN:0596517742>
<ASIN:0596805527>
<ASIN:0470684143>



Last Updated ( Tuesday, 15 January 2013 )
 
 

   
RSS feed of all content
I Programmer - full contents
Copyright © 2014 i-programmer.info. All Rights Reserved.
Joomla! is Free Software released under the GNU/GPL License.