java如何遍历树

遍历树的方法

在Java中，树的遍历通常分为深度优先遍历（DFS）和广度优先遍历（BFS）。以下是常见的几种遍历方式及其实现方法。

深度优先遍历（DFS）

深度优先遍历分为前序遍历、中序遍历和后序遍历三种方式。

前序遍历（根-左-右）

前序遍历首先访问根节点，然后递归地遍历左子树，最后遍历右子树。

public void preOrder(TreeNode root) {
    if (root == null) return;
    System.out.println(root.val); // 访问根节点
    preOrder(root.left);          // 遍历左子树
    preOrder(root.right);         // 遍历右子树
}

中序遍历（左-根-右）

中序遍历先递归地遍历左子树，然后访问根节点，最后遍历右子树。

public void inOrder(TreeNode root) {
    if (root == null) return;
    inOrder(root.left);           // 遍历左子树
    System.out.println(root.val);  // 访问根节点
    inOrder(root.right);          // 遍历右子树
}

后序遍历（左-右-根）

后序遍历先递归地遍历左子树，然后遍历右子树，最后访问根节点。

public void postOrder(TreeNode root) {
    if (root == null) return;
    postOrder(root.left);         // 遍历左子树
    postOrder(root.right);        // 遍历右子树
    System.out.println(root.val); // 访问根节点
}

广度优先遍历（BFS）

广度优先遍历使用队列实现，按层次遍历树的节点。

public void levelOrder(TreeNode root) {
    if (root == null) return;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        System.out.println(node.val);
        if (node.left != null) queue.offer(node.left);
        if (node.right != null) queue.offer(node.right);
    }
}

迭代实现

递归方法虽然简洁，但在某些情况下可能因栈溢出而失效。以下是迭代实现的前序遍历：

public void preOrderIterative(TreeNode root) {
    if (root == null) return;
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        System.out.println(node.val);
        if (node.right != null) stack.push(node.right);
        if (node.left != null) stack.push(node.left);
    }
}

树的节点定义

以下是树的节点定义示例：

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) {
        this.val = val;
    }
}

总结

树的遍历可以通过递归或迭代实现。深度优先遍历包括前序、中序和后序三种方式，广度优先遍历通常使用队列实现。根据具体需求选择合适的遍历方式。