class Tree {
  constructor() {
    this.root = null // 根节点
  }
  _node(data) {
    function node(data) {
      this.data = data;
      this.left = null;
      this.right = null;
    }
    return new node(data)
  }
  // 插入节点
  insert(data) {
    const newNode = this._node(data);
    const insertNode = (roots, newNode) => {
      if (newNode.data < roots.data) {
        // 左边
        if (roots.left === null) {
          roots.left = newNode
        } else {
          insertNode(roots.left, newNode)
        }
      } else {
        // 右边
        if (roots.right === null) {
          roots.right = newNode
        } else {
          insertNode(roots.right, newNode)
        }
      }
    }
    //判断是不是第一个
    if (this.root === null) {
      this.root = newNode
    } else {
      insertNode(this.root, newNode);
    }
  }
  // 先序遍历
  preorder() {
    let arr = [];
    const preorderNode = (roots) => {
      if (!roots) return false
      arr.push(roots.data);
      preorderNode(roots.left);
      preorderNode(roots.right);
    }
    preorderNode(this.root)
    return arr;
  }
  // 中序遍历
  cenorder() {
    let arr = [];
    const preorderNode = (roots) => {
      if (!roots) return false
      preorderNode(roots.left);
      arr.push(roots.data);
      preorderNode(roots.right);
    }
    preorderNode(this.root)
    return arr;
  }
  // 后续遍历
  endorder() {
    let arr = [];
    const preorderNode = (roots) => {
      if (!roots) return false
      preorderNode(roots.left);
      preorderNode(roots.right);
      arr.push(roots.data);
    }
    preorderNode(this.root)
    return arr;
  }
  // 寻找最小值
  findMin() {
    let r = this.root;
    while (r.left) {
      r = r.left
    }
    return r.data
  }
  // 寻找最大值
  findMax() {
    let r = this.root;
    while (r.right) {
      r = r.right
    }
    return r.data
  }
}