在 JavaScript 中实现二叉搜索树-js教程-PHP中文网

在 JavaScript 中实现二叉搜索树

WBOY

发布： 2023-08-30 09:25:02

转载

468 人浏览过

在 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中文网其他相关文章！