二叉树的遍历 java

### Java 二叉树遍历实现方法

#### 定义二叉树的节点类
为了在Java中操作二叉树，首先需要定义一个表示二叉树节点的类。这个类通常包含三个主要部分：存储数据的变量、指向左子节点的引用以及指向右子节点的引用。

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

#### 构建二叉树
创建具体的二叉树实例可以通过设置各个`TreeNode`对象之间的连接来完成。这一步骤可以根据实际需求灵活调整，比如通过数组输入或其他形式的数据源动态建立一棵完整的二叉树结构[^1]。

#### 遍历方式介绍
对于给定的一棵二叉树来说，存在多种不同的遍历策略用于访问其所有的节点：

- **前序遍历**（先根遍历）：按照“根->左->右”的顺序依次访问各节点；
- **中序遍历**：遵循“左->根->右”的路径进行访问；
- **后序遍历**：采取“左->右->根”的模式遍历整个树形结构；
- **层次遍历**：从上到下逐层扫描每一行上的所有元素[^4]。

这里重点展示如何利用递归来实现上述三种常见的深度优先搜索(DFS)类型的遍历算法——即前序、中序和后序遍历。

##### 前序遍历代码示例
当执行前序遍历时，会先处理当前节点再分别对其左右两个分支做相同的操作直到遇到叶子为止。

public static void preOrder(TreeNode node){
    if(node != null){
        System.out.print(node.val+" ");
        preOrder(node.left);
        preOrder(node.right);
    }
}

##### 中序遍历代码示例
中序遍历则是在访问完左侧之后才打印出当前节点的信息并继续探索右侧的部分。

public static void inOrder(TreeNode node){
    if(node!=null){
        inOrder(node.left);
        System.out.print(node.val+" ");
        inOrder(node.right);
    }
}

##### 后序遍历代码示例
而后序遍历则是等到左右两侧都被完全解析过后才会输出该位置处的内容。

public static void postOrder(TreeNode node){
    if(node!=null){
        postOrder(node.left);
        postOrder(node.right);
        System.out.print(node.val+" ");
    }
}

以上就是基于递归机制下的基本二叉树遍历方法，在实际应用当中还可以考虑采用迭代的方式或是借助栈这种辅助性的数据结构来进行优化改进[^2]。