java如何遍历树

遍历树的方法

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

深度优先遍历（DFS）

深度优先遍历包括前序遍历、中序遍历和后序遍历。以二叉树为例，节点定义如下：

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

前序遍历（根-左-右）

递归实现：

void preOrderTraversal(TreeNode root) {
    if (root == null) return;
    System.out.println(root.val);
    preOrderTraversal(root.left);
    preOrderTraversal(root.right);
}

迭代实现（使用栈）：

void preOrderTraversal(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);
    }
}

中序遍历（左-根-右）

递归实现：

void inOrderTraversal(TreeNode root) {
    if (root == null) return;
    inOrderTraversal(root.left);
    System.out.println(root.val);
    inOrderTraversal(root.right);
}

迭代实现：

void inOrderTraversal(TreeNode root) {
    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();
        System.out.println(curr.val);
        curr = curr.right;
    }
}

后序遍历（左-右-根）

递归实现：

void postOrderTraversal(TreeNode root) {
    if (root == null) return;
    postOrderTraversal(root.left);
    postOrderTraversal(root.right);
    System.out.println(root.val);
}

迭代实现：

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

广度优先遍历（BFS）

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

void levelOrderTraversal(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);
    }
}

通用树遍历

对于多叉树（每个节点可能有多个子节点），可以使用类似的方法。节点定义如下：

class TreeNode {
    int val;
    List<TreeNode> children;
    TreeNode(int x) { val = x; children = new ArrayList<>(); }
}

前序遍历

递归实现：

void preOrderTraversal(TreeNode root) {
    if (root == null) return;
    System.out.println(root.val);
    for (TreeNode child : root.children) {
        preOrderTraversal(child);
    }
}

后序遍历

递归实现：

void postOrderTraversal(TreeNode root) {
    if (root == null) return;
    for (TreeNode child : root.children) {
        postOrderTraversal(child);
    }
    System.out.println(root.val);
}

广度优先遍历

void levelOrderTraversal(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);
        for (TreeNode child : node.children) {
            queue.offer(child);
        }
    }
}

以上方法覆盖了常见的树遍历需求，可以根据具体场景选择合适的遍历方式。