二叉树的四种遍历 以及代码实现,看这一篇就够了

共 5885字,需浏览 12分钟

 ·

2021-04-07 10:23

点击上方蓝色字体,选择“标星公众号”

优质文章,第一时间送达

76套java从入门到精通实战课程分享

★ 前言:
二叉树的遍历,是我们数据结构 重点中的重点 ,90% 的笔试题都是二叉树遍历的变形
但是呢,有很多小伙伴对它的遍历方式还是有些模糊
那么,接下来我就为大家详细介绍各种遍历方式的区别:


何为 遍历 : 

就是把二叉树中的每个结点,一个不落的都走一遍。。

我们先封装一个 二叉树 的对象类:

public class TreeNode {
    int v;
    TreeNode left; // 左子树
    TreeNode right; // 右子树

    public TreeNode(int v) {
        this.v = v;
    }

    @Override
    public String toString() {
        return String.format("%c",v);
    }
}


1、DFS(Depth First Search):深度优先遍历 – 栈

第一种视角看三种遍历:

(1)前序遍历:

遍历顺序:(递归)

把根结点放前面处理:


1、首先,处理 根结点

2、接着,完整地遍历根的 左子树(采用先序)

3、最后,完整地遍历根的 右子树(采用先序)

ce344a7010c273058b7f64c0ade9ecdb.webp

具体实现:根 { 左子树 } { 右子树 }


① 我们是从 根结点 开始,

即 :A{ } { }


② 由于我们是先遍历 左子树

所以, A { B{}{} } { }


A { B{ D{}{} }{} } { }


A { B{ D{}{G} }{} } { }


③ 最后遍历 右子树:


A { B{ D{}{G} }{} } { C{}{} }


A { B{ D{}{G} }{} } { C{E}{} }


A { B{ D{}{G} }{} } { C{E}{ F{}{} } }


A { B{ D{}{G} }{} } { C{E}{ F{H}{} } }


这样我们就得出了我们先序遍历出来的结果:

A B D G C E F H


① 代码实现:(递归)

// 前序遍历
    public static void preTraversal(TreeNode root) {
        // 前提:这颗树不是空树(根结点存在)
        if (root != null) {
            // 1、首先处理根结点
            System.out.printf("%c",root.v);
            // 2、按照前序的方式,递归处理该结点的左子树
            preTraversal(root.left);
            // 3、按照前序的方式,递归处理该结点的右子树
            preTraversal(root.right);
        } 
    }


② 代码实现:(非递归)

    public static void preOrder(TreeNode root) {
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode cur = root;
        while (!stack.isEmpty() || cur != null) {
            //遍历左子树
            while (cur != null) {
                System.out.println(cur.v);
                stack.push(cur);
                cur = cur.left;
            }
            //取出栈顶元素
            TreeNode top = stack.pop();
            //遍历右子树
            cur = top.right;
        }
    }

983e9a6540b027fe42a01691e6c69763.webp



(2)中序遍历:

遍历顺序:(递归)

1、先遍历整颗树的 左子树(采用中序)

2、中间再处理 根结点 (根放到中间处理)

3、再遍历整棵树的 右子树 (采用中序)

233dd4a11569ce25d7608217a837efda.webp


具体实现:{ 左子树 } 根 { 右子树 }

即:{ } A { }


我们先来遍历 左子树, 遍历的方式采用 中序遍历


{ {}B{} } A { }


{ { {}D{} }B{} } A { }


{ { {}D{G} }B{} } A { }


我们再来遍历 右子树,遍历的方式仍然采用 中序遍历


{ { {}D{G} }B{} } A { {}C{} }


{ { {}D{G} }B{} } A { {E}C{} }


{ { {}D{G} }B{} } A { {E}C{ {}F{} } }


{ { {}D{G} }B{} } A { {E}C{ {H}F{} } }


这样我们就得出了我们 中序遍历 出来的结果:

D G B A E C H F


① 代码实现:(递归)

// 中序遍历
    public static void inTraversal(TreeNode root) {
        if (root != null) {
            // 1、中序遍历左子树
            inTraversal(root.left);
            // 2、处理根
            System.out.printf("%c",root.v);
            // 3、中序遍历右子树
            inTraversal(root.right);
        }
    }


② 代码实现:(非递归)

public static void inOrder(TreeNode root) {
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode cur = root;
        while (!stack.isEmpty() || cur != null) {
            //遍历左子树
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            //取出栈顶元素
            TreeNode top = stack.pop();
            //回来的时候打印他
            System.out.println(top.v);
            //遍历右子树
            cur = top.right;
        }
    }


(3)后序遍历:

遍历顺序:(递归)

1、先遍历整颗树的 左子树(采用后序)

2、再遍历整棵树的 右子树 (采用后序)

3、最后再处理 根结点 (根放到最后处理)

199a16ae823dd93637782026c58ec50b.webp


具体实现:{ 左子树 } { 右子树 } 根

即:{ } { } A


我们先来遍历 左子树, 遍历的方式采用 后序遍历:


{ {}{}B } { }A


{ { {}{}D }{}B } { }A


{ { {}{G}D }{}B } { }A


我们再来遍历 右子树,遍历的方式仍然采用 后序遍历


{ { {}{G}D }{}B } { }A


{ { {}{G}D }{}B } { {}{}C }A


{ { {}{G}D }{}B } { {E}{}C }A


{ { {}{G}D }{}B } { {E}{ {}{}F }C }A


{ { {}{G}D }{}B } { {E}{ {H}F}{}C }A


这样我们就得出了我们 后序遍历 出来的结果:

G D B E H F C A


① 代码实现:(递归)

// 后序遍历
    public static void postTraversal(TreeNode root) {
        if (root != null) {
            // 1、后续遍历左子树
            postTraversal(root.left);
            // 2、后续遍历右子树
            postTraversal(root.right);
            // 3、处理根
            System.out.printf("%c",root.v);

        }
    }


② 代码实现:(非递归)

    public static void postOrder(TreeNode root) {
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode cur = root;
        TreeNode last = null;//记录上次遍历的结点
        while (!stack.isEmpty() || cur != null) {
            //遍历左子树
            while (cur != null) {
                //第一次经过 cur 这个结点
                stack.push(cur);
                cur = cur.left;
            }
            //取出栈顶元素但不删除
            TreeNode top = stack.peek();
            if(top.right == null) {
                //第二次经过 top 这个结点(因为右边为空,所以可以看作第三次)
                //从左子树中回来,但是右子树为空,可以看作从右子树回来
                stack.pop();
                last = top;
                System.out.println(top.v);
            } else if (top.right == last){
                //第三次经过 top
                //说明从右子树中回来的
                stack.pop();
                last = top;
                System.out.println(top.v);
            } else {
                //第二次经过 top
                //说明从左子树中回来的
                cur = top.right;
            }
        }
    }


第二种视角看三种遍历:


前序 / 中序 / 后序,都是沿着红色的虚线前进

003506b930b2d440950263e15eba922c.webp

根据每次结点 经过的次数 来进行判断是 什么 类型 的遍历:

  • 前序:A B D C E F

  • 中序:D B A E C F

  • 后序:D B E F C A

2、BFS(Broadcast First Search):广度优先遍历

层次遍历:- - (队列)

按照从上到下,从左到右依次将二叉树遍历一遍

716192c5466853ead5f64b9a0391c4bc.webp



步骤:准备一个队列

1、启动阶段 : 把根节点放入队列

deb3c8d4602b596e6904cfad3b4b6b49.webp


2、开启循环,直到队列为空(isEmpty)

(1)从队列中取出队首结点

(2)层序遍历经过该结点(打印)

(3)把该结点的 左 / 右 孩子放入队列中(如果存在)

78c63dc7ca3abcd856cd3992664d7396.webp


重复上述循环,即可层序遍历完二叉树


最终打印的结果是:A B C D E F G H I


代码实现:

//层序遍历
public class TreeLevelOrder {
    public static void levelOrderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }
        //队列的元素的类型是树的结点
        Queue<TreeNode> queue = new LinkedList<>();
        //1、把根节点放入队列
        queue.add(root);
        //2、开启循环
        while (!queue.isEmpty()) {
            //(1)从队列中取出队首元素
            //node 就是层序遍历时经过的结点
            TreeNode node = queue.remove();
            //(2)打印遍历结点的值
            System.out.println(node.v);
            //(3)把该结点的左右子树放入队列中
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
    }
}

用途:(判断完全二叉树)

————————————————

版权声明:本文为CSDN博主「小乔不掉发」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。

原文链接:

https://blog.csdn.net/qq_45658339/article/details/109608414





锋哥最新SpringCloud分布式电商秒杀课程发布

👇👇👇

👆长按上方微信二维码 2 秒





感谢点赞支持下哈 f5a908479e59eca0c88caafb9b294170.webp

浏览 35
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报