Java二叉树的四种遍历方式详解

二叉树是一种常见的数据结构，在Java中也有很多实现方式。对二叉树进行遍历是必不可少的操作，Java提供了四种不同的遍历方式，这篇文章会详细讲解这四种方法，以及对应的代码实现和示例说明。

什么是二叉树

二叉树是一种树结构，其每个结点最多只有两个子节点。其中一个为左子节点，一个为右子节点。

每个结点都由三部分组成：一个数据域、左子树和右子树。左子树和右子树同样是二叉树，其结点也由三部分组成：一个数据域、左子树和右子树。

代码实现

在Java中，我们可以通过类似下面的代码来定义一个二叉树节点的类：

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

二叉树的四种遍历方式

先序遍历

先序遍历是指对二叉树的遍历方式是“根节点->左子树->右子树”。

先序遍历可以通过递归实现，对于每个结点，先输出该结点的数据域，然后递归遍历该结点的左子树和右子树。

public void preorderTraversal(TreeNode root){
    if(root == null){
        return;
    }
    System.out.print(root.val+" ");
    preorderTraversal(root.left);
    preorderTraversal(root.right);
}

中序遍历

中序遍历是指对二叉树的遍历方式是“左子树->根节点->右子树”。

中序遍历同样可以通过递归实现，对于每个结点，先递归遍历该结点的左子树，然后输出该结点的数据域，最后递归遍历该结点的右子树。

public void inorderTraversal(TreeNode root){
    if(root == null){
        return;
    }
    inorderTraversal(root.left);
    System.out.print(root.val+" ");
    inorderTraversal(root.right);
}

后序遍历

后序遍历是指对二叉树的遍历方式是“左子树->右子树->根节点”。

后序遍历同样可以通过递归实现，对于每个结点，先递归遍历该结点的左子树和右子树，然后输出该结点的数据域。

public void postorderTraversal(TreeNode root){
    if(root == null){
        return;
    }
    postorderTraversal(root.left);
    postorderTraversal(root.right);
    System.out.print(root.val+" ");
}

层次遍历

层次遍历是指对二叉树的遍历方式是按照层次从上到下，从左到右进行遍历，每层结点从左到右输出。

层次遍历需要借助队列实现，将根结点加入队列中，然后依次出队遍历队列中的结点，将其非空子节点加入队列中。

public void bfsTraversal(TreeNode root){
    if (root == null){
        return;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    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);
            }
        }
    }
}

示例说明

示例1

我们先创建一颗二叉树：

      1
     / \
    2   3
   / \   \
  4   5   6

我们可以先通过对应的代码创建这棵树：

TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
root.right.right = new TreeNode(6);

然后我们可以通过先序遍历方法遍历这棵树，并输出结果：

preorderTraversal(root); // 1 2 4 5 3 6

同样地，我们可以通过其他三个遍历方式来遍历这棵树，并输出结果。

示例2

我们再创建一棵二叉树：

        5
       / \
      4   7
     /   / \
    2   6   8

同理，我们可以先通过对应的代码来创建这棵树：

TreeNode root = new TreeNode(5);
root.left = new TreeNode(4);
root.right = new TreeNode(7);
root.left.left = new TreeNode(2);
root.right.left = new TreeNode(6);
root.right.right = new TreeNode(8);

然后我们可以通过层次遍历方法遍历这棵树，并输出结果：

bfsTraversal(root); // 5 4 7 2 6 8

同样地，我们也可以通过其他三个遍历方式来遍历这棵树，并输出结果。

总的来说，Java二叉树的四种遍历方式都是通过递归来实现的，代码实现也比较简单。但我们要注意不同遍历方式的顺序，并了解对应的遍历顺序特点，才能适当地应用到实际工作当中。