Class Binary Search Tree trong JavaScript

Dưới đây là triển khai hoàn chỉnh của class BinarySearchTree:

Ví dụ

class BinarySearchTree {
  constructor() {
    // Khởi tạo phần tử root là null.
    this.root = null;
  }
  insertIter(data) {
    let node = new this.Node(data);
    // Kiểm tra nếu cây rỗng
    if (this.root === null) {
      // Chèn làm phần tử đầu tiên
      this.root = node;
      return;
    }
    let currNode = this.root;
    while (true) {
      if (data < currNode.data) {
        // Đặt giá trị ở đây vì đã đến nút lá
        if (currNode.left === null) {
          currNode.left = node;
          break;
        } else {
          currNode = currNode.left;
        }
      } else {
        // Đặt giá trị ở đây vì đã đến nút lá
        if (currNode.right === null) {
          currNode.right = node;
          break;
        } else {
          currNode = currNode.right;
        }
      }
    }
  }
  insertRec(data) {
    let node = new this.Node(data);
    // Kiểm tra nếu cây rỗng
    if (this.root === null) {
      // Chèn làm phần tử đầu tiên
      this.root = node;
    } else {
      insertRecHelper(this.root, node);
    }
  }
  searchIter(data) {
    let currNode = this.root;
    while (currNode !== null) {
      if (currNode.data === data) {
        // Tìm thấy phần tử!
        return true;
      } else if (data < currNode.data) {
        // Đi trái vì data nhỏ hơn cha
        currNode = currNode.left;
      } else {
        // Đi phải vì data lớn hơn cha
        currNode = currNode.right;
      }
    }
    return false;
  }
  searchRec(data) {
    return searchRecHelper(data, this.root);
  }
  getMinVal() {
    if (this.root === null) {
      throw "Cây rỗng!";
    }
    let currNode = this.root;
    while (currNode.left !== null) {
      currNode = currNode.left;
    }
    return currNode.data;
  }
  getMaxVal() {
    if (this.root === null) {
      throw "Cây rỗng!";
    }
    let currNode = this.root;
    while (currNode.right !== null) {
      currNode = currNode.right;
    }
    return currNode.data;
  }
  deleteNode(key) {
    return !(deleteNodeHelper(this.root, key) === false);
  }
  inOrder() {
    inOrderHelper(this.root);
  }
  preOrder() {
    preOrderHelper(this.root);
  }
  postOrder() {
    postOrderHelper(this.root);
  }
}
BinarySearchTree.prototype.Node = class {
  constructor(data, left = null, right = null) {
    this.data = data;
    this.left = left;
    this.right = right;
  }
};
// CÁC PHƯƠNG THỨC HELPER
function preOrderHelper(root) {
  if (root !== null) {
    console.log(root.data);
    preOrderHelper(root.left);
    preOrderHelper(root.right);
  }
}
function inOrderHelper(root) {
  if (root !== null) {
    inOrderHelper(root.left);
    console.log(root.data);
    inOrderHelper(root.right);
  }
}
function postOrderHelper(root) {
  if (root !== null) {
    postOrderHelper(root.left);
    postOrderHelper(root.right);
    console.log(root.data);
  }
}
function insertRecHelper(root, node) {
  if (node.data < root.data) {
    // Đặt giá trị ở đây vì đã đến nút lá
    if (root.left === null) {
      root.left = node;
    } else {
      insertRecHelper(root.left, node);
    }
  } else {
    // Đặt giá trị ở đây vì đã đến nút lá
    if (root.right === null) {
      root.right = node;
    } else {
      insertRecHelper(root.right, node);
    }
  }
}
function searchRecHelper(data, root) {
  if (root === null) {
    // Đã đến lá nhưng không tìm thấy.
    return false;
  }
  if (data < root.data) {
    return searchRecHelper(data, root.left);
  } else if (data > root.data) {
    return searchRecHelper(data, root.right);
  }
  // Nghĩa là phần tử đã tìm thấy
  return true;
}
/**
 * Nhận root và key, đệ quy tìm key.
 * Nếu tìm thấy key, có thể có 3 trường hợp:
 * 1. Nút này là nút lá.
 * 2. Nút này ở giữa cây với một con.
 * 3. Nút này có cả hai con (trường hợp phức tạp).
 */
function deleteNodeHelper(root, key) {
  if (root === null) {
    // Cây rỗng
    return false;
  }
  if (key < root.data) {
    root.left = deleteNodeHelper(root.left, key);
    return root;
  } else if (key > root.data) {
    root.right = deleteNodeHelper(root.right, key);
    return root;
  } else {
    // Không có con - trường hợp 1: nút lá
    if (root.left === null && root.right === null) {
      root = null;
      return root;
    }
    // Trường hợp một con
    if (root.left === null) return root.right;
    if (root.right === null) return root.left;
    // Cả hai con, cần tìm successor
    let currNode = root.right;
    while (currNode.left !== null) {
      currNode = currNode.left;
    }
    root.data = currNode.data;
    // Xóa giá trị từ cây con phải.
    root.right = deleteNodeHelper(root.right, currNode.data);
    return root;
  }
}