在JavaScript中实现二进制搜索树

Z时代
2024-01-10
分类：综合

树数据结构

树是由某些边缘连接的节点的集合。按照惯例，树的每个节点都保存一些数据并引用其子级。

二进制搜索树

二进制搜索树是一种二进制树，其中值较小的节点存储在左侧，而值较大的节点存储在右侧。

例如，有效BST的可视化表示为-

/ \

20 36

/ \ / \

10 22 30 40

现在让我们以JavaScript语言实现我们自己的Binary Search Tree。

步骤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;
   };
};

这将创建Binary Search Tree类，我们可以使用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);