本文實例講述了JavaScript數據結構之二叉查找樹的定義與表示方法。分享給大家供大家參考，具體如下：
樹是一種非線性的數據結構，以分層的方式存儲數據。樹被用來存儲具有層級關系的數據，比如文件系統(tǒng)中的文件；樹還被用來存儲有序列表。這里將研究一種特殊的樹：二叉樹。選擇樹而不是那些基本的數據結構，是因為在二叉樹上進行查找非常快（而在鏈表上查找則不是這樣），為二叉樹添加或刪除元素也非常快（而對數組執(zhí)行添加或刪除操作則不是這樣）。
樹是n個結點的有限集。最上面的為根，下面為根的子樹。樹的節(jié)點包含一個數據元素及若干指向其子樹的分支。結點擁有的子樹稱為結點的度。度為0的結點稱為葉子或終端結點。度不為0的結點稱為非終端結點或分支結點。樹的度是樹內各結點的度的最大值。結點的層次從根開始定義，根為第0層。樹中結點的最大層次稱為樹的深度或高度。
二叉樹是一種特殊的樹，它的子節(jié)點個數不超過兩個。二叉樹具有一些特殊的計算性質，使得在它們之上的一些操作異常高效。通過將子節(jié)點的個數限定為 2，可以寫出高效的程序在樹中插入、查找和刪除數據。
在使用 JavaScript 構建二叉樹之前，需要給我們關于樹的詞典里再加兩個新名詞。一個父節(jié)點的兩個子節(jié)點分別稱為左節(jié)點和右節(jié)點。在一些二叉樹的實現中，左節(jié)點包含一組特定的值，右節(jié)點包含另一組特定的值。二叉查找樹是一種特殊的二叉樹，相對較小的值保存在左節(jié)點中，較大的值保存在右節(jié)點中。這一特性使得查找的效率很高，對于數值型和非數值型的數據，比如單詞和字符串，都是如此。
二叉查找樹由節(jié)點組成，所以我們要定義一個Node對象，代碼如下：
function Node(data,left,right){//結點類 this.data=data; this.left=left; this.right=right; this.show=show;}function show(){//顯示節(jié)點中數據 return this.data;}其中l(wèi)eft和right分別用來指向左右子結點。
接下來需要創(chuàng)建二叉查找樹的類，代碼如下：
function BST(){//樹類 this.root=null; this.insert=insert; this.inOrder=inOrder; this.preOrder=preOrder; this.postOrder=postOrder;}接下來是插入節(jié)點的代碼。遍歷小的插左邊，大的插右邊。代碼如下：
function insert(data){//插入操作 var n=new Node(data,null,null); if(this.root==null){//第一個元素 this.root=n; }else{ var current=this.root;//永遠指向根節(jié)點 var parent; while(true){//一直運行直到找到左結點或右結點為止 parent=current; if(data<current.data){ current=current.left; if(current==null){//如果沒有左節(jié)點 parent.left=n; break; } }else{ current=current.right; if(current==null){//如果沒有右節(jié)點 parent.right=n; break; }//如果有右節(jié)點，則跳到while重新執(zhí)行，將該節(jié)點作為parent重新開始判斷 } } }}希望本文所述對大家JavaScript程序設計有所幫助。
新聞熱點
疑難解答
