月眸


二叉树遍历

毛毛小妖 2019-10-08 15浏览 0条评论
首页/ 正文
分享到: / / / /

一、前序遍历

/**
 * 前序遍历:通过栈保留待操作值
 */
public static void preOrder(TreeNode head){
    if(head == null){
        return;
    }

    Stack<TreeNode> stack = new Stack<>();
    stack.push(head);
    while(!stack.isEmpty()){
        TreeNode treeNode = stack.pop();
        System.out.print(treeNode.value + " ");
        if(treeNode.right != null){
            stack.push(treeNode.right);
        }
        if(treeNode.left != null){
            stack.push(treeNode.left);
        }
    }
    System.out.println();
}

二、中序遍历

/**
 * 中序遍历:当有结点时入栈,当没结点时出栈并输出
 */
public static void midOrder(TreeNode head){
    if(head == null){
        return;
    }

    Stack<TreeNode> stack = new Stack<>();
    while(head != null || !stack.isEmpty()){
        if(head != null){
            stack.push(head);
            head = head.left;
        }else {
            TreeNode treeNode = stack.pop();
            System.out.print(treeNode.value + " ");
            head = treeNode.right;
        }
    }
    System.out.println();
}

三、后序遍历

/**
 * 后序遍历:通过栈保留待操作值,类似于前序遍历
 */
public static void postOrder(TreeNode head){
    if(head == null){
        return;
    }

    Stack<TreeNode> stack1 = new Stack<>();
    Stack<TreeNode> stack2 = new Stack<>();
    stack1.push(head);
    while(!stack1.isEmpty()){
        TreeNode treeNode = stack1.pop();
        stack2.push(treeNode);//头结点是最后一个
        if(treeNode.left != null){
            stack1.push(treeNode.left);
        }
        if(treeNode.right != null){
            stack1.push(treeNode.right);
        }
    }

    while(!stack2.isEmpty()){
        System.out.print(stack2.pop().value + " ");
    }
    System.out.println();
}

 

最后修改:2019-10-08 16:05:02 © 著作权归作者所有
如果觉得我的文章对你有用,请随意赞赏
扫一扫支付

上一篇

发表评论

说点什么吧~

评论列表

还没有人评论哦~赶快抢占沙发吧~