Ordered Binary Tree - Sorting Traversal
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596
function OrderedBinaryTree(value){
this.value = value || null;
this.left = null;
this.right = null;
}
OrderedBinaryTree.prototype.addRight = function(value){
if( this.right ){
this.right.addNode(value);
} else {
this.right = new OrderedBinaryTree(value);
}
};
OrderedBinaryTree.prototype.addLeft = function(value){
if( this.left ){
this.left.addNode(value);
} else {
this.left = new OrderedBinaryTree(value);
}
};
OrderedBinaryTree.prototype.addNode = function(value){
if( this.value ){
if( typeof value === "number" ){
if( value > this.value ){
this.addRight(value);
} else {
this.addLeft(value);
}
} else {
this.addLeft(value);
}
} else {
//Root Node
if( this.isLeaf() ){
this.addLeft(value);
} else {
if( this.left && this.right ){
if( value > this.left.value ){
this.addRight(value);
} else {
this.addLeft(value);
}
}
else if( !this.right ){
this.addRight(value);
} else {
this.addLeft(value);
}
}
}
}
OrderedBinaryTree.prototype.isLeaf = function(){
return !this.left && !this.right;
}
var root = new OrderedBinaryTree(null);
var sortTarget = [1, 9, 2, 50, 100, 34, 3 ];
for( var i in sortTarget ){
root.addNode(sortTarget[i]);
}
function accumulator( prev, current ){
prev = prev || [];
if( current ){
prev.push(current);
}return prev;
}
function traverse( node, accumulator, prev, ascending ){
ascending = ( typeof ascending !== "undefined" )? ascending : true;
if( node ){
if( node.isLeaf() ){
return accumulator( prev, node.value );
} else {
var traversalPreference = [node.left, node.right];
if(!ascending){
traversalPreference = [node.right, node.left];
}
prev = traverse(traversalPreference[0],accumulator, prev, ascending );
prev = accumulator(prev, node.value);
prev = traverse(traversalPreference[1],accumulator, prev, ascending );
return prev;
}
} else {
return prev;
}
}
console.log( "Target Array : ", sortTarget );
console.log( "Sorted Array (ascending) : ", traverse(root,accumulator) );
console.log( "Sorted Array (descending): ", traverse(root,accumulator, [], false) );
JavaScript
INFO