在 JavaScript 中實作二元搜尋樹

樹資料結構

樹是由一些邊連接的節點的集合。按照慣例，樹的每個節點 保存一些資料和對其子節點的引用。

二元搜尋樹

二元搜尋樹是一棵二元樹，其中具有較小值的節點儲存在左側，而具有較小值的節點儲存在左側。較高的值儲存在右側。

例如，有效 BST 的視覺表示是 -

     25
   /   \
  20   36
 / \   / \
10 22 30 40

現在讓我們用 JavaScript 語言實作我們自己的二元搜尋樹。

第 1 步：節點類別

該類別將表示存在於 BST 中各個點的單一節點。 BST 沒什麼 而是按照規則放置的儲存資料和子引用的節點的集合 如上所述。

class Node{
   constructor(data) {
      this.data = data;
      this.left = null;
      this.right = null;
   };
};

要建立一個新的Node 實例，我們可以使用一些資料來呼叫此類-

const newNode = new Node(23);

這將建立一個新的Node 實例，其資料設定為23，左右引用均為null。

第 2 步：二叉搜尋樹類：

class BinarySearchTree{
   constructor(){
      this.root = null;
   };
};

這將建立一個二元搜尋樹類，我們可以使用 new 關鍵字呼叫它來建立一個 樹實例。

現在我們已經完成了基本的工作，讓我們繼續在正確的位置插入一個新節點（根據定義中描述的 BST 規則）。

步驟3：在BST中插入節點

class BinarySearchTree{
   constructor(){
      this.root = null;
   }
   insert(data){
      var newNode = new Node(data);
      if(this.root === null){
         this.root = newNode;
      }else{
         this.insertNode(this.root, newNode);
      };
   };
   insertNode(node, newNode){
      if(newNode.data < node.data){
         if(node.left === null){
            node.left = newNode;
         }else{
            this.insertNode(node.left, newNode);
         };
      } else {
         if(node.right === null){
            node.right = newNode;
         }else{
            this.insertNode(node.right,newNode);
         };
      };
   };
};

範例

完整二叉搜尋樹碼：

class Node{
   constructor(data) {
      this.data = data;
      this.left = null;
      this.right = null;
   };
};
class BinarySearchTree{
   constructor(){
      this.root = null;
   }
   insert(data){
      var newNode = new Node(data);
      if(this.root === null){
         this.root = newNode;
      }else{
         this.insertNode(this.root, newNode);
      };
   };
   insertNode(node, newNode){
      if(newNode.data < node.data){
         if(node.left === null){
            node.left = newNode;
         }else{
            this.insertNode(node.left, newNode);
         };
      } else {
         if(node.right === null){
            node.right = newNode;
         }else{
            this.insertNode(node.right,newNode);
         };
      };
   };
};
const BST = new BinarySearchTree();
BST.insert(1);
BST.insert(3);
BST.insert(2);

以上是在 JavaScript 中實作二元搜尋樹的詳細內容。更多資訊請關注PHP中文網其他相關文章！