非再帰的なJavaプログラムを使用した中間順序の走査

非再帰的な中間順序の走査には、スタックを使用します。以下の例では、二分木のノードを表すTreeNodeクラスがあると仮定します。

import java.util.Stack;
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) {
        this.val = val;
        left = null;
        right = null;
    }
}
public class InorderTraversal {
    public static void inorder(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode current = root;
        while (current != null || !stack.isEmpty()) {
            while (current != null) {
                stack.push(current);
                current = current.left;
            }
            current = stack.pop();
            System.out.print(current.val + " ");
            current = current.right;
        }
    }
    public static void main(String[] args) {
        // 二分木の例を作成
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(3);
        root.right = new TreeNode(7);
        root.left.left = new TreeNode(2);
        root.left.right = new TreeNode(4);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(8);
        // 中間順序の走査を実行
        System.out.println("中間順序の走査結果:");
        inorder(root);
    }
}

上記のプログラムでは、スタックを使用して中間順序の走査を実現しています。現在のノードをスタックにプッシュし、左の子ノードに移動します。左の子ノードがなくなったら、スタックからノードをポップして表示し、そのノードの右の子ノードに移動します。このプロセスを繰り返し、スタックが空になり、現在のノードがnullになるまで続けます。

上記のプログラムを実行すると、中間順序の走査結果が表示されます。この方法を使用すると、再帰を使用せずに中間順序の走査を行うことができます。

この記事では、非再帰的なJavaプログラムを使用して中間順序の走査を行う方法を解説しました。非再帰的な方法は、再帰を使用せずに中間順序の走査を実現するため、メモリの使用量を削減することができます。