/** 二叉查找树 */
{
    function Node(data, left, right) {
        this.data = data;
        this.left = left;
        this.right = right;
        this.show = show;
        this.count = 1;
    }

    function show() {
        return this.data
    }

    function BST() {
        this.root = null;
        this.insert = insert;
        this.inOrder = inOrder;
        this.preOrder = preOrder;
        this.postOrder = postOrder;
        this.getMax = getMax;
        this.getMin = getMin;
        this.find = find;
        this.remove = remove;
        this.update = update;
        this.allCount = 0; // 统计总的节点数
        this.edges = 0;
    }

    // 更新
    function update(data) {
        var grade = this.find(data)
        grade.count++
        return grade 
    }

    // 插入元素
    function insert(data) {
        var n = new Node(data, null, null)
        
        if (this.root == null) {
            this.root = n;
            this.allCount++; // 插入一个节点 节点数增1
        } else {
            var current = this.root;
            var parent;
            
            while (true) {
                parent = current;
                if (data < current.data) {
                    current = current.left
                    if (current == null) {
                        parent.left = n;
                        this.allCount++; // 插入一个节点 节点数增1
                        this.edges++; // 除根节点外，每增加一个节点添加一条边
                        break;
                    }
                } else {
                    current = current.right;
                    if (current == null) {
                        parent.right = n;
                        this.allCount++; // 插入一个节点 节点数增1
                        this.edges++; // 除根节点外，每增加一个节点添加一条边
                        break;
                    }
                }
            }
        }
    }

    // 中序遍历 从小到大排序
    function inOrder(node) {
        if (!(node == null)) {
            inOrder(node.left)
            console.log(node.show() + ' ' + node.count)
            inOrder(node.right)
        }
    }

    // 先序遍历 
    function preOrder (node) {
        if(!(node == null)) {
            console.log(node.show())
            preOrder(node.left)
            preOrder(node.right)
        }
    }
    
    // 后序遍历
    function postOrder(node) {
        if(!(node == null)) {
            postOrder(node.left)
            postOrder(node.right)
            console.log(node.show())
        }
    }

    // 最小值
    function getMin() {
        var current = this.root;
        while (!(current.left == null)) {
            current = current.left;
        }
        return current.data
    }

    // 最大值
    function getMax() {
        var current = this.root
        while(!(current.right == null)) {
            current = current.right
        }
        return current.data
    }
    
    // 查找给定值
    function find(data) {
        var current = this.root
        
        while(current != null) {
            if(current.data == data) {
                return current
            } else if(current.data > data) {
                current = current.left
            } else {
                current = current.right
            }
        }

        return null; // 找不到返回null 
    }

    function remove(data) {
        if(this.find(data)) {
            this.allCount--;
            this.edges--;
            root = removeNode(this.root, data)
        }
    }

    function removeNode(node, data) {
        if(node == null) {return null}

        if(data == node.data) {
            if(node.left == null && node.right == null) {
                return null
            }
            if(node.left == null && node.right != null) {
                return node.right
            }
            if(node.right == null && node.left != null) {
                return node.left 
            }

            // 有两个子节点的节点 找到右子树上的最小值
            var tempNode = getSmallest(node.right)
            node.data = tempNode.data;

            node.right = removeNode(node.right, tempNode.data)
            return node 
        } else if (data < node.data) {
            node.left = removeNode(node.left, data)
            return node;
        } else {
            node.right = removeNode(node.right, data)
            return node;
        }
    }

    // 子树上最小值
    function getSmallest(node) {
        var current = node;
        while (!(current.left == null)) {
            current = current.left;
        }
        return current
    }

    var nums = new BST();
    // nums.insert(8)
    // nums.insert(3)
    // nums.insert(10)
    // nums.insert(1)
    // nums.insert(6)
    // nums.insert(14)
    // nums.insert(4)
    // nums.insert(7)
    // nums.insert(13)

    console.log(nums.allCount)
    console.log(nums.edges)
    nums.remove(3)
    console.log(nums.allCount)
    console.log(nums.edges)

    
    // console.log('-------')
    // preOrder(nums.root) 
    // console.log('-----')
    // postOrder(nums.root) 

    // console.log(nums.getMin())
    // console.log(nums.getMax())
    
    // console.log(nums.find(8))
    // 找不到的就插入 找到的就更新

    var arr = []

    for(let i = 0; i < 100; i++) {
        arr[i] = Math.floor(Math.random()*100)
    }


    for(var i = 0; i < arr.length; i++) {
        let data = arr[i]
        var dataFind = nums.find(data)
        
        if(dataFind == null) {
            nums.insert(data)
        } else {
            nums.update(data)
        }
    }

    inOrder(nums.root) 

    console.log(nums)
}