java数据结构和算法——二叉树的前序遍历、中序遍历和后序遍历

一、二叉树的前序遍历、中序遍历和后序遍历概念

• 前序遍历: 先输出父节点，再遍历左子树和右子树
• 中序遍历: 先遍历左子树， 再输出父节点，再遍历右子树
• 后序遍历: 先遍历左子树，再遍历右子树， 最后输出父节点
• 小结: 看输出父节点的顺序，就确定是前序遍历，中序遍历还是后序遍历

二、二叉树的前序遍历、中序遍历和后序遍历的思路图解

三、二叉树的前序遍历、中序遍历和后序遍历的代码示例

1、代码

package com.rf.springboot01.dataStructure.tree; /**
 * @description: 二叉树的前序遍历、中序遍历和后序遍历示例
 * @author: xiaozhi
 * @create: 2020-08-27 22:03
 */ public class BinaryTreeDemo { public static void main(String[] args) { //创建二叉树 BinaryTree binaryTree = new BinaryTree(); //创建需要的结点 EmpNode root = new EmpNode(1,"张三"); EmpNode node2 = new EmpNode(2, "李四"); EmpNode node3 = new EmpNode(3, "王五"); EmpNode node4 = new EmpNode(4, "小志"); EmpNode node5 = new EmpNode(5, "Tom"); //手动创建该二叉树 binaryTree.setRoot(root);//创建根节点 root.setLeft(node2);//创建根节点左边子节点 root.setRight(node3);//创建根节点右边子节点 node3.setRight(node4);//创建根节点右边子节点的右边子节点 node3.setLeft(node5);//创建根节点右边子节点的左边子节点 //测试 System.out.println("前序遍历==============="); binaryTree.preOrder();//输出的no的顺序为1,2,3,5,4 System.out.println("中序遍历----------------"); binaryTree.infixOrder();//输出的no的顺序为2,1,5,3,4 System.out.println("后序遍历================"); binaryTree.suffixOrder();//输出的no的顺序为2,5,4,3,1 } } /** 
* @Description: 创建BinaryTree 二叉树
* @Param:  
* @Author: xz  
* @return: 
* @Date: 2020/8/27 22:03
*/ class BinaryTree{ private EmpNode root; public void setRoot(EmpNode root) { this.root = root; } //前序遍历方法 public void preOrder(){ if(root !=null){ this.root.preOrder(); }else{ System.out.println("二叉树为空，无法遍历"); } } //中序遍历方法 public void infixOrder(){ if(root != null){ this.root.infixOrder(); }else { System.out.println("二叉树为空，无法遍历"); } } //后序遍历方法 public void suffixOrder(){ if(root != null){ this.root.suffixOrder(); }else{ System.out.println("二叉树为空，无法遍历"); } } } /** 
* @Description: 先创建EmpNode结点类
* @Author: xz
* @Date: 2020/8/27 22:03
*/ class EmpNode{ private int no; private String name; private EmpNode left;//左节点，默认为null private EmpNode right;//右节点，默认为null //构造方法 public EmpNode(int no, String name) { this.no = no; this.name = name; } //getter、setter方法 public int getNo() { return no; } public void setNo(int no) { this.no = no; } public String getName() { return name; } public void setName(String name) { this.name = name; } public EmpNode getLeft() { return left; } public void setLeft(EmpNode left) { this.left = left; } public EmpNode getRight() { return right; } public void setRight(EmpNode right) { this.right = right; } //toString方法 @Override public String toString() { return "EmpNode{" + "no=" + no + ", name='" + name + '\'' + '}'; } //前序遍历方法 public void preOrder(){ //先输出父节点 System.out.println(this); //递归向左子树前序遍历 if(this.left != null){ this.left.preOrder(); } //递归向右子树前序遍历 if(this.right != null){ this.right.preOrder(); } } //中序遍历方法 public void infixOrder(){ //递归向左子树中序遍历 if(this.left !=null){ this.left.infixOrder(); } //输出父结点 System.out.println(this); //递归向右子树中序遍历 if(this.right !=null){ this.right.infixOrder(); } } //后序遍历方法 public void suffixOrder(){ //递归向左子树后序遍历 if(this.left != null){ this.left.suffixOrder(); } //递归向右子树后序遍历 if(this.right !=null){ this.right.suffixOrder(); } //输出父节点 System.out.println(this); } } 

2、运行main函数，输出结果如下：