快捷導(dǎo)航

JavaScript數(shù)據(jù)結(jié)構(gòu)之二叉樹(shù)的刪除算法示例

更新時(shí)間：2017年04月13日 09:53:38 作者：布瑞澤的童話

這篇文章主要介紹了JavaScript數(shù)據(jù)結(jié)構(gòu)之二叉樹(shù)的刪除算法,簡(jiǎn)單分析了javascript刪除數(shù)據(jù)結(jié)構(gòu)中二叉樹(shù)節(jié)點(diǎn)時(shí)所遇到的各種情況與相關(guān)的處理原理與算法實(shí)現(xiàn)技巧,需要的朋友可以參考下

本文實(shí)例講述了JavaScript數(shù)據(jù)結(jié)構(gòu)之二叉樹(shù)的刪除算法。分享給大家供大家參考，具體如下：

從二叉查找樹(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.data){
      node.left=removeNode(node.left,data);
      return node;
    }else{
      node.right=removeNode(node.right,data);
      return node;
    }
}

更多關(guān)于JavaScript相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《JavaScript數(shù)據(jù)結(jié)構(gòu)與算法技巧總結(jié)》、《JavaScript數(shù)學(xué)運(yùn)算用法總結(jié)》、《JavaScript排序算法總結(jié)》、《JavaScript遍歷算法與技巧總結(jié)》、《JavaScript查找算法技巧總結(jié)》及《JavaScript錯(cuò)誤與調(diào)試技巧總結(jié)》

希望本文所述對(duì)大家JavaScript程序設(shè)計(jì)有所幫助。

您可能感興趣的文章: