"use strict";
//        -8-
//     3         10
//  1     6         14
//    4  7      13
var nodes = [8, 3, 10, 1, 6, 14, 4, 7, 13];
function BinaryTree() {
    //↓↓↓↓↓↓↓↓二叉树创建↓↓↓↓↓↓↓↓
    var Node = function (key) {
        this.key = key;
        this.left = null;
        this.right = null
    };
    var root = null;

    function insertNode(node, newNode) {
        if (newNode.key < node.key) {
            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);
        }
    }

    this.insert = function (key) {
        var newNode = new Node(key);
        if (root === null)
            root = newNode;
        else
            insertNode(root, newNode)
    };
    //↑↑↑↑↑↑↑↑二叉树创建↑↑↑↑↑↑↑↑
    //↓↓↓↓↓↓↓↓前序遍历的代码实现↓↓↓↓↓↓↓↓
    function preOrderTraverseNode(node, callback) {
        if (node) {
            callback(node.key)
            preOrderTraverseNode(node.left, callback)
            preOrderTraverseNode(node.right, callback)
        }
    }

    this.preOrderTraverse = function (callback) {
        preOrderTraverseNode(root, callback)
    }
    //↑↑↑↑↑↑↑↑前序遍历的代码实现↑↑↑↑↑↑↑
    //↓↓↓↓↓↓↓↓中序遍历的代码实现↓↓↓↓↓↓↓↓
    function inOrderTraverseNode(node, callback) {
        if (node) {
            inOrderTraverseNode(node.left, callback)
            callback(node.key);
            inOrderTraverseNode(node.right, callback)
        }
    }

    this.inOrderTraverse = function (callback) {
        inOrderTraverseNode(root, callback)
    }
    //↑↑↑↑↑↑↑↑中序遍历的代码实现↑↑↑↑↑↑↑
    //↓↓↓↓↓↓↓↓后序遍历的代码实现↓↓↓↓↓↓↓↓
    function postOrderTraverseNode(node, callback) {
        if (node) {
            postOrderTraverseNode(node.left, callback)
            postOrderTraverseNode(node.right, callback)
            callback(node.key);
        }
    }

    this.postOrderTraverse = function (callback) {
        postOrderTraverseNode(root, callback)
    }
    //↑↑↑↑↑↑↑↑后序遍历的代码实现↑↑↑↑↑↑↑
    //↓↓↓↓↓↓↓↓最小数↓↓↓↓↓↓↓↓
    function minNode(node) {
        if (node) {
            while (node && node.left !== null) {
                node = node.left
            }
            return node.key;
        }
        return null
    }

    this.min = function () {
        return minNode(root)
    }
    //↑↑↑↑↑↑↑↑最小数↑↑↑↑↑↑↑
    //↓↓↓↓↓↓↓↓最大数↓↓↓↓↓↓↓↓
    function maxNode(node) {
        if (node) {
            while (node && node.right) {
                node = node.right
            }
            return node.key;
        }
        return null
    }

    this.max = function () {
        return maxNode(root)
    }
    //↑↑↑↑↑↑↑↑最大数↑↑↑↑↑↑↑
    //↓↓↓↓↓↓↓↓查找↓↓↓↓↓↓↓↓
    function searchNode(node, key) {
        if (node === null)
            return false;
        if (key < node.key)
            return searchNode(node.left, key)
        else if (key > node.key)
            return searchNode(node.right, key)
        return true
    }

    this.search = function (key) {
        return searchNode(root, key)
    }
    //↑↑↑↑↑↑↑↑查找↑↑↑↑↑↑↑
    var findMinNode = function (node) {
        if (node) {
            while (node === null && node.left !== null) {

            }
            return node;
        }
        return null
    };
    //↓↓↓↓↓↓↓↓二叉树叶子节点的删除原理↓↓↓↓↓↓↓↓
    function removeNode(node, key) {
        if (node === null)
            return null;
        if (key < node.key) {
            node.left = removeNode(node.left, key)
            return node
        } else if (key > node.key) {
            node.right = removeNode(node.right, key)
            return node
        } else {
            if (node.left === null && node.right === null) {
                node = null;
                return node
            }else
            if (node.left === null) {
                node = node.right;
                return node;
            }else if (node.right === null) {
                node = node.left;
                return node;
            }
            //左右两个节点删除
            var aux = findMinNode(node.right);
            node.key = aux.key;
            node.right = removeNode(node.right,aux.key)
            return node
        }

    }

    this.remove = function (key) {
        return removeNode(root, key)
    }
    //↑↑↑↑↑↑↑↑二叉树叶子节点的删除原理↑↑↑↑↑↑↑
}
var binaryTree = new BinaryTree();
nodes.forEach(function (key) {
    binaryTree.insert(key)
});
function callback(key) {
    console.log(key);
}
// binaryTree.preOrderTraverse(callback);
// binaryTree.inOrderTraverse(callback);
// binaryTree.postOrderTraverse(callback);
// console.log(nodes, '最小数:', binaryTree.min());
// console.log(nodes, '最大数:', binaryTree.max());
binaryTree.remove(3)
binaryTree.inOrderTraverse(callback);