Implementing a binary search tree in JavaScript-JS Tutorial-php.cn

Implementing a binary search tree in JavaScript

WBOY

Release： 2023-08-30 09:25:02

forward

466 people have browsed it

在 JavaScript 中实现二叉搜索树

Tree data structure

A tree is a collection of nodes connected by some edges. By convention, each node of the tree Save some data and references to its child nodes.

Binary Search Tree

A binary search tree is a binary tree in which nodes with smaller values are stored on the left and nodes with smaller values are stored on the left. Higher values are stored on the right.

For example, the visual representation of a valid BST is -

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

Copy after login

Now let us implement our own binary search tree in JavaScript language.

Step 1: Node Class

This class will represent a single node that exists at each point in the BST. BST Nothing Rather, it is a collection of nodes that store data and subreferences placed according to rules. As mentioned above.

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

Copy after login

To create a new Node instance we can call this class with some data -

const newNode = new Node(23);

Copy after login

This will create a new Node instance with its data set to 23 and both left and right references is null.

Step 2: Binary Search Tree Class:

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

Copy after login

This will create the Binary Search Tree class, which we can call using the new keyword to create a tree instance.

Now that we have done the basics, let's go ahead and insert a new node at the correct location (according to the BST rules described in the definition).

Step 3: Insert nodes in 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);
         };
      };
   };
};

Copy after login

Example

Full binary search tree code:

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);

Copy after login

The above is the detailed content of Implementing a binary search tree in JavaScript. For more information, please follow other related articles on the PHP Chinese website!