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

 

Depth first traversal

Now that you have these methods you can write sequences of steps such as;

alert(tree.root());
alert(tree.rightChild());
alert(tree.rightChild());
alert(tree.parent());
alert(tree.leftChild());
alert(tree.rightChild());

Notice that if any of the methods move to a location not within the tree the result is that the returned value is undefined and this can be tested for.

As a final example of how powerful this sort of tree relative approach is let's write a short depth first tree traversal. There are a number of variations on depth first tree traversal algorithms but the simplest and often the most useful is depth-first in preorder which goes:

visit the root
traverse the left sub-tree
traverse the right sub-tree

This can be implemented recursively as:

function traverse(){
alert(tree.getNode());
if(tree.leftChild()!==undefined)traverse();
tree.parent();
if(tree.rightChild()!==undefined)traverse();
tree.parent();
}

Notice that the left and right Child methods actually move to the node in question so you have to use the parent method to "backup" when things go wrong. As with all recursive functions it is almost magical but it works. To try it out use:

tree.root();
traverse();

which for the example tree give earlier displays:

1,2,4,5,3,6,7

Of course there are lots of other methods you can add and there might even be some refactoring to be applied - notice that all of the methods end in the same way.

The full listing is:


function BinaryTree(){
this.Nodes = new Array();
this.level = 0;
this.node = 0;

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

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

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

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

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

this.btSMF = function(level, node){
  return node + (1 << level) - 1;
 }

 

If you would like the code for this project then register and click on CodeBin.

If you would like to be informed about new articles on I Programmer you can either follow us on Twitter, on Facebook , on Digg or you can subscribe to our weekly newsletter.

 See Also:

 

Banner


Just JavaScript - In The Beginning Was The Object

JavaScript is a very subtle and sophisticated language and it deserves to be treated in its own right and not as a poor copy of other object-oriented language. In this first chapter of Just JavaScript [ ... ]



Javascript Jems - Lambda expressions

JavaScript has lambda expressions in all but name. Find out how they work and how to use them.


Other Articles

<ASIN:0137054890>

<ASIN:0596517742>

<ASIN:1590597273> 



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.