Skip to content

Instantly share code, notes, and snippets.

@thinkphp
Created December 9, 2011 08:57
Show Gist options
  • Save thinkphp/1450799 to your computer and use it in GitHub Desktop.
Save thinkphp/1450799 to your computer and use it in GitHub Desktop.
Binary Search Tree implementation in pure JavaScript
/**
* by Adrian Statescu <[email protected]>
* Twitter: @thinkphp
* G+ : http://gplus.to/thinkphp
* MIT Style License
*/
function Node(info){
this.info = info
this.left = null;
this.right = null;
this.level = null;
}
function SearchBinaryTree() {
this._root = null;
}
SearchBinaryTree.prototype = {
constructor: SearchBinaryTree,
create: function(value){
/*
var node = {
info : value,
left: null,
right: null
}*/
if(this._root == null) {
this._root = new Node(value);
} else {
current = this._root;
for(;;) {
if(value < current.info) {
if(current.left) {
current = current.left;
} else {
current.left = new Node(value);
break;
}
} else if(value > current.info) {
if(current.right) {
current = current.right;
} else {
current.right = new Node(value);
break;
}
} else {
break;
}
}
}
},
travers: function(process) {
function inorder(node) {
if(node.left != null) {
inorder(node.left);
}
process.call(this,node);
if(node.right != null) {
inorder(node.right);
}
}
inorder(this._root);
},
BFT: function(callback) {
node = this._root;
node.level = 1;
var queue = [node],
output = [],
current_level = node.level,
current_node;
while(queue.length > 0) {
current_node = queue.shift();
if(current_node.level > current_level) {
current_level++;
output.push("\n");
}
output.push(current_node.info + " ");
if(current_node.left) {
current_node.left.level = current_level + 1;
queue.push(current_node.left);
}
if(current_node.right) {
current_node.right.level = current_level + 1;
queue.push(current_node.right);
}
}
return callback.call(this,output.join(""))
}
}
var out = [];
var tree = new SearchBinaryTree();
tree.create(8);
tree.create(3);
tree.create(1);
tree.create(6);
tree.create(4);
tree.create(7);
tree.create(10);
tree.create(14);
tree.create(13);
tree.travers(function(node){
out.push(node.info)
})
console.log(out);
tree.BFT(function(out){
console.log(out);
})
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment