JavaScript二叉查找樹的定義與使用實(shí)例

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

樹是一種非線性的數(shù)據(jù)結(jié)構(gòu)，以分層的方式存儲(chǔ)數(shù)據(jù)。樹被用來存儲(chǔ)具有層級(jí)關(guān)系的數(shù)據(jù)，比如文件系統(tǒng)中的文件；樹還被用來存儲(chǔ)有序列表。這里將研究一種特殊的樹：二叉樹。選擇樹而不是那些基本的數(shù)據(jù)結(jié)構(gòu)，是因?yàn)樵诙鏄渖线M(jìn)行查找非?？欤ǘ阪湵砩喜檎覄t不是這樣），為二叉樹添加或刪除元素也非常快（而對(duì)數(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)包含另一組特定的值。二叉查找樹是一種特殊的二叉樹，相對(duì)較小的值保存在左節(jié)點(diǎn)中，較大的值保存在右節(jié)點(diǎn)中。這一特性使得查找的效率很高，對(duì)于數(shù)值型和非數(shù)值型的數(shù)據(jù)，比如單詞和字符串，都是如此。

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

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

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

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

聲明：本網(wǎng)頁內(nèi)容旨在傳播知識(shí)，若有侵權(quán)等問題請(qǐng)及時(shí)與本網(wǎng)聯(lián)系，我們將在第一時(shí)間刪除處理。TEL:177 7030 7066 E-MAIL:11247931@qq.com