从 JavaScrip 中的二叉搜索树中删除所需的节点

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

问题

假设，我们有以下代码创建一个二叉搜索树 DS 并为我们提供插入节点的功能 -

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(5);
BST.insert(3);
BST.insert(6);
BST.insert(2);
BST.insert(4);
BST.insert(7);

执行完这段代码后，我们的 BST 将如下所示 -

/ \

3 6

/ \ \

2 4 7

我们需要编写另一个函数deleteNode()，它接受任何 BST 的根作为第一个参数，一个数值作为第二个参数。

如果第二个参数指定的值存在于树中，我们的函数应该删除保存该值的节点，否则我们的函数什么都不做。在这两种情况下，我们的函数都应该返回 BST 的更新根。

示例

此代码将是 -

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(5);
BST.insert(3);
BST.insert(6);
BST.insert(2);
BST.insert(4);
BST.insert(7);
const printTree = (node) => {
   if(node !== null) {
      printTree(node.left);
      console.log(node.data);
      printTree(node.right);
   };
};
const deleteNode = function(root, key) {
   if(!root){
      return null;
   };
   if(root.data > key){
      if(!root.left){
         return root;
      }else{
         root.left = deleteNode(root.left, key);
      };
   } else if(root.data < key){
      if(!root.right) return root;
      elseroot.right= deleteNode(root.right, key);
   } else {
      if(!root.left || !root.right){
         returnroot.left|| root.right;
      } else {
         let nd = new TreeNode();
         let right = root.right;
         nd.left = root.left;
         while(right.left){
            right = right.left;
         }
         nd.data = right.data;
         nd.right = deleteNode(root.right, right.data);
         return nd;
      }
   }
   return root;
};
console.log('Before Deleting any node');
printTree(BST.root);
console.log('After deleting node with data 4');
printTree(deleteNode(BST.root, 4));