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