binary search tree in typescript

binary-search-tree.ts

// tslint:disable: max-classes-per-file
class TreeNode {
  public left: TreeNode = null;
  public right: TreeNode = null;
  constructor(public data) {
    this.data = data;
    this.left = null;
    this.right = null;
  }
}

export default class Tree {
  public root: TreeNode = null;

  public addNode(data) {
    const node = new TreeNode(data);
    if (!this.root) {
      this.root = node;
    } else {
      this.insertNode(this.root, node);
    }
  }

  public insertNode(baseNode: TreeNode, node: TreeNode) {
    if (node.data <= baseNode.data) { // 插入左边
      if (!baseNode.left) {
        baseNode.left = node;
      } else {
        this.insertNode(baseNode.left, node);
      }
    } else { // 插入右边
      if (!baseNode.right) {
        baseNode.right = node;
      } else {
        this.insertNode(baseNode.right, node);
      }
    }
  }

  /**
   *
   * @param {'inorder': 左中右 | 'preorder': 中左右 | 'postorder': 左右中} type
   */
  public traverseDFS(type: 'inorder' | 'preorder' | 'postorder' = 'inorder') {
    const result = [];
    const recurive = (node: TreeNode) => {
      if (node) {
        // 中序遍历
        if (type === 'inorder') {
          recurive(node.left);
          result.push(node.data);
          recurive(node.right);
        }
        if (type === 'preorder') {
          result.push(node.data);
          recurive(node.left);
          recurive(node.right);
        }
        if (type === 'postorder') {
          recurive(node.left);
          recurive(node.right);
          result.push(node.data);
        }
      }
    };
    recurive(this.root);
    return result;
  }

  public traverseBFS() {
    if (!this.root) {
      return;
    }
    const queue = [];
    const result = [];
    queue.push(this.root);
    while (queue.length) {
      const node = queue.shift();
      if (node.left) {
        queue.push(node.left);
      }
      if (node.right) {
        queue.push(node.right);
      }
      result.push(node.data);
    }
    return result;
  }

  public findMin() {
    const minNode = this.findMinNode(this.root);
    return minNode ? minNode.data : null;
  }

  public findMax() {
    const maxNode = this.findMaxNode(this.root);
    return maxNode ? maxNode.data : null;
  }

  public removeNode(data) {
    return this.remove(this.root, data);
  }

  private findMinNode(node: TreeNode) {
    if (!node) {
      return null;
    }
    while (node.left) {
      node = node.left;
    }
    return node;
  }

  private findMaxNode(node: TreeNode) {
    if (!node) {
      return null;
    }
    while (node.right) {
      node = node.right;
    }
    return node;
  }

  private remove(node, data) {
    if (!node) {
      return null;
    }
    if (data > node.data) { // 往右
      node.right = this.remove(node.right, data);
      return node;
    }
    if (data < node.data) { // 往左
      node.left = this.remove(node.left, data);
      return node;
    }
    if (node.data === data) { // 找到
      if (!node.left && !node.right) {
        node = null;
        return node;
      }
      if (!node.left) {
        node = node.right;
        return node;
      }
      if (!node.right) {
        node = node.left;
        return node;
      }
      const min = this.findMinNode(node.right); // 在右树中找最小节点，保证比左树大，比右树小
      node.data = min.data; // 使用右树最小数据替换数据
      node.right = this.remove(node.right, min.data); // 右树删掉最小数据节点
      return node;
    }
  }
}