Javaで二分木の走査コードを書く方法

Javaにおけるバイナリツリーの走査には前順、中順、後順の3種類あります。

// 定义二叉树节点
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    
    TreeNode(int val) {
        this.val = val;
    }
}

// 前序遍历
void preOrderTraversal(TreeNode root) {
    if (root == null) {
        return;
    }
    
    System.out.print(root.val + " ");  // 先访问根节点
    preOrderTraversal(root.left);      // 再前序遍历左子树
    preOrderTraversal(root.right);     // 最后前序遍历右子树
}

// 中序遍历
void inOrderTraversal(TreeNode root) {
    if (root == null) {
        return;
    }
    
    inOrderTraversal(root.left);       // 先中序遍历左子树
    System.out.print(root.val + " ");  // 再访问根节点
    inOrderTraversal(root.right);      // 最后中序遍历右子树
}

// 后序遍历
void postOrderTraversal(TreeNode root) {
    if (root == null) {
        return;
    }
    
    postOrderTraversal(root.left);     // 先后序遍历左子树
    postOrderTraversal(root.right);    // 再后序遍历右子树
    System.out.print(root.val + " ");  // 最后访问根节点
}

構築した二叉木の走査は、必要に応じて走査方法を選択して行うことができます。例：

public static void main(String[] args) {
    // 构建二叉树
    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);
    
    // 前序遍历
    System.out.println("前序遍历结果：");
    preOrderTraversal(root);
    
    // 中序遍历
    System.out.println("\n中序遍历结果：");
    inOrderTraversal(root);
    
    // 后序遍历
    System.out.println("\n后序遍历结果：");
    postOrderTraversal(root);
}