js实现二叉树算法丨技术开发分享录

js实现二叉树算法

{{ detail.nickname }}

转载 翻译 {{ formatTime(detail.create_time) }} 字数 {{ detail.content && detail.content.length }} 阅读 {{ detail.read_num }} {{ formatTag(v) }}

"二叉树的遍历(traversing binary tree)是指从根结点出发,按照某种次序依次访问二叉树中所有的结点,使得每个结点被访问依次且仅被访问一次。\n\n根据根节点访问的顺序,分为前序遍历、中序遍历、后序遍历\n\n前序遍历: 先访问根节点,然后分别前序遍历左右子树\n中序遍历: 先中序遍历左子树,访问根节点,在中序遍历右子树\n后序遍历: 先中序遍历左子树,在中序遍历右子树,最后访问根节点\n还有一种层次遍历:从根节点开始,从上至下逐层遍历,在同一层中,则按照从左到右的顺序对节点逐个访问\n\n![](https://upload-images.jianshu.io/upload_images/10609541-34fec21c68c6bf0e.jpg?imageMogr2/auto-orient/strip|imageView2/2/w/822/format/webp =350x250)\n\n如果我们要遍历上图中二叉树中,则\n前序遍历: F C A D B E H G M\n中序遍历: A C B D F H E M G\n后序遍历: A B D C H M G E F\n层次遍历: F C E A D H G B M\n\n完整代码\n\n```html\n<!DOCTYPE html>\n<html lang=\"en\">\n\n<head>\n    <meta charset=\"UTF-8\">\n    <title>二叉树</title>\n</head>\n\n<body>\n    <script>\n    function TreeNode(val) {\n        this.val = val;\n        this.left = null;\n        this.right = null;\n    }\n\n    var Tree = (function() {\n        var root = null;\n\n        var build = function(valueList) {\n            if (!valueList || valueList.length === 0) {\n                return\n            }\n            root = new TreeNode(valueList.shift())\n            var queue = [root]\n            var tempQueue = []\n            while (queue.length > 0) {\n                var node = queue.shift();\n                if (valueList.length === 0) { //构建结束\n                    break;\n                }\n                var leftVal = valueList.shift()\n                if (leftVal !== null) { //构建左子节点\n                    node.left = new TreeNode(leftVal)\n                    tempQueue.push(node.left)\n                }\n\n                if (valueList.length === 0) { //构建结束\n                    break;\n                }\n                var rightVal = valueList.shift()\n                if (rightVal !== null) { //构建又子节点\n                    node.right = new TreeNode(rightVal)\n                    tempQueue.push(node.right)\n                }\n                if (queue.length === 0) { //本次构建结束\n                    queue = tempQueue;\n                }\n            }\n            return this;\n        }\n\n        var preOrder = function() {\n            return _preOrder(root)\n        }\n        var inOrder = function() {\n            return _inOrder(root)\n        }\n        var postOrder = function() {\n            return _postOrder(root)\n        }\n\n        //层次遍历或者广度优先遍历\n        var bfs = function() {\n            if (!root) { return }\n            var queue = [],\n                result = []\n\n            queue.push(root)\n            while (queue.length > 0) {\n                var node = queue.shift()\n                result.push(node.val)\n                if (node.left) {\n                    queue.push(node.left)\n                }\n                if (node.right) {\n                    queue.push(node.right)\n                }\n            }\n            return result\n        }\n\n        // 层次遍历2 把每一层的节点放到一个数组里,\n        // 返回结构: [[leve1, leve1],[leve2,leve1],[leve3, leve3]]\n        var bfs2 = function() {\n            if (!root) { return }\n            var queue = [],\n                result = []\n            queue.push(root)\n\n            var levelArr = [];\n            var tempQueue = []\n\n            while (queue.length > 0) {\n                var node = queue.shift()\n\n                levelArr.push(node.val)\n                if (node.left) {\n                    tempQueue.push(node.left)\n                }\n                if (node.right) {\n                    tempQueue.push(node.right)\n                }\n                if (queue.length === 0) { //说明本层遍历结束\n                    result.push(levelArr.concat())\n                    levelArr = []\n                    queue = tempQueue\n                    tempQueue = []\n                }\n            }\n            return result\n        }\n\n        //private methods\n        var _preOrder = function(node, result) {\n            result = result || []\n            if (node) {\n                result.push(node.val)\n                _preOrder(node.left, result)\n                _preOrder(node.right, result)\n            }\n            return result\n        }\n        var _inOrder = function(node, result) {\n            result = result || []\n            if (node) {\n                _inOrder(node.left, result)\n                result.push(node.val)\n                _inOrder(node.right, result)\n            }\n            return result\n        }\n        var _postOrder = function(node, result) {\n            result = result || []\n            if (node) {\n                _postOrder(node.left, result)\n                _postOrder(node.right, result)\n                result.push(node.val)\n            }\n            return result\n        }\n        return {\n            build: build,\n            preOrder: preOrder,\n            inOrder: inOrder,\n            postOrder: postOrder,\n            bfs: bfs,\n            bfs2: bfs2\n        }\n    })();\n    var nodeList =  [3,9,20,null,null,15,7]\n    var tree = Tree.build(nodeList);\n    console.log('前序遍历:', tree.preOrder())\n    console.log('中序遍历:', tree.inOrder())\n    console.log('后序遍历:', tree.postOrder())\n    console.log('层次遍历:', tree.bfs())\n    console.log('层次遍历(分层显示):', tree.bfs2())\n    </script>\n</body>\n\n</html>\n```\n\n参考链接\n\n- 原文链接:https://www.jianshu.com/p/3097664f80e8"
PS:写作不易,如要转裁,请标明转载出处。

如果此篇对您有帮助,可小额赞助,以兹鼓励!

猜你想看