master

分支 (1)

标签 (2)

管理

管理

master

v1.1.0

v1.0.0

sort_two_fork_tree
/
binarySortTree.html

<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <title>排序二叉树</title>
</head>

<body>
    <script>
    var BinaryTree = function() {
        var Node = function(key) {
            this.key = key;
            this.left = null;
            this.right = null;
        }
        var root = null;
        var insertNode = function(node, newNode) {
            if (newNode.key < node.key) {
                if (node.left === null) {
                    node.left = newNode
                } else {
                    insertNode(node.left, newNode)
                }
            } else if (newNode.key > node.key) {
                if (node.right === null) {
                    node.right = newNode
                } else {
                    insertNode(node.right, newNode)
                }
            }
        }
        this.insert = function(key) {
            var node = new Node(key)
            if (root === null) {
                root = node
            } else {
                insertNode(root, node)
            }
        }
        this.show_root = function() {
            console.log(JSON.stringify(root))
        }
        var inOrderTraverseNode = function(node, callback) {
            if (node !== null) {
                inOrderTraverseNode(node.left, callback);
                callback(node.key);
                inOrderTraverseNode(node.right, callback);
            }
        }
        var preOrderTraverse = function(node, callback) {
            if (node !== null) {
                callback(node.key);
                preOrderTraverse(node.left, callback);
                preOrderTraverse(node.right, callback);
            }
        }
        var postOrderTraverse = function(node, callback) {
            if (node !== null) {
                postOrderTraverse(node.left, callback);
                postOrderTraverse(node.right, callback);
                callback(node.key);
            }
        }
        this.inOrderTraverse = function(callback) {
            inOrderTraverseNode(root, callback); // 从小到大排序
        }
        this.preOrderTraverse = function(callback) {
            preOrderTraverse(root, callback); // 复制二叉树
        }
        this.postOrderTraverse = function(callback) {
            postOrderTraverse(root, callback); // 文件系统遍历
        }
        var minNode = function(node) {
            if (node) {
                while (node && node.left !== null) {
                    node = node.left
                }
                return node.key
            }
            return null;
        }
        var maxNode = function(node) {
            if (node) {
                while (node && node.right !== null) {
                    node = node.right
                }
                return node.key
            }
            return null;
        }
        var findNode = function(node, key) {
            if (node) {
                if (node.key === key) {
                    return node
                }
                if (key < node.key) {
                    return findNode(node.left, key)
                }
                if (key > node.key) {
                    return findNode(node.right, key)
                }
            }
            return null
        }

        var findMinNode = function(node){
        	if(node){
        		while(node && node.left !== null){
        			node = node.left;
        		}
        		return node
        	}
        	return null
        }

        var removeNode = function(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;
        		}
        		if (node.left === null){
        			node = node.right;
        			return node;
        		}
        		if(node.right === null){
        			node = node.left;
        			return node;
        		}
        		var minNode = findMinNode(node.right);
        		node.key = minNode.key;
        		node.right = removeNode(node.right,minNode.key);
        		return node;
        	}

        }
        // 最小
        this.min = function() {
            return minNode(root)
        }
        // 最大
        this.max = function() {
            return maxNode(root)
        }
        // 查找
        this.findNode = function(key) {
            return findNode(root, key)
        }
        // 删除
        this.remove = function(key){
        	return removeNode(root,key)
        }
    }

    var nodes = [8, 3, 10, 1, 6, 14, 4, 7, 13];
    var binaryTree = new BinaryTree();
    nodes.forEach((item, index) => {
        binaryTree.insert(item)
    })
    binaryTree.show_root();
    var callback = console.log;
    // binaryTree.inOrderTraverse(callback)
    // binaryTree.preOrderTraverse(callback)
    // binaryTree.postOrderTraverse(callback)
    console.log('min:', binaryTree.min())
    console.log('max:', binaryTree.max())
    console.log(binaryTree.findNode(14))
    console.log('remove',binaryTree.remove(8))
    binaryTree.show_root();
    </script>
</body>

</html>