二叉树的各种遍历方式
通过递归方式,可实现二叉树的层级遍历,先序,中序,后序等遍历方式。
package com.ykq;
import java.util.ArrayList;
import java.util.List;
/**
* @author: ykq
* @date: 2023/3/17 14:33
* @Description:
*/
public class ListNodeTest {
public static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) {
this.val = val;
}
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
public static void main(String[] args) {
TreeNode node1 = new TreeNode(1);
TreeNode node2 = new TreeNode(2);
TreeNode node3 = new TreeNode(3);
TreeNode node4 = new TreeNode(4);
TreeNode node5 = new TreeNode(5);
TreeNode node6 = new TreeNode(6);
TreeNode node7 = new TreeNode(7);
TreeNode node8 = new TreeNode(8);
TreeNode node9 = new TreeNode(9);
TreeNode node10 = new TreeNode(10);
node1.left = node2;
node1.right = node3;
node2.left = node4;
node2.right = node5;
node3.left = node6;
node3.right = node7;
node6.right = node8;
node7.left = node9;
node4.right = node10;
System.out.print("层序遍历:");
hierarchicalTraversal(node1);
System.out.println();
System.out.print("前序遍历:");
preOrderTraversal(node1);
System.out.println();
System.out.print("中序遍历:");
inOrderTraversal(node1);
System.out.println();
System.out.print("后序遍历:");
postOrderTraversal(node1);
System.out.println();
System.out.print("根右左遍历:");
rootRightLeft(node1);
System.out.println();
System.out.print("右根左遍历:");
rightRootLeft(node1);
System.out.println();
System.out.print("右左根遍历:");
rightLeftRoot(node1);
}
/**
* @Author ykq
* @Date 2023/3/17 14:56
* @Description 层级遍历
*/
public static void hierarchicalTraversal(TreeNode root) {
if (root == null) {
return;
}
List<TreeNode> nodeList = new ArrayList<>();
nodeList.add(root);
hierarchicalTraversal(nodeList);
}
/**
* @Author ykq
* @Date 2023/3/17 15:07
* @Description 递归层序遍历
*/
public static void hierarchicalTraversal(List<TreeNode> nodeList) {
List<TreeNode> treeNodeList = new ArrayList<>();
for (TreeNode treeNode : nodeList) {
System.out.print(treeNode.val + " ");
if (treeNode.left != null) {
treeNodeList.add(treeNode.left);
}
if (treeNode.right != null) {
treeNodeList.add(treeNode.right);
}
}
if (treeNodeList.size() > 0) {
hierarchicalTraversal(treeNodeList);
}
}
/**
* @Author ykq
* @Date 2023/3/17 14:38
* @Description 前序遍历->根左右
*/
public static void preOrderTraversal(TreeNode root) {
if (root == null) {
return;
}
System.out.print(root.val + " ");
preOrderTraversal(root.left);
preOrderTraversal(root.right);
}
/**
* @Author ykq
* @Date 2023/3/17 14:42
* @Description 中序遍历->左根右
*/
public static void inOrderTraversal(TreeNode root) {
if (root == null) {
return;
}
inOrderTraversal(root.left);
System.out.print(root.val + " ");
inOrderTraversal(root.right);
}
/**
* @Author ykq
* @Date 2023/3/17 14:44
* @Description 后序遍历->左右根
*/
public static void postOrderTraversal(TreeNode root) {
if (root == null) {
return;
}
postOrderTraversal(root.left);
postOrderTraversal(root.right);
System.out.print(root.val + " ");
}
/**
* @Author ykq
* @Date 2023/3/17 14:49
* @Description 根右左
*/
public static void rootRightLeft(TreeNode root) {
if (root == null) {
return;
}
System.out.print(root.val + " ");
rootRightLeft(root.right);
rootRightLeft(root.left);
}
/**
* @Author ykq
* @Date 2023/3/17 14:51
* @Description 右根左
*/
public static void rightRootLeft(TreeNode root) {
if (root == null) {
return;
}
rightRootLeft(root.right);
System.out.print(root.val + " ");
rightRootLeft(root.left);
}
/**
* @Author ykq
* @Date 2023/3/17 14:52
* @Description 右左根
*/
public static void rightLeftRoot(TreeNode root) {
if (root == null) {
return;
}
rightLeftRoot(root.right);
rightLeftRoot(root.left);
System.out.print(root.val + " ");
}
}