二叉树的遍历的步骤（我是怎么调试出来二叉树的遍历）
二叉树的遍历的步骤（我是怎么调试出来二叉树的遍历）接下来我们这几种遍历算法，一个一个的认识。package tree; /** * @Auther: truedei * @Date: 2020 /20-6-7 17:39 * @Description: */ public class TestTrueDeiTree { public static void main(String[] args) { TreeNode t1 = new TreeNode(3); TreeNode t2 = new TreeNode(9); TreeNode t3 = new TreeNode(20); TreeNode t4 = new TreeNode(15); TreeNode t5 = new TreeNode(7); t1.left
推荐学习- 牛掰！“基础-中级-高级”Java程序员面试集结，看完献出我的膝盖
- 数据结构与算法，程序员必过的坎？不掌握一定挤不进BATJ的神技？
我是怎么调试出来二叉树的遍历(超精彩配图)，从此遍历不再愁了！
二叉树遍历（Traversing binary tree）是指从根节点触发，按照某种次序依次访问二叉树中所有的结点，使得每个结点被依次访问且仅仅被访问一次。
二叉树的遍历有四种方式，分别为：先序遍历、中序遍历、后序遍历、层次遍历。
一、准备工作
在做实验之前先准备一个二叉树的结构，这样方便进行实验。
（一）定义二叉树的数据结构
package tree;
/**
* @Auther: truedei
* @Date: 2020 /20-6-5 11:59
* @Description:
*/
public class TreeNode {
int val;//每个节点存放的数据
TreeNode left;//左节点
TreeNode right;//右节点
TreeNode(int x) { val = x; }
}（二）手工构造一个二叉树
至于为什么是手工，因为不想把你搞混了，这篇文章主要是遍历，对于构造二叉树的方法可以自行研究一下。
package tree;
/**
* @Auther: truedei
* @Date: 2020 /20-6-7 17:39
* @Description:
*/
public class TestTrueDeiTree {
public static void main(String[] args) {
TreeNode t1 = new TreeNode(3);
TreeNode t2 = new TreeNode(9);
TreeNode t3 = new TreeNode(20);
TreeNode t4 = new TreeNode(15);
TreeNode t5 = new TreeNode(7);
t1.left=t2;
t1.right=t3;
t3.left=t4;
t3.right=t5;
}
}
构造之后的二叉树的结构图：
接下来我们这几种遍历算法，一个一个的认识。
四种遍历的概念：
（1）先序遍历：先访问根节点，再访问左子树，最后访问右子树；可以说为”根-左-右“。
（2）后序遍历：先左子树，再右子树，最后根节点；可以说为”左-右-根“。
（3）中序遍历：先左子树，再根节点，最后右子树；可以说为”左-根-右“。
（4）层序遍历：每一层从左到右访问每一个节点。
（一）前序遍历1、前序遍历概念
前序遍历：先访问根节点，再访问左子树，最后访问右子树；可以说为”根-左-右“。
按照：先访问根节点，再访问左子树，最后访问右子树的顺序如果用图来描述一下的话，是这样子的;
2、图解前序遍历
1、首先我们有一颗如下所示的二叉树，这就是我们的初始值：
方便理解，为此我做了一个GIF的图：
遍历的顺序：
通过这个规则我们得到前序遍历结果：3、9、20、15、7
3、代码实现前序遍历（1）递归实现/** 根-> 左-> 右
* 前序遍历
* @param root
*/
public static void PreOrder(TreeNode root) {
//结束的条件
if (root==null)
return;
System.out.print(root.val " ");
//使用递归进行遍历左孩子
PreOrder(root.left);
//递归遍历右孩子
PreOrder(root.right);
}
结果：
3 9 20 15 7
（2）非递归实现
1.首先申请一个新的栈，记为stack；
2.声明一个结点treeNode，让其指向root结点；
3.如果treeNode的不为空，将treeNode的值打印，并将treeNode入栈，然后让treeNode指向4.treeNode的左结点，
5.重复步骤3，直到treenode为空；
6.然后出栈，让treeNode指向treeNode的右孩子
7.重复步骤3，直到stack为空.
/**根-->左-->右
* 非递归前序遍历
*
*
* 1，首先申请一个新的栈，记为stack；
* 2，声明一个结点treeNode，让其指向node结点；
* 3，如果treeNode的不为空，将treeNode的值打印，并将treeNode入栈，然后让treeNode指向treeNode的左结点，
* 4，重复步骤3，直到treenode为空；
* 5，然后出栈，让treeNode指向treeNode的右孩子
* 6，重复步骤3，直到stack为空.
*
* @param root
*/
public static void preOrderStack(TreeNode root){
//利用栈的特性（先进的后出），用于存储节点数据，一层一层的往上冒
Stack<TreeNode> stack = new Stack<>();
//相当于临时的变量，记录当前的所在节点
TreeNode treeNode = root;
//两个条件满足一个即可继续执行，退出的条件是当前的节点为null和栈也空了，说明没有数据了
//栈空了说明冒到了最上一层，最上一层也遍历成了，就空了
while (treeNode != null || !stack.isEmpty()){
//迭代访问节点的左孩子，并入栈
//一直遍历最左边的节点
while (treeNode != null){
//先根
System.out.print(treeNode.val " ");
stack.push(treeNode);
//遍历完根，然后还是遍历最左边的。。如果还有的话，还是遍历最左边的
treeNode = treeNode.left;
}
//如果节点没有左孩子，则弹出栈顶节点，访问节点右孩子
if(!stack.isEmpty()){
treeNode = stack.pop();
treeNode = treeNode.right;
}
}
}4、使用IDEA调试java代码进一步查看执行过程
现在我的代码是这样子的：
package tree;
/**
* @Auther: truedei
* @Date: 2020 /20-6-7 17:39
* @Description:
*/
public class TestTrueDeiTree {
public static void main(String[] args) {
TreeNode t1 = new TreeNode(3);
TreeNode t2 = new TreeNode(9);
TreeNode t3 = new TreeNode(20);
TreeNode t4 = new TreeNode(15);
TreeNode t5 = new TreeNode(7);
t1.left=t2;
t1.right=t3;
t3.left=t4;
t3.right=t5;
PreOrder(t1);
}
/**
* 前序遍历
* @param root
*/
public static void PreOrder(TreeNode root) { //先序遍历
if (root==null)
return;
System.out.print(root.val " ");
//使用递归进行遍历左孩子
PreOrder(root.left);
//递归遍历右孩子
PreOrder(root.right);
}
}
//树结构
class TreeNode {
int val;//每个节点存放的数据
TreeNode left;//左节点
TreeNode right;//右节点
TreeNode(int x) { val = x; }
}
为了方便调试，我们先在下面这几个地方打上断点：
第1次：
因为是初次遍历，所以root肯定不为null，所以执行打印的这条语句；
打印了3，就是我们想要的结果
继续调试，更详细的解析，就看图吧：
继续下一步
再次点击下一步之后，传入的是null，所以就不会再继续执行剩下的代码了
继续点击下一步：
至于为什么会调用执行了遍历右孩子的代码。原因有:
1、程序的代码都是顺序执行的
2、和JVM相关，如果你学过JVM，则这个地方为什么会执行就会很清晰了
3、遍历3的左孩子的结束了，自然而然的销毁了之前的代码，然后就执行到了
继续点下一步，会又一次的进入，并且把20的left节点传入
这个应该就不用多解释了，上面解释的很清楚了
继续下一步会打印出当前节点的值，并调到下一个Debug处
继续下一步会为null，所以退出当前的方法
发现还是为null
再次点击下一步，就会结束掉这次的了
再次点击下一步，会销毁掉刚才运行的方法，回到上一次进入时的状态，这次就该轮到right了
再点一次，main方法也会执行结束，并将其销毁，从而得到了我们想要的结果：
中序遍历：先左子树，再根节点，最后右子树；可以说为”左-根-右“。
按照：先左子树，再根节点，最后右子树的顺序如果用图来描述一下的话，是这样子的;
2、图解中序遍历1、首先我们有一颗如下所示的二叉树，这就是我们的初始值：
执行顺序：
因为是递归，代码也很简单，修改一下位置就好了。
/** 左-> 根-> 右
* 中序遍历
* @param root
*/
public static void MidOrder(TreeNode root) { //先序遍历
if (root==null)
return;
//使用递归每次都先进行遍历左孩子
MidOrder(root.left);
System.out.print(root.val " ");
//递归遍历右孩子
MidOrder(root.right);
}
（2）非递归实现
1.申请一个新栈，记为stack，申请一个变量treeNode，初始时令treeNode为头节点；
2.先把treeNode节点压入栈中，对以treeNode节点为头的整棵子树来说，依次把整棵树的左子树压入栈中，即不断令treeNode=treeNode.leftChild，然后重复步骤2；
3.不断重复步骤2，直到发现treeNode为空，此时从stack中弹出一个节点记为treeNode，打印node的值，并让treeNode= treeNode.right，然后继续重复步骤2；
当stack为空并且treeNode为空时结束
/** 左-->根-->右
* 非递归实现中序遍历
* @param root
*/
public static void MidOrderStack(TreeNode root){
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode treeNode = root;
while(treeNode!=null || !stack.isEmpty()){
while(treeNode != null){
stack.push(treeNode);
treeNode = treeNode.left;
}
if(!stack.isEmpty()){
treeNode = stack.pop();
System.out.print(treeNode.val " ");
treeNode = treeNode.right;
}
}
}4、调试略
整个过程和前序遍历都是差不多的，可以自己试着调试一下，这里就不在啰嗦了。
(三）后序遍历1、后序遍历概念后序遍历：先左子树，再右子树，最后根节点；可以说为”左-右-根“。
按照：先左子树，再右子树，最后根节点的顺序如果用图来描述一下的话，是这样子的;
2、图解后序遍历1、首先我们有一颗如下所示的二叉树，这就是我们的初始值：
遍历到顺序和结果：
动态过程图：
/** 左-->右-->根
* 后序遍历
* @param root
*/
public static void BackOrder(TreeNode root) { //先序遍历
if (root==null)
return;
//使用递归每次都先进行遍历左孩子
BackOrder(root.left);
//递归遍历右孩子
BackOrder(root.right);
//根
System.out.print(root.val " ");
}
（2）非递归实现
/** 左-->右-->根
* 非递归实现后序遍历
* @param root
*/
public static void BackOrderStack(TreeNode root){
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode treeNode = root;
TreeNode lastVisit = null; //标记每次遍历最后一次访问的节点
//节点不为空，结点入栈，并且指向下一个左孩子
while(treeNode!=null || !stack.isEmpty()){
while(treeNode!=null){
stack.push(treeNode);
treeNode = treeNode.left;
}
//栈不为空
if(!stack.isEmpty()){
//出栈
treeNode = stack.pop();
/**
* 这块就是判断treeNode是否有右孩子，
* 如果没有，则输出treeNode.val，让lastVisit指向treeNode，并让treeNode为空
* 如果有右孩子，将当前节点继续入栈，treeNode指向它的右孩子 继续重复循环
*/
if(treeNode.right == null || treeNode.right == lastVisit) {
System.out.print(treeNode.val " ");
lastVisit = treeNode;
treeNode = null;
}else{
stack.push(treeNode);
treeNode = treeNode.right;
}
}
}
}4、调试略
整个过程和前序遍历都是差不多的，可以自己试着调试一下，这里就不在啰嗦了。
（四）层次遍历
1.首先申请一个新的队列，记为queue；
2.将根结点root压入queue中；
3.每次从queue中出队，并赋值给root，作为下一次的根，然后打印root.val的值，如果root左孩子4.不为空，则将左孩子入队；如果root的右孩子不为空，则将右孩子入队；
重复步骤3，直到queue为空。
/**
* 层次遍历
* @param root
*/
public static void levelOrder(TreeNode root){
LinkedList<TreeNode> queue = new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()){
root = queue.pop();
System.out.print(root.val " ");
if(root.left!=null)
queue.add(root.left);
if(root.right!=null)
queue.add(root.right);
}
}
结果：
3 9 20 15 7 三、总结
遍历二叉树可以使用递归的方式和非递归的方式来遍历。
四种遍历：
（1）先序遍历：先访问根节点，再访问左子树，最后访问右子树；可以说为”根-左-右“。
（2）后序遍历：先左子树，再右子树，最后根节点；可以说为”左-右-根“。
（3）中序遍历：先左子树，再根节点，最后右子树；可以说为”左-根-右“。
（4）层序遍历：每一层从左到右访问每一个节点。
所有代码：
package tree;
import java.util.LinkedList;
import java.util.Stack;
/**
* @Auther: truedei
* @Date: 2020 /20-6-7 17:39
* @Description: //preorder，midorder，backorder
*/
public class TestTrueDeiTree {
public static void main(String[] args) {
TreeNode t1 = new TreeNode(3);
TreeNode t2 = new TreeNode(9);
TreeNode t3 = new TreeNode(20);
TreeNode t4 = new TreeNode(15);
TreeNode t5 = new TreeNode(7);
t1.left=t2;
t1.right=t3;
t3.left=t4;
t3.right=t5;
System.out.println("递归前序遍历：");
PreOrder(t1);
System.out.println();
System.out.println("递归中序遍历：");
MidOrder(t1);
System.out.println();
System.out.println("递归后序遍历：");
BackOrder(t1);
System.out.println();
System.out.println("非递归前序遍历：");
preOrderStack(t1);
System.out.println();
System.out.println("非递归中序遍历：");
MidOrderStack(t1);
System.out.println();
System.out.println("非递归后序遍历：");
BackOrderStack(t1);
System.out.println();
System.out.println("层次遍历：");
levelOrder(t1);
}
/**根-->左-->右
* 递归前序遍历
* @param root
*/
public static void PreOrder(TreeNode root) {
if (root==null)
return;
System.out.print(root.val " ");
//使用递归进行遍历左孩子
PreOrder(root.left);
//递归遍历右孩子
PreOrder(root.right);
}
/**根-->左-->右
* 非递归前序遍历
*
*
* 1，首先申请一个新的栈，记为stack；
* 2，声明一个结点treeNode，让其指向node结点；
* 3，如果treeNode的不为空，将treeNode的值打印，并将treeNode入栈，然后让treeNode指向treeNode的右结点，
* 4，重复步骤3，直到treenode为空；
* 5，然后出栈，让treeNode指向treeNode的右孩子
* 6，重复步骤3，直到stack为空.
*
* @param root
*/
public static void preOrderStack(TreeNode root){
//利用栈的特性（先进的后出），用于存储节点数据，一层一层的往上冒
Stack<TreeNode> stack = new Stack<>();
//相当于临时的变量，记录当前的所在节点
TreeNode treeNode = root;
//两个条件满足一个即可继续执行，退出的条件是当前的节点为null和栈也空了，说明没有数据了
//栈空了说明冒到了最上一层，最上一层也遍历成了，就空了
while (treeNode != null || !stack.isEmpty()){
//迭代访问节点的左孩子，并入栈
//一直遍历最左边的节点
while (treeNode != null){
//先根
System.out.print(treeNode.val " ");
stack.push(treeNode);
//遍历完根，然后还是遍历最左边的。。如果还有的话，还是遍历最左边的
treeNode = treeNode.left;
}
//如果节点没有左孩子，则弹出栈顶节点，访问节点右孩子
if(!stack.isEmpty()){
treeNode = stack.pop();
treeNode = treeNode.right;
}
}
}
/** 左-->根-->右
* 中序遍历
* @param root
*/
public static void MidOrder(TreeNode root) { //先序遍历
if (root==null)
return;
//使用递归每次都先进行遍历左孩子
MidOrder(root.left);
System.out.print(root.val " ");
//递归遍历右孩子
MidOrder(root.right);
}
/** 左-->根-->右
* 中序遍历
*
*1. 申请一个新栈，记为stack，申请一个变量treeNode，初始时令treeNode为头节点；
*2. 先把treeNode节点压入栈中，对以treeNode节点为头的整棵子树来说，依次把整棵树的左子树压入栈中，即不断令treeNode=treeNode.leftChild，然后重复步骤2；
*3. 不断重复步骤2，直到发现treeNode为空，此时从stack中弹出一个节点记为treeNode，打印node的值，并让treeNode= treeNode.right，然后继续重复步骤2；
*4. 当stack为空并且treeNode为空时结束。
* @param root
*/
public static void MidOrderStack(TreeNode root){
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode treeNode = root;
while(treeNode!=null || !stack.isEmpty()){
while(treeNode != null){
stack.push(treeNode);
treeNode = treeNode.left;
}
if(!stack.isEmpty()){
treeNode = stack.pop();
System.out.print(treeNode.val " ");
treeNode = treeNode.right;
}
}
}
/** 左-->右-->根
* 后序遍历
* @param root
*/
public static void BackOrder(TreeNode root) { //先序遍历
if (root==null)
return;
//使用递归每次都先进行遍历左孩子
BackOrder(root.left);
//递归遍历右孩子
BackOrder(root.right);
//根
System.out.print(root.val " ");
}
/** 左-->右-->根
* 非递归实现后序遍历
* @param root
*/
public static void BackOrderStack(TreeNode root){
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode treeNode = root;
TreeNode lastVisit = null; //标记每次遍历最后一次访问的节点
//节点不为空，结点入栈，并且指向下一个左孩子
while(treeNode!=null || !stack.isEmpty()){
while(treeNode!=null){
stack.push(treeNode);
treeNode = treeNode.left;
}
//栈不为空
if(!stack.isEmpty()){
//出栈
treeNode = stack.pop();
/**
* 这块就是判断treeNode是否有右孩子，
* 如果没有，则输出treeNode.val，让lastVisit指向treeNode，并让treeNode为空
* 如果有右孩子，将当前节点继续入栈，treeNode指向它的右孩子 继续重复循环
*/
if(treeNode.right == null || treeNode.right == lastVisit) {
System.out.print(treeNode.val " ");
lastVisit = treeNode;
treeNode = null;
}else{
stack.push(treeNode);
treeNode = treeNode.right;
}
}
}
}
/**
* 层次遍历
* @param root
*/
public static void levelOrder(TreeNode root){
LinkedList<TreeNode> queue = new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()){
root = queue.pop();
System.out.print(root.val " ");
if(root.left!=null)
queue.add(root.left);
if(root.right!=null)
queue.add(root.right);
}
}
}
class TreeNode {
int val;//每个节点存放的数据
TreeNode left;//左节点
TreeNode right;//右节点
TreeNode(int x) { val = x; }
}
作者：TrueDei
原文链接：https://blog.csdn.net/qq_17623363/article/details/106612418
