package 二叉树的中序遍历;import java.util.*;// 定义二叉树节点
class TreeNode {int val; // 节点值TreeNode left; // 左子节点TreeNode right; // 右子节点// 构造函数TreeNode(int x) {val = x;}
}public class DMain {// 构建二叉树（层序遍历方式）public static TreeNode buildTree(Integer[] nums) {// 如果输入数组为空或第一个节点为null，直接返回空树if (nums == null || nums.length == 0 || nums[0] == null) {return null;}// 创建根节点TreeNode root = new TreeNode(nums[0]);// 使用队列辅助构建二叉树Queue<TreeNode> queue = new LinkedList<>();queue.offer(root); // 将根节点加入队列int index = 1; // 从数组的第二个元素开始处理while (!queue.isEmpty() && index < nums.length) {// 从队列中取出当前节点TreeNode node = queue.poll();// 处理左子节点if (nums[index] != null) {node.left = new TreeNode(nums[index]); // 创建左子节点queue.offer(node.left); // 将左子节点加入队列}index++; // 移动到下一个元素// 处理右子节点if (index < nums.length && nums[index] != null) {node.right = new TreeNode(nums[index]); // 创建右子节点queue.offer(node.right); // 将右子节点加入队列}index++; // 移动到下一个元素}// 返回构建好的二叉树的根节点return root;}// 迭代的层序遍历public static List<List<Integer>> levelOrder(TreeNode root) {// 存储层序遍历的结果List<List<Integer>> result = new ArrayList<>();// 如果根节点为空，直接返回空结果if (root == null) {return result;}// 使用队列辅助层序遍历Queue<TreeNode> queue = new LinkedList<>();queue.offer(root); // 将根节点加入队列while (!queue.isEmpty()) {// 当前层的节点数量int levelSize = queue.size();// 存储当前层的节点值List<Integer> level = new ArrayList<>();// 遍历当前层的所有节点for (int i = 0; i < levelSize; i++) {TreeNode node = queue.poll(); // 从队列中取出当前节点level.add(node.val); // 将当前节点的值加入当前层的列表// 将当前节点的左子节点加入队列if (node.left != null) {queue.offer(node.left);}// 将当前节点的右子节点加入队列if (node.right != null) {queue.offer(node.right);}}// 将当前层的节点值列表加入结果列表result.add(level);}// 返回层序遍历的结果return result;}// 主函数public static void main(String[] args) {Scanner sc = new Scanner(System.in);System.out.println("请输入二叉树（用,分隔，null表示空节点）：");String s=sc.nextLine();String[] str=s.split(",");Integer[] nums=new Integer[str.length];for (int i = 0; i < str.length; i++) {if (str[i].equals("null")) {nums[i] = null;}else{nums[i] = Integer.parseInt(str[i]);}}// 构建二叉树TreeNode root = buildTree(nums);// 中序遍历二叉树List<Integer> integers = inorderTraversal(root);System.out.println("中序遍历结果：");for (Integer integer : integers) {System.out.print(integer + " ");}System.out.println();//层序遍历二叉树List<List<Integer>> result = levelOrder(root);// 输出层序遍历结果System.out.println("层序遍历结果：");for (List<Integer> level : result) {for (int val : level) {System.out.print(val + " ");}System.out.println();}}public static List<Integer> inorderTraversal(TreeNode root) {List<Integer> list = new ArrayList<>();inorder(root, list);return list;}public static void inorder(TreeNode root, List<Integer> list) {if (root == null) {return;}inorder(root.left, list);list.add(root.val);inorder(root.right, list);}}
结果：
