首页 > 其他 > 详细

利用栈实现二叉树的先序、中序、后序遍历

时间:2020-07-15 16:01:44      阅读:151      评论:0      收藏:0      [点我收藏+]

技术分享图片

先序:A->B->D->E->C->F->G

function preTraverStack(root,cb){
    let stack = new Stack()
    stack.push(root)
    while(!stack.isEmpty()){
        let node = stack.pop()
        if(node.right != null){
            stack.push(node.right)
        }
        if(node.left != null){
            stack.push(node.left)
        }
        cb(node.val)
    }
}

中序:D->B->E->A->F->C->G

function inorderTraverStack(root,cb){
    let stack = new Stack()
    stack.push(root)
    while(!stack.isEmpty()){
        while(stack.peek().left != null){
            stack.push(stack.peek().left)
        }
        while(!stack.isEmpty()){
            let node = stack.pop()
            cb(node.val)
            if(node.right != null){
                stack.push(node.right)
                break
            }
        }
    }
}

后序:D->E->B->F->G->C->A

function postTraverStack(root,cb){
    let stack = new Stack()
    stack.push(root)
    let lastNode = null
    while(!stack.isEmpty()){
        while(stack.peek().left != null){
            stack.push(stack.peek().left)
        }
        while(!stack.isEmpty()){
            if(lastNode == stack.peek().right || stack.peek().right == null){
                let node = stack.pop()
                cb(node.val)
                lastNode = node
            }else if(stack.peek().right != null){
                stack.push(stack.peek().right)
                break
            }
        }
    }
}

  

利用栈实现二叉树的先序、中序、后序遍历

原文:https://www.cnblogs.com/zhenjianyu/p/13305132.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!