Sorted Binary Tree
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142
function BinaryNode(v, compareFunction ){
this._value = v;
this._leftNode = null;
this._rightNode = null;
this.comparator = compareFunction || function( a, b ){
if( typeof a === typeof b ){
if( typeof a === "string" ){
if( a == b ){
return 0;
} else if( a > b ){
return 1;
} else if( a < b ){
return -1;
}
} else if( typeof a === "number" ){
return a - b;
} else {
return 0;
}
} else {
return 0;
}
};
}
BinaryNode.prototype = {
get value(){
return this._value;
},
set value(v){
if( v ){
this._value = v;
}
},
get leftNode(){
return this._leftNode;
},
set leftNode(node){
if( node instanceof BinaryNode ){
this._leftNode = node;
}
},
get rightNode(){
return this._rightNode;
},
set rightNode(node){
if( node instanceof BinaryNode ){
this._rightNode = node;
}
},
isLeaf(){
return !this._leftNode && !this._rightNode;
},
addToLeft(node){
if( node instanceof BinaryNode ){
if( this._leftNode ){
this._leftNode.addNode(node);
} else {
console.log( "Grafted ", node.value, " to left" );
this._leftNode = node;
}
}
},
addToRight(node){
if( node instanceof BinaryNode ){
if( this._rightNode ){
this._rightNode.addNode(node);
} else {
console.log( "Grafted ", node.value, " to right" );
this._rightNode = node;
}
}
},
addNode(node){
if( node instanceof BinaryNode ){
var compareValue = this.comparator( this.value, node.value );
if( compareValue < 0 ){
console.log( "Add ", node.value, " to left" );
this.addToLeft(node);
} else {
console.log( "Add ", node.value, " to right" );
this.addToRight(node);
}
}
}
}
function BinaryTree( compareFunction ){
this.root = null;
this.comparator = compareFunction || null;
}
BinaryTree.prototype = {
add(value){
if( typeof value !== "undefined" && value !== null ){
console.log( "Adding ", value );
if( this.root ){
var newNode = new BinaryNode(value, this.comparator);
this.root.addNode(newNode);
} else {
console.log( "Add ", value, " to root" );
this.root = new BinaryNode(value, this.comparator);
}
}
},
};
var tree = new BinaryTree();
var testArray = [ 0, 99, 3, 55, 15, 2, 50, 100, 6 ];
for( var i = 0; i < testArray.length; i++ ){
tree.add(testArray[i]);
}
function traverseLeft( node, func ){
if( node ){
if( node.isLeaf() ){
func(node.value);
} else {
traverseLeft(node.leftNode, func );
func(node.value);
traverseLeft(node.rightNode, func );
}
}
}
function traverseRight( node, func ){
if( node ){
if( node.isLeaf() ){
func(node.value);
} else {
traverseRight(node.rightNode, func);
func(node.value);
traverseRight(node.leftNode, func );
}
}
}
traverseLeft(tree.root, (x)=>console.log(x) );
console.log( " === " );
traverseRight(tree.root, (x)=>console.log(x) );
JavaScript
INFO