Java二叉树的四种遍历(递归和非递归)

Java二叉树的四种遍历

二叉树是一种非常常用的数据结构，在算法和数据结构中有广泛的应用。对于二叉树的操作，最常用的就是遍历。在Java中，我们可以使用递归和非递归两种方式来进行遍历。本文将详细讲解Java二叉树的四种遍历方式：前序遍历、中序遍历、后序遍历和层次遍历。

二叉树的定义

二叉树是每个节点最多有两个子树的树结构，通常被用于实现二叉查找树和二叉堆。二叉树有五种遍历方式：前序遍历、中序遍历、后序遍历、层次遍历和倒序遍历。

二叉树的三种遍历方式

前序遍历

前序遍历顺序为：根节点 -> 左子树 -> 右子树。对于前序遍历，递归和非递归两种方式都十分容易实现。以下是递归和非递归实现前序遍历的示例代码：

// 递归实现前序遍历
public void preOrderTraversal(TreeNode root){
    if(root == null){
        return;
    }
    System.out.print(root.val + " ");
    preOrderTraversal(root.left);
    preOrderTraversal(root.right);
}

// 非递归实现前序遍历
public void preOrderTraversal(TreeNode root){
    Stack<TreeNode> stack = new Stack<>();
    while(root != null || !stack.isEmpty()){
        while(root != null){
            stack.push(root);
            System.out.print(root.val + " ");
            root = root.left;
        }
        if(!stack.isEmpty()){
            root = stack.pop();
            root = root.right;
        }
    }
}

中序遍历

中序遍历顺序为：左子树 -> 根节点 -> 右子树。对于中序遍历，递归和非递归两种方式都十分容易实现。以下是递归和非递归实现中序遍历的示例代码：

// 递归实现中序遍历
public void inOrderTraversal(TreeNode root){
    if(root == null){
        return;
    }
    inOrderTraversal(root.left);
    System.out.print(root.val + " ");
    inOrderTraversal(root.right);
}

// 非递归实现中序遍历
public void inOrderTraversal(TreeNode root){
    Stack<TreeNode> stack = new Stack<>();
    while(root != null || !stack.isEmpty()){
        while(root != null){
            stack.push(root);
            root = root.left;
        }
        if(!stack.isEmpty()){
            root = stack.pop();
            System.out.print(root.val + " ");
            root = root.right;
        }
    }
}

后序遍历

后序遍历顺序为：左子树 -> 右子树 -> 根节点。对于后序遍历，递归和非递归两种方式都比较复杂，需要用到其他数据结构。以下是递归和非递归实现后序遍历的示例代码：

// 递归实现后序遍历
public void postOrderTraversal(TreeNode root){
    if(root == null){
        return;
    }
    postOrderTraversal(root.left);
    postOrderTraversal(root.right);
    System.out.print(root.val + " ");
}

// 非递归实现后序遍历
public void postOrderTraversal(TreeNode root){
    Stack<TreeNode> stack = new Stack<>();
    TreeNode prev = null;
    while(root != null || !stack.isEmpty()){
        while(root != null){
            stack.push(root);
            root = root.left;
        }
        root = stack.pop();
        if(root.right == null || root.right == prev){
            System.out.print(root.val + " ");
            prev = root;
            root = null;
        } else {
            stack.push(root);
            root = root.right;
        }
    }
}

层次遍历

层次遍历顺序为：从根节点开始，按照从上到下、从左到右的顺序遍历所有节点。层次遍历需要借助辅助队列来实现，以下是层次遍历的示例代码：

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

总结

本文讲解了Java二叉树的四种遍历方式：前序遍历、中序遍历、后序遍历和层次遍历。其中，前序遍历和中序遍历可以使用递归和非递归两种方式进行遍历，而后序遍历和层次遍历需要使用辅助数据结构来实现。对于数据结构和算法的学习，遍历二叉树是基础，建议大家多进行实践和练习。