JS实现二叉树算法

转载自:https://www.fenxianglu.cn/article/403

二叉树的遍历(traversing binary tree)是指从根结点出发,按照某种次序依次访问二叉树中所有的结点,使得每个结点被访问依次且仅被访问一次。

根据根节点访问的顺序,分为前序遍历、中序遍历、后序遍历

前序遍历: 先访问根节点,然后分别前序遍历左右子树
中序遍历: 先中序遍历左子树,访问根节点,在中序遍历右子树
后序遍历: 先中序遍历左子树,在中序遍历右子树,最后访问根节点
还有一种层次遍历:从根节点开始,从上至下逐层遍历,在同一层中,则按照从左到右的顺序对节点逐个访问

JS实现二叉树算法-

如果我们要遍历上图中二叉树中,则
前序遍历: F C A D B E H G M
中序遍历: A C B D F H E M G
后序遍历: A B D C H M G E F
层次遍历: F C E A D H G B M

完整代码

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

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

<body>
    <script>
    function TreeNode(val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }

    var Tree = (function() {
        var root = null;

        var build = function(valueList) {
            if (!valueList || valueList.length === 0) {
                return
            }
            root = new TreeNode(valueList.shift())
            var queue = [root]
            var tempQueue = []
            while (queue.length > 0) {
                var node = queue.shift();
                if (valueList.length === 0) { //构建结束
                    break;
                }
                var leftVal = valueList.shift()
                if (leftVal !== null) { //构建左子节点
                    node.left = new TreeNode(leftVal)
                    tempQueue.push(node.left)
                }

                if (valueList.length === 0) { //构建结束
                    break;
                }
                var rightVal = valueList.shift()
                if (rightVal !== null) { //构建又子节点
                    node.right = new TreeNode(rightVal)
                    tempQueue.push(node.right)
                }
                if (queue.length === 0) { //本次构建结束
                    queue = tempQueue;
                }
            }
            return this;
        }

        var preOrder = function() {
            return _preOrder(root)
        }
        var inOrder = function() {
            return _inOrder(root)
        }
        var postOrder = function() {
            return _postOrder(root)
        }

        //层次遍历或者广度优先遍历
        var bfs = function() {
            if (!root) { return }
            var queue = [],
                result = []

            queue.push(root)
            while (queue.length > 0) {
                var node = queue.shift()
                result.push(node.val)
                if (node.left) {
                    queue.push(node.left)
                }
                if (node.right) {
                    queue.push(node.right)
                }
            }
            return result
        }

        // 层次遍历2 把每一层的节点放到一个数组里,
        // 返回结构: [[leve1, leve1],[leve2,leve1],[leve3, leve3]]
        var bfs2 = function() {
            if (!root) { return }
            var queue = [],
                result = []
            queue.push(root)

            var levelArr = [];
            var tempQueue = []

            while (queue.length > 0) {
                var node = queue.shift()

                levelArr.push(node.val)
                if (node.left) {
                    tempQueue.push(node.left)
                }
                if (node.right) {
                    tempQueue.push(node.right)
                }
                if (queue.length === 0) { //说明本层遍历结束
                    result.push(levelArr.concat())
                    levelArr = []
                    queue = tempQueue
                    tempQueue = []
                }
            }
            return result
        }

        //private methods
        var _preOrder = function(node, result) {
            result = result || []
            if (node) {
                result.push(node.val)
                _preOrder(node.left, result)
                _preOrder(node.right, result)
            }
            return result
        }
        var _inOrder = function(node, result) {
            result = result || []
            if (node) {
                _inOrder(node.left, result)
                result.push(node.val)
                _inOrder(node.right, result)
            }
            return result
        }
        var _postOrder = function(node, result) {
            result = result || []
            if (node) {
                _postOrder(node.left, result)
                _postOrder(node.right, result)
                result.push(node.val)
            }
            return result
        }
        return {
            build: build,
            preOrder: preOrder,
            inOrder: inOrder,
            postOrder: postOrder,
            bfs: bfs,
            bfs2: bfs2
        }
    })();
    var nodeList =  [3,9,20,null,null,15,7]
    var tree = Tree.build(nodeList);
    console.log('前序遍历:', tree.preOrder())
    console.log('中序遍历:', tree.inOrder())
    console.log('后序遍历:', tree.postOrder())
    console.log('层次遍历:', tree.bfs())
    console.log('层次遍历(分层显示):', tree.bfs2())
    </script>
</body>

</html>
------本页内容已结束,喜欢请分享------

感谢您的来访,获取更多精彩文章请收藏本站。

© 版权声明
THE END
喜欢就支持一下吧
点赞7 分享
评论 抢沙发
头像
欢迎您留下宝贵的见解!
提交
头像

昵称

取消
昵称表情代码图片