JavaScript數據結構之二叉樹的刪除算法示例

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

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

本文實例講述了JavaScript數據結構之二叉樹的刪除算法。分享給大家供大家參考，具體如下：

從二叉查找樹上刪除節(jié)點的操作復雜程度取決于刪除哪個節(jié)點。如果刪除沒有子節(jié)點的節(jié)點就非常簡單，如果節(jié)點只有一個子節(jié)點，不管是左子節(jié)點還是右子節(jié)點，就變得稍微有點復雜，如果節(jié)點包含兩個子節(jié)點就最復雜。

如果待刪除節(jié)點是葉子節(jié)點，那么只需要將從父節(jié)點指向它的鏈接指向null。

如果待刪除節(jié)點只包含一個子節(jié)點，那么原本指向它的節(jié)點就得使其指向它的子節(jié)點。

如果待刪除節(jié)點包含兩個子節(jié)點，那么我們可以采用兩種方式，一種是查找待刪除節(jié)點左子樹上的最大值，一種是查找待刪除節(jié)點右節(jié)點上的最小值。我們采取后者，找到最小值后，將臨時節(jié)點上的值復制到待刪除節(jié)點，然后再刪除臨時節(jié)點。

刪除操作的代碼如下：

function getSmallest(node){//查找最小節(jié)點
    while(node.left!=null){
      node=node.left;
    }
    return node;
}
function remove(data){
    root=removeNode(this.root,data);//將根節(jié)點轉換
}
function removeNode(node,data){
    if(node==null){
      return null;
    }
    if(data==node.data){
      //如果沒有子節(jié)點
      if(node.right==null&&node.left==null){
        return null;//直接將節(jié)點設為空
      }
      //如果沒有左子節(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.data){
      node.left=removeNode(node.left,data);
      return node;
    }else{
      node.right=removeNode(node.right,data);
      return node;
    }
}

更多關于JavaScript相關內容感興趣的讀者可查看本站專題：《JavaScript數據結構與算法技巧總結》、《JavaScript數學運算用法總結》、《JavaScript排序算法總結》、《JavaScript遍歷算法與技巧總結》、《JavaScript查找算法技巧總結》及《JavaScript錯誤與調試技巧總結》

希望本文所述對大家JavaScript程序設計有所幫助。

您可能感興趣的文章: