没什么难度，不解释了= =
function BinarySearchTree(){
this.size = 0;
this.root = null;
}
//module.exports = BinarySearchTree;
BinarySearchTree.prototype.insert = function(element){
if(this.root===null){
this.root = new Node(element,null);
}else{
var curnode = this.root,last;
while(curnode!=null){
if(curnode.element>element){
last = curnode;
curnode = curnode.left;
}else if(curnode.element<element){
last = curnode;
curnode = curnode.right;
}else{
return false; //find same element
}
}
if(element>last.element){
last.right = new Node(element,last);
}else{
last.left = new Node(element,last);
}
}
this.size++;
return true;
}
BinarySearchTree.prototype.find = function(element){
var cur = this.root;
while(cur!==null){
if(cur.element===element) return cur;
if(cur.element>element){
cur = cur.left;
}else{
cur = cur.right;
}
}
return cur; //null
}
BinarySearchTree.prototype.findMin = function(node){
var cur = node,last;
if(!node) return null;
while(cur!==null){
last = cur;
cur = cur.left;
}
return last;
}
BinarySearchTree.prototype.delete = function(node){
if(!node) return null;
if(node.left===null&&node.right===null){
if(node.parent===null){
node = this.root = null;
this.size = 0;
}else if(node.parent.left===node){
node.parent.left = node = null;
this.size--;
}else{
node.parent.right = node = null;
this.size--;
}
}else if(node.left===null&&node.right!==null){
if(node.parent ===null){
this.size = 0;
this.root = node = null;
}else if(node.parent.left===node){
node.parent.left = node.right;
node.right.parent = node.parent;
node = null;
this.size--;
}else{
node.parent.right = node.right;
node.right.parent = node.parent;
node = null;
this.size--;
}
}else if(node.left!==null&&node.right===null){
if(node.parent===null){
this.root = node = null;
this.size = 0;
}else if(node.parent.left===node){
node.parent.left = node.left;
node.left.parent = node.parent;
node = null;
this.size--;
}else{
node.parent.right = node.left;
node.left.parent = node.parent;
node = null;
this.size--;
}
}else{
var min = this.findMin(node.right);
if(min===null) throw new Error('some error in delete case 4');
var tem = min.element;
min.element = node.element;
node.element = tem;
this.delete(min);
}
}
BinarySearchTree.prototype.printOne = function(node){
return ' '+node.element+' ';
}
BinarySearchTree.prototype.inorder = function(node){
if(!node) return '';
return this.inorder(node.left)+this.printOne(node)+this.inorder(node.right);
}
BinarySearchTree.prototype.preorder = function(node){
if(!node) return '';
return this.printOne(node)+this.preorder(node.left)+this.preorder(node.right);
}
BinarySearchTree.prototype.postorder = function(node){
if(!node) return '';
return this.postorder(node.left)+this.postorder(node.right)+this.printOne(node);
}
//---------------------fot test-----------------------------
var tree = new BinarySearchTree();
var arr = [5,1,2,4,3,7,-1];
arr.forEach(function(a){
tree.insert(a);
});
tree.delete(tree.root.left);
var someone = tree.find(4);
var anotherone = tree.find(10);
var util = require('util');
console.log('find 4:',util.inspect(someone));
console.log('find 10:',util.inspect(anotherone));
var pre = tree.preorder(tree.root);
var ino = tree.inorder(tree.root);
var post = tree.postorder(tree.root);
console.log('pre:',pre);
console.log('in:',ino);
console.log('post:',post);
