前順走査

前順走査では、ノードの値を「根 → 左の子 → 右の子」の順に処理します。

再帰的な実装

public void traverse(Node node) {
    if (node == null) {
        return;
    }
    System.out.println(node.value);
    traverse(node.left);
    traverse(node.right);
}

非再帰的な実装

非再帰では、スタックを使用してノードを管理します。根ノードを最初に処理し、その後にその子ノードをスタックに追加します。左の子を先に処理する必要があるため、右の子からスタックに追加し、次に左の子を追加します。

Stack<Node> stack = new Stack<>();
stack.push(root);

while (!stack.isEmpty()) {
    Node current = stack.pop();
    System.out.println(current.value);
    
    if (current.right != null) {
        stack.push(current.right);
    }
    if (current.left != null) {
        stack.push(current.left);
    }
}

中順走査

中順走査では、「左の子 → 根 → 右の子」の順で処理します。

再帰的な実装

public void traverse(Node node) {
    if (node == null) {
        return;
    }
    traverse(node.left);
    System.out.println(node.value);
    traverse(node.right);
}

非再帰的な実装

中順走査は少し複雑です。左部分木を先に処理する必要があるため、ノードをすぐにスタックから取り除くことはできません。代わりに、左側に子ノードがない場合にのみノードを出力します。

Stack<Node> stack = new Stack<>();
Node current = root;

while (!stack.isEmpty() || current != null) {
    if (current != null) {
        stack.push(current);
        current = current.left;
    } else {
        current = stack.pop();
        System.out.println(current.value);
        current = current.right;
    }
}

後順走査

後順走査では、「左の子 → 右の子 → 根」の順で処理します。

再帰的な実装

public void traverse(Node node) {
    if (node == null) {
        return;
    }
    traverse(node.left);
    traverse(node.right);
    System.out.println(node.value);
}

非再帰的な実装

後順走査は最も複雑です。先順走査と似ていますが、ノードの親情報を保持する必要があります。そのため、2つのスタックを使用します。最初のスタックで「根 → 右 → 左」の順にノードを追加し、次のスタックではその逆順で出力します。

Stack<Node> stack1 = new Stack<>();
Stack<Node> stack2 = new Stack<>();

stack1.push(root);

while (!stack1.isEmpty()) {
    Node node = stack1.pop();
    stack2.push(node);
    
    if (node.left != null) {
        stack1.push(node.left);
    }
    if (node.right != null) {
        stack1.push(node.right);
    }
}

while (!stack2.isEmpty()) {
    System.out.println(stack2.pop().value);
}