排序二叉树——后序遍历

假如你收悉了中序遍历和前序遍历,那么后续遍历的实现相信你也能写出来的。那么后续遍历是怎么一个流程呢?

中序遍历可以看做是把节点按照大小打印出来,而前序编列虽说是复制一个二叉树,其实分析他的运行流程,我们可以看出,前序编列是从根节点开始遍历最左边的值,然后在遍历而右边的值。而后续遍历呢,就是先编列节点左边的值,在遍历节点右边的值,最后在遍历节点本身。就好比前序遍历做的是捕获行为,而后续遍历做的是冒泡行为。下面就开始代码:

<script type="text/javascript">
    function BinaryyTree() {
        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 (node.right==null){
                    node.right=newNode;
                }else {
                    insertNode(node.right,newNode);
                }
            }
        }
        this.insert=function (key) {              //二叉树创建接口
            var newNode= new Node(key);
            if (root===null){
                root=newNode;
            }else {
                insertNode(root,newNode);
            }
        }
var postOrderTraverseNode=function (node, callback) { //后序遍历的实现流程
if(node!==null){
postOrderTraverseNode(node.left,callback);
postOrderTraverseNode(node.right,callback);
callback(node.key);
}
}
this.postOrderTraverse=function (callback) { // 后序遍历的接口
postOrderTraverseNode(root,callback);
}
}
var node=[7,3,9,5,12,21,18,32]; //创建一个数组
var binaryyTree= new BinaryyTree(); //构造一颗二叉树
node.forEach(function (key) { //创建一颗二叉树
binaryyTree.insert(key);
})
var callback=function (key) { //回调函数,实现输出
console.log(key);
};
binaryyTree.postOrderTraverse(callback); //打印后序遍历的结果
</script>

最后我们在控制台输出,这里我建议一定要打开控制台,看看是否能正确输出,不能正确输出那么就说明代码哪里出错了。根据提示做出修改。你也可以在“遍历接口”到“实现流程”之间设置断点,看看程序是如何跑的。下面是在控制台的输出结果

后续遍历

陈健的个人博客,记录生活所见所感、学习笔记。专注于Web前端_SEO教程_读书心得。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

返回主页看更多
狠狠的抽打博主 支付宝 扫一扫