Java二叉树的四种遍历（递归与非递归）

简介

二叉树是一种常见的数据结构，其遍历方式包括前序遍历、中序遍历、后序遍历和层序遍历。Java中可以使用递归和非递归的方式进行遍历。在该攻略中，我们将详细介绍Java二叉树的四种遍历方式，包括递归和非递归实现，帮助读者提高对Java数据结构的理解。

前序遍历

在前序遍历中，我们先访问二叉树的根节点，然后分别访问左子树和右子树。在Java中，我们可以使用递归和非递归的方式实现前序遍历。

递归实现

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

非递归实现

public 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);
        }
    }
}

中序遍历

在中序遍历中，我们先访问二叉树的左子树，然后访问根节点，最后再访问右子树。同样地，在Java中我们也可以使用递归和非递归的方式实现中序遍历。

递归实现

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

非递归实现

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

后序遍历

在后序遍历中，我们先访问二叉树的左子树，然后访问右子树，最后再访问根节点。同样地，在Java中我们也可以使用递归和非递归的方式实现后序遍历。

递归实现

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

非递归实现

public void postOrderTraversal(TreeNode root){
    if(root == null){
        return;
    }
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    TreeNode prev = null;
    while(!stack.isEmpty()){
        TreeNode curr = stack.peek();
        if(prev == null || prev.left == curr || prev.right == curr){
            if(curr.left!=null){
                stack.push(curr.left);
            }else if(curr.right!=null){
                stack.push(curr.right);
            }
        }else if(curr.left == prev){
            if(curr.right!=null){
                stack.push(curr.right);
            }
        }else{
            System.out.println(curr.val);
            stack.pop();
        }
        prev = curr;
    } 
}

层序遍历

在层序遍历中，我们按照从上到下、从左到右的顺序访问二叉树的每个节点。同样地，在Java中我们也可以使用队列的非递归方式实现层序遍历。

非递归实现

public void levelOrderTraversal(TreeNode root){
    if(root == null){
        return;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while(!queue.isEmpty()){
        int levelSize = queue.size();
        for(int i=0;i<levelSize;i++){
            TreeNode curr = queue.poll();
            System.out.println(curr.val);
            if(curr.left!=null){
                queue.offer(curr.left);
            }
            if(curr.right!=null){
                queue.offer(curr.right);
            }
        }
    } 
}

示例说明

以下为一个简单的二叉树：

       1
     /   \
    2     3
   / \
  4   5

前序遍历

递归：1 2 4 5 3

非递归：1 2 4 5 3

中序遍历

递归：4 2 5 1 3

非递归：4 2 5 1 3

后序遍历

递归：4 5 2 3 1

非递归：4 5 2 3 1

层序遍历

1 2 3 4 5

以上是Java二叉树的四种遍历方式及其实现。希望能够帮助读者更好地掌握Java的数据结构，提高代码能力。