//创建节点类
class Node {
    constructor(key) {
        this.key = key;//节点值
        this.left = null;//左指针
        this.right = null;//右指针
    }
}

class BinaryTree {
    constructor() {
        this.root = null;
    }

    // 在这里写代码
}

//插入
insert(key) {
    const newNode = new Node(key);
    if (this.root === null) {//设置根节点
        this.root = newNode;
    }
    this.insertNode(this.root, newNode);
}
insertNode(node, newNode) {
    if (newNode.key < node.key) {//插值小于节点值进入左子树
        if (node.left === null) {//直到左子树为空
            node.left = newNode
        } else {//左子树已存在
            this.insertNode(node.left, newNode)
        }
    } else if (newNode.key > node.key){//插入值大于节点值进入右子树
        if (node.right === null) {//直到右子树为空
            node.right = newNode
        } else {//右子树已存在
            this.insertNode(node.right, newNode)
        }
    }
}

// 实例化二叉树
const binaryTree = new BinaryTree();
// key值
const keys = [19, 8, 15, 24, 45, 12, 5];
// 生成二叉排序树
keys.forEach(key => binaryTree.insert(key));

//中序遍历
inorderTraversal() {
    let info = [];
    this.inorderTraversalNode(this.root, ({key}) => {
        info.push(key)
    });
    return info;
}
inorderTraversalNode(node, callback) {
    if (node) {//当前节点
        this.inorderTraversalNode(node.left, callback);//遍历左子树
        callback(node);//访问节点
        this.inorderTraversalNode(node.right, callback);//遍历右子树
    }
}
//遍历结果：[5, 8, 12, 15, 19, 24, 45]

//前序遍历
preOrderTraversal() {
    let info = [];
    this.preOrderTraversalNode(this.root, ({key}) => {
        info.push(key)
    });
    return info;
}
preOrderTraversalNode(node, callback) {
    if (node) {//当前节点
        callback(node);//访问节点
        this.preOrderTraversalNode(node.left, callback);//遍历左子树
        this.preOrderTraversalNode(node.right, callback);//遍历右子树
    }
}
//遍历结果：[19,  8,  5, 15, 12, 24, 45]

//后序遍历
postOrderTraversal() {
    let info = [];
    this.postOrderTraversalNode(this.root, ({key}) => {
        info.push(key)
    });
    return info;
}
postOrderTraversalNode(node, callback){
    if (node) {//当前节点
        this.postOrderTraversalNode(node.left, callback);//遍历左子树
        this.postOrderTraversalNode(node.right, callback);//遍历右子树
        callback(node);//访问节点
    }
}
//遍历结果：[5, 12, 15, 8, 45, 24, 19]

//最大值
max() {
    return this.maxNode(this.root)
}
maxNode(node) {
    if (node) {
        while (node.right !== null) {//右子树不为空时
            node = node.right;
        }
        return node.key
    }
    return null
}

//最小值
min() {
    return this.minNode(this.root)
}
minNode(node) {
    if (node) {
        while (node.left !== null) {//左子树不为空时
            node = node.left;
        }
        return node.key
    }
    return null
}

//查找
search(key) {
    return this.searchNode(this.root, key)
}
searchNode(node, key) {
    if (node === null) {
        return false
    }
    if (key < node.key) {//进入左子树
        return this.searchNode(node.left, key)
    } else if (key > node.key) {//进入右子树
        return this.searchNode(node.right, key)
    } else {//相等
        return true
    }
}

//删除
remove(key) {
    this.root = this.removeNode(this.root, key)
}
removeNode(node, key) {
    if (node === null) {//没有找到值对应节点
        return null
    }
    if (key < node.key) {//给定值小于当前节点值
        node.left = this.removeNode(node.left, key);
        return node
    } else if (key > node.key) {//给定值大于当前节点值
        node.right = this.removeNode(node.right, key);
        return node
    } else {//找到对应的节点
        if (node.left === null && node.right === null) {//节点为叶子节点
            node = null;
            return node
        }
        if (node.right === null) {//节点存在左子树
            node = node.left;
            return node
        } else if (node.left === null) {//节点存在右子树
            node = node.right;
            return node
        }
        //节点存在左右子树时，先去右子树找最小值
        const minKey = this.minNode(node.right);
        //用最小值替换节点值
        node.key = minKey;
        //进入右子树删除最小值对应的节点。
        this.removeNode(node.right, minKey);
        return node;
    }
}