JavaScript数据结构23—排序二叉树

本示例表现了排序二叉树的三种操作
查找，删除，插入

//二叉排序树
function BtreeNode(data) {
  this.data = data;
}
BtreeNode.prototype.setL = function(node){
  this.lchild = node;
}
BtreeNode.prototype.setR = function(node){
  this.rchild = node;
}
BtreeNode.prototype.search = function(key){
  if(key == this.data){
    return {find:true,node:this};
  }else if(key < this.data){
    if(!this.lchild){
      return {find:false,node:this};
    }
    return this.lchild.search(key);
  }else{
    if(!this.rchild){
      return {find:false,node:this};
    }
    return this.rchild.search(key);
  }
}
BtreeNode.prototype.insert = function(key){
  var searchResult = this.search(key);
  if(!searchResult.find){
    var s = new BtreeNode(key);
    if(key<searchResult.node.data){
      searchResult.node.lchild = new BtreeNode(key);
    }else{
      searchResult.node.rchild = new BtreeNode(key);
    }
    return true;
  }
  return false;
}
BtreeNode.prototype.delete = function(){
  if(!this.rchild){
    var p = this;
    p = this.lchild;
  }else if(!this.lchild){
    var p = this
    p = this.rchild;
  }else{
    var q = this;
    var s = this.rchild;
    while(s.rchild){
      q = s;
      s = s.rchild;
    }
    this.data = s.data;
    if(q!=this){
      q.rchild = s.lchild;
    }else{
      q.lchild = s.lchild;
    }
  }
}
BtreeNode.prototype.deleteKey = function(key){
  if(this.data == key){
    this.delete();
  }else if(this.data>key){
    this.lchild.deleteKey(key);
  }else{
    this.rchild.deleteKey(key);
  }
}
var array1 = [];
for (var i = 0; i < 5000; i++) {
  array1[i] = parseInt(Math.random()*100000)+1;
}
var b = new BtreeNode(50000);
for (var i = 0; i < array1.length; i++) {
  b.insert(array1[i]);
}
console.info(array1[2]);
console.info(b.search(array1[2]));
b.deleteKey(array1[2]);
console.info(b.search(array1[2]));

OUTPUT

99209
{ find: true,
node:
BtreeNode {
data: 99209,
lchild: BtreeNode { data: 95537, rchild: [Object], lchild: [Object] },
rchild: BtreeNode { data: 99387, rchild: [Object], lchild: [Object] } } }
{ find: false, node: BtreeNode { data: 99191 } }
[Finished in 0.1s]