Java 中二叉树的中序遍历算法实现

本文将介绍使用 Java 语言实现二叉树的中序遍历算法。

代码示例:

import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        Map<Integer, TreeNode> tree = new HashMap<>();

        for (int i = 1; i <= n; i++) {
            int num = scanner.nextInt();
            int ls = scanner.nextInt();
            int rs = scanner.nextInt();

            TreeNode node = tree.getOrDefault(num, new TreeNode(num));
            if (ls != -1) {
                node.left = new TreeNode(ls);
            }
            if (rs != -1) {
                node.right = new TreeNode(rs);
            }
            tree.put(num, node);
        }

        List<Integer> inorderTraversal = inorderTraversal(tree.get(1));
        
        for (int i = 0; i < inorderTraversal.size(); i++) {
            if (i > 0) {
                System.out.print(' ');
            }
            System.out.print(inorderTraversal.get(i));
        }
    }
    
    private static List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;
        
        while (curr != null || !stack.isEmpty()) {
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }
            
            curr = stack.pop();
            result.add(curr.val);
            curr = curr.right;
        }
        
        return result;
    }
}

算法原理:

中序遍历是指按照左子树 -> 根节点 -> 右子树的顺序访问二叉树的节点。代码使用栈来实现中序遍历，具体步骤如下:

初始化一个空栈，并将根节点压入栈中。
当栈不为空或当前节点不为空时，循环执行以下操作:
- 若当前节点不为空，则将其压入栈中，并将当前节点指向其左子节点。
- 若当前节点为空，则弹出栈顶节点，将其值添加到结果列表中，并将当前节点指向其右子节点。
循环结束后，结果列表即为中序遍历的结果。

总结:

本文介绍了使用 Java 语言实现二叉树的中序遍历算法，并给出了代码示例。该算法使用栈来实现遍历，简单易懂，并且可以方便地扩展到其他遍历方式。