SOURCE

// 树的基础概念
// 一个树只有一个根节点
// 每一个值都是一个节点
// 有子节点的称之为内部节点
// 没有子节点的称此为叶子节点
// 计量一个节点子节点数量的单位为度,如叶子节点为0度

// 二叉搜索树
// 每个节点的子节点最多只能有两个
// 左侧节点比父节点小,右侧节点比父节点大

// 常见操作
// 插入节点
// 查找节点
// 中序遍历
// 先序遍历
// 后序遍历
// 最小节点
// 最大节点
// 移除节点

// 节点辅助类
let Node = function(element){
    this.element = element;
    this.left = null;
    this.right = null;
}
// 插入子节点辅助类
let insertNode = function(node, newNode){
    if(newNode.element < node.element){
        if(node.left === null){
            node.left = newNode
        }else{
            insertNode(node.left, newNode)
        }
    }else{
        if(node.right === null){
            node.right = newNode
        }else{
            insertNode(node.right, newNode)
        }
    }
}

class BinarySearchTree{
    constructor(){
        this.root = null
    }
    // 插入节点
    insert(key){
        let newNode = new Node(key)
        if(this.root === null){
            this.root = newNode
        } else {
            insertNode(this.root, newNode)
        }
        
    }
    // 查找节点
    searchNode(node, key){
        if(node === null) return null
        if(key < node.element){
            this.searchNode(node.left, key)
        } if(key > node.element){
            this.searchNode(node.right, key)
        }else{
            return node
        }
    }
    search(key){
        this.searchNode(this.root, key)
    }
    // 先序遍历
    preOrderTraverseNode(node, callback){
        if(node !== null){
            callback(node.element)
            this.preOrderTraverseNode(node.left, callback)
            this.preOrderTraverseNode(node.right, callback)
        }
    }
    preOrderTraverse(callback){
        this.preOrderTraverseNode(this.root, callback)
    }
    // 中序遍历
    inOrderTraverseNode(node, callback){
        if(node !== null){
            this.inOrderTraverseNode(node.left, callback)
            callback(node.element)
            this.inOrderTraverseNode(node.right, callback)
        }
    }
    inOrderTraverse(callback){
        this.inOrderTraverseNode(this.root, callback)
    }
    // 后序遍历
    postOrderTraverseNode(node, callback){
        if(node !== null){
            this.postOrderTraverseNode(node.left, callback)
            this.postOrderTraverseNode(node.right, callback)
            callback(node.element)
        }
    }
    postOrderTraverse(callback){
        this.postOrderTraverseNode(this.root, callback)
    }
    // 最小节点
    minNode(node){
        if(node === null) return null
        while(node.left !== null){
            node = node.left
        }
        return node
    }
    min(){
        return this.minNode(this.root)
    }
    // 最大节点
    maxNode(node){
        if(node === null) return null
        while(node.right !== null){
            node = node.right
        }
        return node
    }
    max(){
        return this.maxNode(this.root)
    }
    // 移除节点 三种情况,重点分析有两个子节点的情况
    removeNode(node, key){
        if(node === null) return null
        if(key < node.element){
            node.left = this.removeNode(node.left, key)
            return node
        }else if (key > node.element){
            node.right = this.removeNode(node.right, key)
            return node
        }else{
            // 第一种情况, 没有子叶
            if(node.left === null && node.right === null){
                node = null
                return node
            }
            // 有一个子叶
            if(node.left === null){
                node = node.right
                return node
            }else if(node.right === null){
                node = node.left
                return node
            }
            // 有两个子叶,关键,将右侧子叶最小的节点,替换删除的节点
            let rightSonMin = this.minNode(node.right)
            node.element = rightSonMin.element
            node.right = this.removeNode(node.right, rightSonMin.element)
            return node
        }

    }
    remove(key){
        return this.removeNode(this.root, key)
    }
}
let tree = new BinarySearchTree();
tree.insert(11);
tree.insert(7);
tree.insert(15);
tree.insert(5);
tree.insert(9);
tree.insert(13);
tree.insert(20);
tree.insert(3);
tree.insert(6);
tree.insert(8);
tree.insert(10);
tree.insert(12);
tree.insert(14);
tree.insert(18);
tree.insert(25);

tree.preOrderTraverse((value) => console.log(value));
// tree.inOrderTraverse((value) => console.log(value));
// tree.postOrderTraverse((value) => console.log(value));

// console.log(tree.min().element); // 3
// console.log(tree.max().element); // 25
// console.log(tree.search(1) ? 'Key 1 found.' : 'Key 1 not found.'); // Key 1 not found.
// console.log(tree.search(8) ? 'Key 8 found.' : 'Key 8 not found.'); // Key 8 found.

// 测试移除节点
// 移除没有子节点的情况
console.log(tree.remove(3))
tree.preOrderTraverse((value) => console.log(value));
// 移除有一个子节点的情况
console.log(tree.remove(5))
tree.preOrderTraverse((value) => console.log(value));
// 移除有两个子节点的情况
console.log(tree.remove(9))
tree.preOrderTraverse((value) => console.log(value));