BST(二叉搜索树)JS实现

{
  root: {
    left: {
      val: 1,
      left: null,
      right: null
    },
    right: {
      val: 10,
      left: null,
      right: null
    },
    val: 5
  }
}

function Node(val, left, right) {
  this.val = val;
  this.left = left;
  this.right = right;
}
function BST() {
  this.root = null;
}

BST.prototype = {
  isNull() {
    return this.root === null;
  },
  // 插入节点
  insert(val) {
    if (isNaN(val) || typeof val !== "number") {
      return;
    }
    if (this.isNull()) {
      this.root = new Node(val, null, null);
    } else {
      var curr = this.root;
      while (curr) {
        if (val < curr.val) {
          if (curr.left === null) {
            curr.left = new Node(val, null, null);
            break;
          }
          curr = curr.left;
        } else {
          if (curr.right === null) {
            curr.right = new Node(val, null, null);
            break;
          }
          curr = curr.right;
        }
      }
    }
  },
  // 删除节点
  remove(val) {
    if (this.isNull()) {
      return false;
    }
    var node = this.root;
    var parent = node;
    while (node) {
      if (val < node.val) {
        parent = node;
        node = node.left;
      } else if (val > node.val) {
        parent = node;
        node = node.right;
      } else {
        if (parent === node) {
          this.root = null;
        } else {
          parent.left = null;
          parent.right = null;
        }
        return true;
      }
    }
    return false;
  },
  // 查找节点
  find(val) {
    if (this.isNull()) {
      return null;
    }
    var node = this.root;
    while (node) {
      if (val < node.val) {
        node = node.left;
      } else if (val > node.val) {
        node = node.right;
      } else {
        return node;
      }
    }
    return null;
  },
  // 获取指定节点数据出现次数
  count(val) {
    var res = 0;
    if (this.isNull()) {
      return res;
    }
    var node = this.root;
    while (node) {
      if (val < node.val) {
        node = node.left;
      } else if (val > node.val) {
        node = node.right;
      } else {
        res++;
        node = node.right;
      }
    }
    return res;
  },
  /* 深度优先 */
  // 前序非递归
  preOrder() {
    if (this.isNull()) {
      return [];
    }
    var res = [];
    var stack = [this.root];
    var node;
    while (stack.length) {
      node = stack.pop();
      res.push(node.val);
      node.right && stack.push(node.right);
      node.left && stack.push(node.left);
    }
    return res;
  },
  // 前序递归
  preOrderRecursive() {
    function helper(node) {
      if (!node) {
        return [];
      }
      return [node.val, ...helper(node.left), ...helper(node.right)];
    }
    return helper(this.root);
  },
  // 中序非递归
  inOrder() {
    if (this.isNull()) {
      return [];
    }
    var res = [];
    var stack = [];
    var node = this.root;
    while (stack.length || node) {
      if (node) {
        stack.push(node);
        node = node.left;
      } else {
        node = stack.pop();
        res.push(node.val);
        node = node.right;
      }
    }
    return res;
  },
  // 中序递归
  inOrderRecursive() {
    function helper(node) {
      if (!node) {
        return [];
      }
      return [...helper(node.left), node.val, ...helper(node.right)];
    }
    return helper(this.root);
  },
  // 后序非递归
  postOrder() {
    if (this.isNull()) {
      return [];
    }
    var res = [];
    var stack = [this.root];
    var node = this.root;
    while (stack.length) {
      node.left && stack.push(node.left);
      node.right && stack.push(node.right);
      res.unshift(node.val);
      node = stack.pop();
    }
    return res;
  },
  // 后序递归
  postOrderRecursive() {
    function helper(node) {
      if (!node) {
        return [];
      }
      return [...helper(node.left), ...helper(node.right), node.val];
    }
    return helper(this.root);
  },
  /* 广度优先 */
  // 层序非递归
  bfs() {
    if (this.isNull()) {
      return [];
    }
    var res = [];
    var que = [this.root];
    var node;
    while (que.length) {
      node = que.shift();
      res.push(node.val);
      node.left && que.push(node.left);
      node.right && que.push(node.right);
    }
    return res;
  },
  // 层序递归
  bfsRecursive() {
    var res = [];
    function helper(node, level) {
      if (!node) return;
      res[level] = node.val;
      node.left && helper(node.left, 2 * level);
      node.right && helper(node.right, 2 * level + 1);
    }
    helper(this.root, 1);
    return res.filter((item) => typeof item === "number");
  },
  // 获取二叉树最大深度
  getDepth() {
    function helper(node, depth) {
      if (!node) {
        return depth;
      }
      return Math.max(
        helper(node.left, depth + 1),
        helper(node.right, depth + 1)
      );
    }
    return helper(this.root, 0);
  },
  // 获取最小值
  getMin() {
    if (this.isNull()) {
      return null;
    }
    var res;
    var node = this.root;
    while (node) {
      res = node.val;
      node = node.left;
    }
    return res;
  },
  // 获取最大值
  getMax() {
    if (this.isNull()) {
      return null;
    }
    var res;
    var node = this.root;
    while (node) {
      res = node.val;
      node = node.right;
    }
    return res;
  },
};

var tree = new BST();
tree.insert(10);
tree.insert(5);
tree.insert(15);
tree.insert(3);
tree.insert(6);
tree.insert(12);
tree.insert(18);
tree.insert(1);
tree.insert(0);
tree.insert(1);
console.log('二叉树结构:', tree);
console.log('前序:', tree.preOrder(), tree.preOrderRecursive());
console.log('中序:', tree.inOrder(), tree.inOrderRecursive());
console.log('后序:', tree.postOrder(), tree.postOrderRecursive());
console.log('层序:', tree.bfs(), tree.bfsRecursive());
console.log('最大深度:', tree.getDepth());
console.log('最小值:', tree.getMin());
console.log('最大值:', tree.getMax());
console.log('查找3:', tree.find(3));
console.log('计数1:', tree.count(1));
tree.remove(1);
console.log('查找3:', tree.find(3));
console.log('计数1:', tree.count(1));