C++でスタックを1つだけ使って二分木の葉ノードを左から右へ出力する方法

本記事では、二分木の葉ノードを左から右の順で出力するプログラムを紹介します。ここでのポイントは、スタックを1つだけしか使えないという制約です。

push() 操作で二分木のノードをスタックに挿入し、pop() 操作で葉ノードを取り出して表示します。

葉ノードとは?

葉ノード(リーフノード)とは、左ポインタと右ポインタがどちらも NULL になっている、木の末端にあるノードのことです。つまり、そのノードは親ノードではないことを意味します。

実行例

入力 : 12 21 32 41 59 33 70
出力 : 41 59 33 70

上記の例では、値が 41、59、33、70 のノードが葉ノードに該当します。

スタックは LIFO(Last In First Out:後入れ先出し)方式のデータ構造で、トップポインタは最後に挿入された要素を指します。この性質により、最後に挿入された葉ノードが他のノードよりも先にスタックから取り出されることになります。

以下のコードは、STL を使用した C++ 実装の例です。

アルゴリズム

START
    Step 1 -> ノード構造体を作成
        int 型の data を宣言
        ノード型のポインタ *left, *right を宣言
    Step 2 -> 値 val を引数に持つノード挿入用関数を作成
        malloc でノード変数を確保
        node->data = val を設定
        node->left = node->right = NULL を設定
        node を返す
    Step 3 -> 関数 void leaf(Node *ptr) を宣言
        vector stackstck を作成
        無限ループ While 1
        IF ptr が有効なら
            stck.push(ptr)
            ptr = ptr->left
        Else
            IF (stck.empty())
                Break
            Else
                IF (stck.top()->right == NULL)
                    ptr = stck.top()
                    stck.pop()
                    IF ptr->left == NULL
                        ptr->data を表示
                End
                While ptr == stck.top()->right
                    ptr = stck.top()
                    stck.pop()
                    IF stck.empty()
                        Break
                    End
                IF !stck.empty()
                    ptr = stck.top()->right
                Else
                    ptr = NULL
                EndIF
            End
        End
    Step 4 -> main() 内で
        Node* root = New(12) のように値を渡して New を呼び出す
        leaf(root) を呼び出す
STOP

C++ 実装コード

#include <bits/stdc++.h>
using namespace std;
// ノードの構造体定義
struct Node {
    Node* left;
    Node* right;
    int data;
};
// 新しいノードを作成する関数
Node* New(int val) {
    Node* node = new Node();
    node->left = node->right = NULL;
    node->data = val;
    return node;
}
// スタックを使って葉ノードを出力する関数
void leaf(Node* ptr) {
    // ノードを格納するスタック
    stack<Node*> stck;
    while (1) {
        if (ptr) {
            stck.push(ptr);
            ptr = ptr->left;
        } else {
            if (stck.empty())
                break;
            else {
                if (stck.top()->right == NULL) {
                    ptr = stck.top();
                    stck.pop();
                    // 葉ノードを表示
                    if (ptr->left == NULL)
                        printf("%d ", ptr->data);
                }
                while (ptr == stck.top()->right) {
                    ptr = stck.top();
                    stck.pop();
                    if (stck.empty())
                        break;
                }
                if (!stck.empty())
                    ptr = stck.top()->right;
                else
                    ptr = NULL;
            }
        }
    }
}
int main() {
    printf("leaf nodes at end level are : ");
    Node* root = New(12);
    root->left = New(21);
    root->right = New(32);
    root->left->left = New(41);
    root->left->right = New(59);
    root->right->left = New(33);
    root->right->right = New(70);
    leaf(root);
    return 0;
}

処理の流れの解説

このアルゴリズムは、反復的な中順走査(インオーダー走査)の考え方を応用しています。

• まず、現在のノードが存在する限り、スタックに push しながら左の子へ移動していきます。
• 左端まで到達したら、スタックのトップにあるノードを調べます。そのノードの右の子が NULL であり、かつ左の子も NULL であれば、それは葉ノードなので値を出力します。
• 右側の部分木の走査が完了したノードは、スタックから pop しながら親へ戻ります。
• スタックが空になるまでこの処理を繰り返すことで、すべての葉ノードが左から右の順に出力されます。

出力結果

上記のプログラムを実行すると、以下の出力が得られます。

leaf nodes at end level are : 41 59 33 70

このように、再帰を使わずスタックを1つだけ用いても、二分木の葉ノードを正しく左から右の順序で出力できることが確認できます。