//**************************************
//
// Name: ordered binary tree
// Description:JavaScript is slow and th
// e more speed you can get out of it the b
// etter. Ever have an array, which you nee
// ded to sort or have a list of items you
// wanted to sort quickly. Bubble sorts do
// the job but do you find yourself waiting
// for the sort to happen. This script may
// help you speed up your sorts. Ordered Bi
// nary trees are said to be one of the fas
// test way to sort data. Here is a simple
// implementation of one for you. You can u
// se it as is or improve on it. Have fun!
Eric Repec
// By: Eric Repec InetSolution
//
// Inputs:Currently this implementation
// only supports the input of strings. Howe
// ver, you can place any type of data into
// this structure with a bit of coding. Ple
// ase see my incode comments for help.
//
// Returns:binary tree.
//
//This code is copyrighted and has// limited warranties.Please see http://
// www.Planet-Source-Code.com/vb/scripts/Sh
// owCode.asp?txtCodeId=3240&lngWId;=2//for details.//**************************************
//
<HTML>
<HEAD>
<META NAME="GENERATOR" Content="Microsoft Visual Studio 6.0">
<SCRIPT LANGUAGE=JAVASCRIPT>
var oCurr; // temp object to hold our current pointer.
var t = new tree("t"); // Lets get started by creating our tree with one value.
// manually add a few nodes.
t.addSorted("a");
t.addSorted("y");
t.addSorted("z");
t.addSorted("g");
t.addSorted("q");
t.addSorted("r");
t.addSorted("s");
// show the user what our sorted list lo
// oks like
alert(t.sortedList());
// another way to iterate through the da
// ta..
oCurr = t.getFirst();
alert(oCurr.value);
oCurr = oCurr.getNextSorted();
alert(oCurr.value);
oCurr = oCurr.getNextSorted();
alert(oCurr.value);
oCurr = oCurr.getNextSorted();
alert(oCurr.value);
oCurr = oCurr.getNextSorted();
alert(oCurr.value);
oCurr = oCurr.getNextSorted();
alert(oCurr.value);
oCurr = oCurr.getNextSorted();
alert(oCurr.value);
// OK now lets play with arrays.
var a = new Array("r","g","f","q","h","y","z","a","b","e","u","w","b","m","x","p","k");
// create our tree and make the first no
// de equal to the first item in the array.
//
var t2 = new tree(a[0])
// loop through all the data in the arra
// y and add them to the tree.
for(var i = 1;i < a.length;i++)
t2.addSorted(a[i]);
// OK now we can pull the array back out
// and it is sorted.
a = t2.sortedArray();
// lets build the array into a string so
// we can see it.
var string = "";
for(var i=0;i < a.length;i++)
string += a[i];
alert("array dump = " + string);
function tree(value)
{
this.value = value;
this.parent;
this.left;
this.right;
// this will traverse the tree and find a sutable spot for the next node. It will evaluate the value being passed.
// if you wish to use something other then strings you will have to change the if statement below to properly evaluate
// your type of data.
this.addSorted = function(value)
{
// this is where we are making the determination of where to add this node to the tree.
// you can change this evaluation to match your data type.
if(value < this.value)
{
if(this.left == null)
{
// add the value to the left of the current node
return this.addLeft(value);
}else
{
// recursively call addSort on the left node
return this.left.addSorted(value);
}
}else
{
if(this.right == null)
{
// add the value to the right of the current node
return this.addRight(value);
}else
{
// recursively call addSort on the right node
return this.right.addSorted(value);
}
}
}
// helper function to add a left child node.
this.addLeft = function(value)
{
this.left = new tree(value);
this.left.parent = this;
return this.left;
}
// helper function to add a right child node.
this.addRight = function(value)
{
this.right = new tree(value);
this.right.parent = this;
return this.right;
}
// output a string of sorted values. this function can be changed to support your type of object.
this.sortedList = function()
{
var string = "";
string = this.value;
if(this.left != null)
string = this.left.sortedList() + "," + string;
if(this.right != null)
string += "," + this.right.sortedList();
return string;
}
// this will return the first sorted node in the tree node.
this.getFirst = function getFirst()
{
var curr = this;
while(curr.left != null)
curr = curr.left;
return curr;
}
// this will return the next node in a sorted list by using just the tree object.
// this is a bit messy because I choose not to use recursion to implement this function.
this.getNextSorted = function()
{
// check to see if we have a right node
if(this.right != null)
return this.right.getFirst();
// check to see if we are the left node of a parent
if(this.parent != null)
if(this.parent.left == this)
return this.parent;
else
{
var curr = this;
while(curr.parent.right == curr)
{
curr = curr.parent;
if(curr.parent == null)
return null;
}
return curr.parent;
}
}
// this function will use the getNextSorted() function to build an array of sorted items
this.sortedArray = function()
{
var a = new Array();
var curr = this.getFirst();
var i = 0;
while(curr != null)
{
a[i++] = curr.value;
curr = curr.getNextSorted();
}
return a;
}
}
</SCRIPT>
<TITLE></TITLE>
</HEAD>
<BODY>
<P> </P>
</BODY>
</HTML> |
