Java常见算法（四）【二叉树遍历】

Java常见算法（四）【二叉树遍历】

文章目录

• 二叉树遍历
• • 1、前序遍历-递归
  • 2、中序遍历-递归
  • 3、后序遍历-递归
  • 前、中、后续遍历实验源码

二叉树遍历

https://www.bilibili.com/video/BV1Jv411A7Ty?p=22

1、前序遍历-递归

https://www.bilibili.com/video/BV1Jv411A7Ty?p=23

前序、中序、后续遍历其实就是一直打印栈顶，但是打印的时机有所不同；

前序遍历是第一次成为栈顶就打印。

 //1、前序-递归
    public static void preorder(TreeNode root){
        if(root==null){
            return;
        }
        System.out.println(root.val);//(第一次成为栈顶才打印)
        preorder(root.left);
        preorder(root.right);
    }

结果：

1
2
4
5
6
7
3

2、中序遍历-递归

https://www.bilibili.com/video/BV1Jv411A7Ty?p=24

前序、中序、后续遍历其实就是一直打印栈顶，但是打印的时机有所不同；

中序遍历是第二次成为栈顶才打印。

 //1、中序-递归(第二次成为栈顶才打印)
    public static void preorder1(TreeNode root){
        if(root==null){
            return;
        }
        
        preorder1(root.left);
        System.out.println(root.val);//(第二次成为栈顶时进行打印)
        preorder1(root.right);
    }

结果：

4
2
6
5
7
1
3

3、后序遍历-递归

https://www.bilibili.com/video/BV1Jv411A7Ty?p=25

前序、中序、后续遍历其实就是一直打印栈顶，但是打印的时机有所不同；

后序遍历是第三次成为栈顶才打印。

 //1、后序-递归(第三次成为栈顶才打印)
    public static void preorder2(TreeNode root){
        if(root==null){
            return;
        }
        preorder2(root.left);
        preorder2(root.right);
        System.out.println(root.val);//(第三次成为栈顶时进行打印)
    }

结果：

2
4
5
6
7
3
1

前、中、后续遍历实验源码

package com.example.rabbitmq;

import org.junit.jupiter.api.Test;
import org.springframework.boot.test.context.SpringBootTest;

import java.util.linkedList;
import java.util.Queue;

@SpringBootTest

class SuanfaApplicationTests17 {

    //定义一个二叉树
    static class TreeNode{
        public int val;
        public TreeNode left;
        public TreeNode right;
        public int deep;//深度
        public TreeNode(){}
        public TreeNode(int val){this.val=val;}
        public TreeNode(int val,TreeNode left,TreeNode right){
            this.val=val;
            this.left=left;
            this.right=right;
        }
    }

    //1、前序-递归
    public static void preorder(TreeNode root){
        if(root==null){
            return;
        }
        System.out.println(root.val);//(第一次成为栈顶才打印)
        preorder(root.left);
        preorder(root.right);
    }

    //2、中序-递归
    public static void preorder1(TreeNode root){
        if(root==null){
            return;
        }
        preorder1(root.left);
        System.out.println(root.val);//(第二次成为栈顶时进行打印)
        preorder1(root.right);
    }

    //3、后序-递归
    public static void preorder2(TreeNode root){
        if(root==null){
            return;
        }
        preorder(root.left);
        preorder(root.right);
        System.out.println(root.val);//(第三次成为栈顶时进行打印)
    }

    @Test
    public void sf0(){
        //构造一个二叉树
        TreeNode node7=new TreeNode(7,null,null);
        TreeNode node6=new TreeNode(6,null,null);
        TreeNode node5=new TreeNode(5,node6,node7);
        TreeNode node4=new TreeNode(4,null,null);
        TreeNode node3=new TreeNode(3,null,null);
        TreeNode node2=new TreeNode(2,node4,node5);
        TreeNode node1=new TreeNode(1,node2,node3);

        System.out.println("-------前序------");
        preorder(node1);
        System.out.println("-------中序------");
        preorder1(node1);
        System.out.println("-------后序------");
        preorder2(node1);
    }

}

结果：

-------前序------
1
2
4
5
6
7
3
-------中序------
4
2
6
5
7
1
3
-------后序------
2
4
5
6
7
3
1