คลาส Binary Search Tree ใน JavaScript

นี่คือการนำ BinarySearchTree Class ไปใช้งานอย่างสมบูรณ์:

ตัวอย่างโค้ด

class BinarySearchTree {
  constructor() {
    this.root = null;
  }
  insertIter(data) {
    let node = new this.Node(data);
    if (this.root === null) {
      this.root = node;
      return;
    }
    let currNode = this.root;
    while (true) {
      if (data < currNode.data) {
        if (currNode.left === null) {
          currNode.left = node;
          break;
        } else {
          currNode = currNode.left;
        }
      } else {
        if (currNode.right === null) {
          currNode.right = node;
          break;
        } else {
          currNode = currNode.right;
        }
      }
    }
  }
  insertRec(data) {
    let node = new this.Node(data);
    if (this.root === null) {
      this.root = node;
    } else {
      insertRecHelper(this.root, node);
    }
  }
  searchIter(data) {
    let currNode = this.root;
    while (currNode !== null) {
      if (currNode.data === data) {
        return true;
      } else if (data < currNode.data) {
        currNode = currNode.left;
      } else {
        currNode = currNode.right;
      }
    }
    return false;
  }
  searchRec(data) {
    return searchRecHelper(data, this.root);
  }
  getMinVal() {
    if (this.root === null) {
      throw "Empty tree!";
    }
    let currNode = this.root;
    while (currNode.left !== null) {
      currNode = currNode.left;
    }
    return currNode.data;
  }
  getMaxVal() {
    if (this.root === null) {
      throw "Empty tree!";
    }
    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;
  }
};
// HELPER METHODS
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) {
    if (root.left === null) {
      root.left = node;
    } else {
      insertRecHelper(root.left, node);
    }
  } else {
    if (root.right === null) {
      root.right = node;
    } else {
      insertRecHelper(root.right, node);
    }
  }
}
function searchRecHelper(data, root) {
  if (root === null) {
    return false;
  }
  if (data < root.data) {
    return searchRecHelper(data, root.left);
  } else if (data > root.data) {
    return searchRecHelper(data, root.right);
  }
  return true;
}
function deleteNodeHelper(root, key) {
  if (root === null) {
    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 {
    if (root.left === null && root.right === null) {
      root = null;
      return root;
    }
    if (root.left === null) return root.right;
    if (root.right === null) return root.left;
    let currNode = root.right;
    while (currNode.left !== null) {
      currNode = currNode.left;
    }
    root.data = currNode.data;
    root.right = deleteNodeHelper(root.right, currNode.data);
    return root;
  }
}