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

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

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

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

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

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

function Node(data,left,right){//結(jié)點(diǎn)類(lèi)
    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分別用來(lái)指向左右子結(jié)點(diǎn)。

接下來(lái)需要?jiǎng)?chuàng)建二叉查找樹(shù)的類(lèi)，代碼如下：

function BST(){//樹(shù)類(lèi)
    this.root=null;
    this.insert=insert;
    this.inOrder=inOrder;
    this.preOrder=preOrder;
    this.postOrder=postOrder;
}

接下來(lái)是插入節(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){//如果沒(méi)有左節(jié)點(diǎn)
            parent.left=n;
            break;
          }
        }else{
          current=current.right;
          if(current==null){//如果沒(méi)有右節(jié)點(diǎn)
            parent.right=n;
            break;
          }//如果有右節(jié)點(diǎn)，則跳到while重新執(zhí)行，將該節(jié)點(diǎn)作為parent重新開(kāi)始判斷
        }
      }
    }
}

更多關(guān)于JavaScript相關(guān)內(nèi)容感興趣的讀者可查看本站專(zhuān)題：《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ì)有所幫助。

最新評(píng)論