Tree-Relative

The implementation given above is very simple but this isn't the way that we usually want to use a tree. You don't normally specify that level and node number of the data you want to store or retrieve.  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 this 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 really 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).

What we are doing here is converting the more familiar way of specifying nodes i.e. giving a current node and then referencing its immediate left or right child node, into SMF form.

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

Where we have used the same form for the function as for root so that it can be used to set the current position and/or get/set the value.

And if you know that leftChild is at (level+1, node*2) then right child has to be at level+1,node*2+1, because it is just one node along to the right from the left node. 

This makes rightChild equally easy to write:

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 of the node at (level,node) 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)];
 }
}



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

This starts from the root, moves to the right child of the root. Then to the its rightChild and then back to its parent i.e. the right child of the root. Finally we move to the left child of the root and then its right child. 

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.

Depth first traversal

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.

It is worth stating again that the storage mapping function approach to binary trees isn't the most commonly encountered method. It is more usual to use pointers or a linked list type structure to build the tree dynamically so that it only uses storage for nodes that have something stored. 

<ASIN:1871962625>

<ASIN:1871962560>

<ASIN:1871962579>

<ASIN:1871962501>

<ASIN:1871962528>

<ASIN:1871962420>