二叉树的四种遍历 以及代码实现,看这一篇就够了
共 5885字,需浏览 12分钟
·
2021-04-07 10:23
点击上方蓝色字体,选择“标星公众号”
优质文章,第一时间送达
★ 前言:
二叉树的遍历,是我们数据结构 重点中的重点 ,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、最后,完整地遍历根的 右子树(采用先序)
具体实现:根 { 左子树 } { 右子树 }
① 我们是从 根结点 开始,
即 :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;
}
}
(2)中序遍历:
遍历顺序:(递归)
1、先遍历整颗树的 左子树(采用中序)
2、中间再处理 根结点 (根放到中间处理)
3、再遍历整棵树的 右子树 (采用中序)
具体实现:{ 左子树 } 根 { 右子树 }
即:{ } 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、最后再处理 根结点 (根放到最后处理)
具体实现:{ 左子树 } { 右子树 } 根
即:{ } { } 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;
}
}
}
第二种视角看三种遍历:
前序 / 中序 / 后序,都是沿着红色的虚线前进
根据每次结点 经过的次数 来进行判断是 什么 类型 的遍历:
前序:A B D C E F
中序:D B A E C F
后序:D B E F C A
2、BFS(Broadcast First Search):广度优先遍历
层次遍历:- - (队列)
按照从上到下,从左到右依次将二叉树遍历一遍
步骤:准备一个队列
1、启动阶段 : 把根节点放入队列
2、开启循环,直到队列为空(isEmpty)
(1)从队列中取出队首结点
(2)层序遍历经过该结点(打印)
(3)把该结点的 左 / 右 孩子放入队列中(如果存在)
重复上述循环,即可层序遍历完二叉树
最终打印的结果是: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 秒
感谢点赞支持下哈