JavaScript中如何定義二叉查找樹-創(chuàng)新互聯(lián)

小編給大家分享一下JavaScript中如何定義二叉查找樹，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！

創(chuàng)新互聯(lián)堅(jiān)持“要么做到，要么別承諾”的工作理念，服務(wù)領(lǐng)域包括：網(wǎng)站設(shè)計(jì)、成都網(wǎng)站制作、企業(yè)官網(wǎng)、英文網(wǎng)站、手機(jī)端網(wǎng)站、網(wǎng)站推廣等服務(wù)，滿足客戶于互聯(lián)網(wǎng)時(shí)代的丹徒網(wǎng)站設(shè)計(jì)、移動(dòng)媒體設(shè)計(jì)的需求，幫助企業(yè)找到有效的互聯(lián)網(wǎng)解決方案。努力成為您成熟可靠的網(wǎng)絡(luò)建設(shè)合作伙伴！

樹是一種非線性的數(shù)據(jù)結(jié)構(gòu)，以分層的方式存儲(chǔ)數(shù)據(jù)。樹被用來存儲(chǔ)具有層級關(guān)系的數(shù)據(jù)，比如文件系統(tǒng)中的文件；樹還被用來存儲(chǔ)有序列表。這里將研究一種特殊的樹：二叉樹。選擇樹而不是那些基本的數(shù)據(jù)結(jié)構(gòu)，是因?yàn)樵诙鏄渖线M(jìn)行查找非?？欤ǘ阪湵砩喜檎覄t不是這樣），為二叉樹添加或刪除元素也非?？欤ǘ鴮?shù)組執(zhí)行添加或刪除操作則不是這樣）。

樹是n個(gè)結(jié)點(diǎn)的有限集。最上面的為根，下面為根的子樹。樹的節(jié)點(diǎn)包含一個(gè)數(shù)據(jù)元素及若干指向其子樹的分支。結(jié)點(diǎn)擁有的子樹稱為結(jié)點(diǎn)的度。度為0的結(jié)點(diǎn)稱為葉子或終端結(jié)點(diǎn)。度不為0的結(jié)點(diǎn)稱為非終端結(jié)點(diǎn)或分支結(jié)點(diǎn)。樹的度是樹內(nèi)各結(jié)點(diǎn)的度的大值。結(jié)點(diǎn)的層次從根開始定義，根為第0層。樹中結(jié)點(diǎn)的大層次稱為樹的深度或高度。

二叉樹是一種特殊的樹，它的子節(jié)點(diǎn)個(gè)數(shù)不超過兩個(gè)。二叉樹具有一些特殊的計(jì)算性質(zhì)，使得在它們之上的一些操作異常高效。通過將子節(jié)點(diǎn)的個(gè)數(shù)限定為 2，可以寫出高效的程序在樹中插入、查找和刪除數(shù)據(jù)。

在使用 JavaScript 構(gòu)建二叉樹之前，需要給我們關(guān)于樹的詞典里再加兩個(gè)新名詞。一個(gè)父節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)分別稱為左節(jié)點(diǎn)和右節(jié)點(diǎn)。在一些二叉樹的實(shí)現(xiàn)中，左節(jié)點(diǎn)包含一組特定的值，右節(jié)點(diǎn)包含另一組特定的值。二叉查找樹是一種特殊的二叉樹，相對較小的值保存在左節(jié)點(diǎn)中，較大的值保存在右節(jié)點(diǎn)中。這一特性使得查找的效率很高，對于數(shù)值型和非數(shù)值型的數(shù)據(jù)，比如單詞和字符串，都是如此。

二叉查找樹由節(jié)點(diǎn)組成，所以我們要定義一個(gè)Node對象，代碼如下：

function Node(data,left,right){//結(jié)點(diǎn)類
    this.data=data;
    this.left=left;
    this.right=right;
    this.show=show;
}
function show(){//顯示節(jié)點(diǎn)中數(shù)據(jù)
    return this.data;
}

其中l(wèi)eft和right分別用來指向左右子結(jié)點(diǎn)。

接下來需要?jiǎng)?chuàng)建二叉查找樹的類，代碼如下：

function BST(){//樹類
    this.root=null;
    this.insert=insert;
    this.inOrder=inOrder;
    this.preOrder=preOrder;
    this.postOrder=postOrder;
}

接下來是插入節(jié)點(diǎn)的代碼。遍歷小的插左邊，大的插右邊。代碼如下：

function insert(data){//插入操作
    var n=new Node(data,null,null);
    if(this.root==null){//第一個(gè)元素
      this.root=n;
    }else{
      var current=this.root;//永遠(yuǎn)指向根節(jié)點(diǎn)
      var parent;
      while(true){//一直運(yùn)行直到找到左結(jié)點(diǎn)或右結(jié)點(diǎn)為止
        parent=current;
        if(data<current.data){
          current=current.left;
          if(current==null){//如果沒有左節(jié)點(diǎn)
            parent.left=n;
            break;
          }
        }else{
          current=current.right;
          if(current==null){//如果沒有右節(jié)點(diǎn)
            parent.right=n;
            break;
          }//如果有右節(jié)點(diǎn)，則跳到while重新執(zhí)行，將該節(jié)點(diǎn)作為parent重新開始判斷
        }
      }
    }
}

以上是“JavaScript中如何定義二叉查找樹”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對大家有所幫助，如果還想學(xué)習(xí)更多知識，歡迎關(guān)注創(chuàng)新互聯(lián)網(wǎng)站建設(shè)公司行業(yè)資訊頻道！

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)建站bm7419.com，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。

本文名稱：JavaScript中如何定義二叉查找樹-創(chuàng)新互聯(lián)
URL鏈接：http://bm7419.com/article0/ddpiio.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供小程序開發(fā)、移動(dòng)網(wǎng)站建設(shè)、全網(wǎng)營銷推廣、商城網(wǎng)站、網(wǎng)站設(shè)計(jì)、做網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)