這篇文章主要介紹了JavaScript資料結構之二元查找樹的定義與表示方法,簡單講述了二元查找樹的概念、特點及javascript針對二叉查找樹的創建、插入、遍歷等操作相關實作技巧,需要的朋友可以參考下
本文實例講述了JavaScript資料結構之二元查找樹的定義與表示方法。分享給大家供大家參考，具體如下：
樹是一種非線性的資料結構，以分層的方式儲存資料。樹被用來儲存具有層級關係的數據，例如檔案系統中的檔案；樹也被用來儲存有序列表。這裡將研究一種特殊的樹：二元樹。選擇樹而不是那些基本的資料結構，是因為在二元樹上進行查找非常快（而在鍊錶上查找則不是這樣），為二叉樹添加或刪除元素也非常快（而對數組執行添加或刪除操作則不是這樣）。
樹是n個結點的有限集合。最上面的為根，下面為根的子樹。樹的節點包含一個資料元素及若干指向其子樹的分支。結點擁有的子樹稱為結點的度數。度為0的結點稱為葉子或終端結點。度不為0的結點稱為非終端結點或分支結點。 樹的度數是樹內各結點的度數的最大值。結點的層次從根開始定義，根為第0層。樹中結點的最大層次稱為樹的深度或高度。
二元樹是一種特殊的樹，它的子節點數不超過兩個。二元樹具有一些特殊的計算性質，使得在它們之上的一些操作異常有效率。將子節點的數量限定為 2，可以寫出高效率的程式在樹中插入、尋找和刪除資料。
在使用 JavaScript 建立二元樹之前，需要先為我們關於樹的字典再加兩個新名詞。一個父節點的兩個子節點分別稱為左節點和右節點。在一些二元樹的實作中，左節點包含一組特定的值，右節點包含另一組特定的值。 二元查找樹是一種特殊的二元樹，相對較小的值保存在左節點中，較大的值保存在右節點中。這項特性使得查找的效率很高，對於數值型和非數值型的數據，例如單字和字串，都是如此。
二元查找樹由節點組成，所以我們要定義一個Node對象，程式碼如下：
function Node(data,left,right){//结点类
this.data=data;
this.left=left;
this.right=right;
this.show=show;
}
function show(){//显示节点中数据
return this.data;
}其中left和right分別用來指向左右子結點。
接下來需要建立二元查找樹的類，程式碼如下：
function BST(){//树类
this.root=null;
this.insert=insert;
this.inOrder=inOrder;
this.preOrder=preOrder;
this.postOrder=postOrder;
}接下來是插入節點的程式碼。遍歷小的插左邊，大的插右邊。程式碼如下：
function insert(data){//插入操作
var n=new Node(data,null,null);
if(this.root==null){//第一个元素
this.root=n;
}else{
var current=this.root;//永远指向根节点
var parent;
while(true){//一直运行直到找到左结点或右结点为止
parent=current;
if(data<current.data){
current=current.left;
if(current==null){//如果没有左节点
parent.left=n;
break;
}
}else{
current=current.right;
if(current==null){//如果没有右节点
parent.right=n;
break;
}//如果有右节点，则跳到while重新执行，将该节点作为parent重新开始判断
}
}
}
}以上是JavaScript二元查找樹的定義與使用實例的詳細內容。更多資訊請關注PHP中文網其他相關文章！
