乐趣区

关于javascript:数据结构二叉树中序递归法遍历

接数据结构 - 初学二叉树创立文章后,咱们在来对二叉树进行中序排序,输入一个有序数据。
二叉树的中序遍历就是首先遍历左子树,而后拜访以后节点,最初遍历右子树。对于上面的二叉树,中序遍历后果如下:

这是思路最简略的办法,容易想到并且容易实现。递归的终止条件是以后节点是否为空。首先递归调用遍历左子树,而后拜访以后节点,最初递归调用右子树。代码如下:

       function BinaryTree(){var Node = function(key){
                this.key = key;
                this.left = null;
                this.right = null;
            }

            // 插入节点 大于旧节点,放在 node.right 小于旧节点,放在 node.left
            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)
                    }
                }
            }
            var root = null;
            // 创立节点并插到相应的地位
            this.insert = function(key){var newNode = new Node(key)
                if(root === null){root = newNode}else{insertNode(root,newNode)
                }
            }
            
            // 遍历节点 左子树 父 右子树 
            var inOrderTraverseNode = function(node,callback){if(node !== null){inOrderTraverseNode(node.left,callback)
                    callback(node.key)
                    inOrderTraverseNode(node.right,callback)
                }
            }
            // 中序遍历
            this.inOrderTraverse = function(callback){inOrderTraverseNode(root,callback)
            }
        }

        var nodes = [8,3,10,1,6,14,4,7,13]
        var binaryTree = new BinaryTree()
        nodes.forEach(key =>{binaryTree.insert(key)
        })
        // 回调函数只做打印以后值
        var callback = function(key){console.log(key)
        }
        binaryTree.inOrderTraverse(callback)
退出移动版