C++で二分木の前順走査（プレオーダー）をスタックにより非再帰的に実装するプログラム

木の走査（ツリートラバーサル）はグラフ走査の一種で、木に含まれるすべてのノードをそれぞれ一度だけ訪問して確認・出力する処理のことです。二分探索木における前順走査（プレオーダー走査）では、「根（Root）→ 左部分木（Left）→ 右部分木（Right）」という順序でノードを訪問します。

本記事では、再帰呼び出しを使わずスタックを活用して前順走査を非再帰的に実装するC++プログラムを、コード例とともにわかりやすく解説します。

前順走査の例

たとえば、次のような二分木が与えられたとします。

この木に対する前順走査の結果は次のとおりです。

前順走査の結果：5 3 2 4 8 9

非再帰的な前順走査を行うC++プログラム

サンプルコード

#include<iostream>
#include <stack>
using namespace std;
struct node {
    int data;
    struct node *left;
    struct node *right;
};
struct node *createNode(int val) {
    struct node *temp = (struct node *)malloc(sizeof(struct node));
    temp->data = val;
    temp->left = temp->right = NULL;
    return temp;
}
void preorder(struct node *root) {
    if (root == NULL)
        return;
    stack<node *> nodeStack;
    nodeStack.push(root);
    while (nodeStack.empty() == false) {
        struct node *temp_node = nodeStack.top();
        cout << temp_node->data << " ";
        nodeStack.pop();
        if (temp_node->right)
            nodeStack.push(temp_node->right);
        if (temp_node->left)
            nodeStack.push(temp_node->left);
    }
}
struct node* insertNode(struct node* node, int val) {
    if (node == NULL) return createNode(val);
    if (val < node->data)
        node->left = insertNode(node->left, val);
    else if (val > node->data)
        node->right = insertNode(node->right, val);
    return node;
}
int main() {
    struct node *root = NULL;
    root = insertNode(root, 5);
    insertNode(root, 8);
    insertNode(root, 3);
    insertNode(root, 2);
    insertNode(root, 6);
    insertNode(root, 9);
    insertNode(root, 4);
    cout << "Pre-Order traversal of the Binary Search Tree is: ";
    preorder(root);
}

実行結果

Pre-Order traversal of the Binary Search Tree is: 5 3 2 4 8 6 9

コードの詳細解説

1. ノードを表す構造体（struct node）

上記プログラムでは、構造体 node が木の1つのノードを表します。この構造体は自分自身と同じ型（struct node 型）へのポインタをメンバとして持つため、「自己参照構造体」と呼ばれます。

struct node {
    int data;
    struct node *left;
    struct node *right;
};

2. createNode() 関数 ― ノードの生成

createNode() 関数は新しいノード temp を作成し、malloc によってメモリを確保します。引数 val の値は data メンバに格納され、左右の子ポインタには NULL が設定されます。

struct node *createNode(int val) {
    struct node *temp = (struct node *)malloc(sizeof(struct node));
    temp->data = val;
    temp->left = temp->right = NULL;
    return temp;
}

3. preorder() 関数 ― スタックによる非再帰走査

preorder() 関数は、スタックを使って木の要素を前順に出力します。処理の流れは以下のとおりです。

• まず根ノードをスタックにプッシュします。
• スタックが空になるまで while ループを繰り返します。
• ループ内では、スタックの先頭ノードのデータを表示してからポップします。
• 続いて、そのノードの右の子を先に、左の子を後にプッシュします。

スタックは後入れ先出し（LIFO）のデータ構造のため、右の子を先に積むことで、次の反復では必ず左側のノードが先に取り出されます。これにより「根 → 左 → 右」という前順の順序が自然に保たれるのです。

void preorder(struct node *root) {
    if (root == NULL)
        return;
    stack<node *> nodeStack;
    nodeStack.push(root);
    while (nodeStack.empty() == false) {
        struct node *temp_node = nodeStack.top();
        cout << temp_node->data << " ";
        nodeStack.pop();
        if (temp_node->right)
            nodeStack.push(temp_node->right);
        if (temp_node->left)
            nodeStack.push(temp_node->left);
    }
}

4. insertNode() 関数 ― ノードの挿入

insertNode() 関数は、指定した値を二分探索木の適切な位置に挿入します。ノードが NULL の場合は createNode() を呼び出して新しいノードを作成し、そうでない場合は値の大小を比較しながら木の中から挿入位置を探します。

struct node* insertNode(struct node* node, int val) {
    if (node == NULL) return createNode(val);
    if (val < node->data)
        node->left = insertNode(node->left, val);
    else if (val > node->data)
        node->right = insertNode(node->right, val);
    return node;
}

5. main() 関数 ― プログラムの実行

main() 関数では、まず根ノードを NULL として初期化し、その後必要な値を持つノードを順番に二分探索木へ挿入していきます。

struct node *root = NULL;
root = insertNode(root, 5);
insertNode(root, 8);
insertNode(root, 3);
insertNode(root, 2);
insertNode(root, 6);
insertNode(root, 9);
insertNode(root, 4);

最後に preorder() 関数を根ノードを引数として呼び出すことで、木のすべての値が前順で画面に表示されます。

cout << "Pre-Order traversal of the Binary Search Tree is: ";
preorder(root);

計算量について

このアルゴリズムは各ノードを一度ずつ処理するため、時間計算量は O(n) です。また、最悪ケース（木が片側に偏っている場合）ではスタックに最大 n 個のノードが積まれる可能性があるため、空間計算量も O(n) となります。