JavaScript二元查找樹的定義與使用實例

這篇文章主要介紹了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中文網其他相關文章！