從二叉查找樹上刪除節(jié)點的操作復(fù)雜程度取決于刪除哪個節(jié)點。如果刪除沒有子節(jié)點的節(jié)點就非常簡單，如果節(jié)點只有一個子節(jié)點，不管是左子節(jié)點還是右子節(jié)點，就變得稍微有點復(fù)雜，如果節(jié)點包含兩個子節(jié)點就最復(fù)雜。
如果待刪除節(jié)點是葉子節(jié)點，那么只需要將從父節(jié)點指向它的鏈接指向null。
如果待刪除節(jié)點只包含一個子節(jié)點，那么原本指向它的節(jié)點就得使其指向它的子節(jié)點。
如果待刪除節(jié)點包含兩個子節(jié)點，那么我們可以采用兩種方式，一種是查找待刪除節(jié)點左子樹上的最大值，一種是查找待刪除節(jié)點右節(jié)點上的最小值。我們采取后者，找到最小值后，將臨時節(jié)點上的值復(fù)制到待刪除節(jié)點，然后再刪除臨時節(jié)點。
刪除操作的代碼如下：
function getSmallest(node){//查找最小節(jié)點
while(node.left!=null){
node=node.left;
}
return node;
}
function remove(data){
root=removeNode(this.root,data);//將根節(jié)點轉(zhuǎn)換
}
function removeNode(node,data){
if(node==null){
return null;
}
if(data==node.data){
//如果沒有子節(jié)點
if(node.right==null&&node.left==null){
return null;//直接將節(jié)點設(shè)為空
}
//如果沒有左子節(jié)點
if(node.left==null){
return node.right;//直接指向其右節(jié)點
}
//如果沒有右子節(jié)點
if(node.right==null){
return node.left;
}
//如果有兩個節(jié)點
if(node.right!=null&&node.left!=null){
var tempNode=getSmallest(node.right);//找到最小的右節(jié)點
node.data=tempNode.data;
node.right=removeNode(node.right,tempNode.data);//依次尋找
return node;
}
}else if(data
node.left=removeNode(node.left,data);
return node;
}else{
node.right=removeNode(node.right,data);