Javaで二分木のインオーダー（中間順）トラバーサルを実行するプログラム

この記事では、二分木におけるインオーダー（中間順）トラバーサルの実装方法について詳しく解説します。インオーダー走査とは、各ノードを「左の部分木 → ノード自身 → 右の部分木」の順番で処理する手法です。つまり、まず左側の部分木をすべて訪問し、その後にノード自体を処理し、最後に右側の部分木を訪れます。

実際の動作例を見てみましょう。

入力（プログラムの実行）：

Run the program

期待される出力：

The In-Order traversal of the tree_object is:
5->12->6->1->9->

アルゴリズム

インオーダー走査は、以下の手順で実行します。

1. 処理を開始する。
2. ノードのデータ構造を定義したクラスをあらかじめ用意しておく。
3. クラスの新しいインスタンスを作成する。
4. 作成したインスタンスを適切な値で初期化する。
5. インオーダー走査を実行するメソッドを呼び出す。
6. 結果を表示する。
7. 処理を終了する。

例1：再帰を使ったインオーダー走査

まずは、もっとも一般的な再帰呼び出しを利用した実装例です。左部分木・ノード・右部分木の順に再帰的に処理することで、シンプルに記述できます。

class Node {
    int item;
    Node left_node, right_node;
    public Node(int key) {
        item = key;
        left_node = right_node = null;
    }
}
public class Tree {
    Node root;
    Tree() {
        root = null;
    }
    void inOrder(Node node) {
        if (node == null)
            return;
        inOrder(node.left_node);
        System.out.print(node.item + "->");
        inOrder(node.right_node);
    }
    public static void main(String[] args) {
        Tree tree_object = new Tree();
        System.out.println("A tree_object object is defined: ");
        tree_object.root = new Node(1);
        tree_object.root.left_node = new Node(12);
        tree_object.root.right_node = new Node(9);
        tree_object.root.left_node.left_node = new Node(5);
        tree_object.root.left_node.right_node = new Node(6);
        System.out.println("The In-Order traversal of the tree_object is: ");
        tree_object.inOrder(tree_object.root);
    }
}

出力結果

A tree_object object is defined:
The In-Order traversal of the tree_object is:
5->12->6->1->9->

例2：スタックを使った非再帰的なインオーダー走査

次に、Stack（スタック）を利用した非再帰（反復的）な実装例を紹介します。再帰を使わないため、深い木構造でもスタックオーバーフローの心配が少なくなるというメリットがあります。

import java.util.Stack;
class Node {
    int data;
    Node left_node, right_node;
    public Node(int item) {
        data = item;
        left_node = right_node = null;
    }
}
class tree {
    Node root;
    void inorder() {
        if (root == null)
            return;
        Stack<Node> temp_stack = new Stack<Node>();
        Node current_node = root;
        while (current_node != null || temp_stack.size() > 0) {
            while (current_node != null) {
                temp_stack.push(current_node);
                current_node = current_node.left_node;
            }
            current_node = temp_stack.pop();
            System.out.print(current_node.data + " ");
            current_node = current_node.right_node;
        }
    }
    public static void main(String args[]) {
        tree tree = new tree();
        System.out.println("A tree_object object is defined: ");
        tree.root = new Node(1);
        tree.root.left_node = new Node(2);
        tree.root.right_node = new Node(3);
        tree.root.left_node.left_node = new Node(4);
        tree.root.left_node.right_node = new Node(5);
        System.out.println("The In-Order traversal of the tree_object is: ");
        tree.inorder();
    }
}

出力結果

A tree_object object is defined:
The In-Order traversal of the tree_object is:
4 2 5 1 3

まとめ

このように、インオーダー走査は「左部分木 → ノード → 右部分木」の順でノードを訪問する手法です。再帰を使えばコードを簡潔に書ける一方、スタックを活用すれば再帰なしで実装でき、大きな木構造にも対応しやすくなります。用途や木のサイズに応じて、適切な方法を選択しましょう。