javascript二叉树基本功能实现

都是常用的功能。

删除是最复杂的。。

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>test</title>
    <script src="js/lib/angular.min.js"></script>
    <script >
        function BinarySearchTree(){
            var Node = function(key){
                this.key = key;
                this.left = null;
                this.right = null;
            };
            var root = null;

            this.insert = function(key){
                var newNode = new Node(key);

                if (root === null) {
                    root = newNode;
                } else {
                    insertNode(root, newNode);
                }
            };

            var insertNode = function(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.inOrderTraverse = function(callback) {
                inOrderTraverseNode(root, callback);
            };

            var inOrderTraverseNode = function(node, callback) {
                if (node !== null) {
                    inOrderTraverseNode(node.left, callback);
                    callback(node.key);
                    inOrderTraverseNode(node.right, callback);
                }
            };

            this.preOrderTraverse = function(callback){
                        preOrderTraverseNode(root, callback);
                    };

                    var preOrderTraverseNode = function (node, callback) {
                        if (node !== null) {
                            callback(node.key); //{1}
                            preOrderTraverseNode(node.left, callback); //{2}
                            preOrderTraverseNode(node.right, callback); //{3}
                        }
                    };

                    this.postOrderTraverse = function(callback){
                        postOrderTraverseNode(root, callback);
                    };

            var postOrderTraverseNode = function (node, callback) {
                        if (node !== null) {
                            postOrderTraverseNode(node.left, callback); //{1}
                            postOrderTraverseNode(node.right, callback); //{2}
                            callback(node.key); //{3}
                        }
                    };

                    this.min = function() {
                        return minNode(root);
                    };

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

                    this.max = function() {
                        return maxNode(root);
                    };

                    var maxNode = function (node) {
                        if (node){
                            while (node && node.right !== null) { //{5}
                                node = node.right;
                            }
                            return node.key;
                        }
                        return null;
                    };

                    this.search = function(key) {
                        return searchNode(root, key);
                    };

                    var searchNode = function(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);
                        }else{
                            return true;
                        }
                    };

                    this.remove = function(key) {
                        root = removeNode(root, key);
                    };

                    var removeNode = function(node, key){
                        if (node === null){ //{2}
                            return null;
                        }
                        if (key < node.key){ //{3}
                            node.left = removeNode(node.left, key); //{4}
                            return node; //{5}
                        } else if (key > node.key){ //{6}
                            node.right = removeNode(node.right, key); //{7}
                            return node; //{8}
                        } else { //键等于node.key
                            //第一种情况——一个叶节点
                            if (node.left === null && node.right === null){ //{9}
                            node = null; //{10}
                            return node; //{11}
                            }
                            //第二种情况——一个只有一个子节点的节点
                            if (node.left === null){ //{12}
                            node = node.right; //{13}
                            return node; //{14}
                            } else if (node.right === null){ //{15}
                            node = node.left; //{16}
                            return node; //{17}
                            }
                            //第三种情况——一个有两个子节点的节点
                            var aux = findMinNode(node.right); //{18}
                            node.key = aux.key; //{19}
                            node.right = removeNode(node.right, aux.key); //{20}
                            return node; //{21}
                        }
                    };

        }

        function printNode(value) {
                console.log(value);
        }

          var tree = new BinarySearchTree();
          tree.insert(11);
          tree.insert(7);
                tree.insert(15);
                tree.insert(5);
                tree.insert(3);
                tree.insert(9);
                tree.insert(8);
                tree.insert(10);
                tree.insert(13);
                tree.insert(12);
                tree.insert(14);
                tree.insert(20);
                tree.insert(18);
                tree.insert(25);
                tree.insert(6);

                tree.inOrderTraverse(printNode);
                tree.preOrderTraverse(printNode);
                tree.postOrderTraverse(printNode);
                console.log(tree.min());
                console.log(tree.max());
                console.log(tree.search(1) ? 'Key 1 found.' : 'Key 1 not found.');
                console.log(tree.search(8) ? 'Key 8 found.' : 'Key 8 not found.');

    </script>

</head>
<body>

</body>
</html>

javascript二叉树基本功能实现

上一篇:GIt帮助文档之创建新的Git仓库——现有目录下,通过导入所有文件来创建


下一篇:poj 2773 利用欧拉函数求互质数