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:

• JavaScript Data Structures - the String Object
• JavaScript Data Structures - the Array object
• Speed dating - the art of the JavaScript Date object
• Javascript data structures - a Collection Object
• Javascript data structures - Stacks
• JavaScript Data Structures - The Linked List
• JavaScript data structures - a Lisp-like list
• Javascript data structures - The Binary Tree

<ASIN:0137054890>

<ASIN:0596517742>

<ASIN:1590597273>