木構造の走査：再帰と反復、退化した木でスタックが尽きる深さ

2026年11月改訂： 2021年に韓国語で公開した記事の C++ サンプル2本を、Apple clang 21 で -Wall -Wextra と -fsanitize=address,undefined -g の両方でビルドし直して実行しました。どちらも警告0件、サニタイザーの報告0件で、出力も2021年と同じでした。直す必要があったのは本文のほうで、full と perfect の二分木を混同していたこと、レベル順走査を省いていたこと、そして深い木で再帰がどう壊れるかに触れていなかったことです。最後の点は Apple M1 Pro で実測しました。

この記事は、木構造をこれから学ぶ人と、テストでは動いていた再帰の木処理が本番データで「Segmentation fault」だけを残して落ちた経験のある人に向けたものです。後者への答えを先に書くと、再帰の走査は1段につき1フレームのスタックを使うので、使用量はノード数ではなく木の高さで決まります。バランスの取れた木なら問題になりませんが、整列済みデータを入れた二分探索木のような退化木では高さ＝ノード数になり、今回の計測ではビルド設定によって約4万〜26万段でスタックが尽きました。

木構造の用語

木はノードが親子関係でつながった階層的（非線形）な構造で、閉路を持ちません。リスト・スタック・キューが一列に並ぶのに対して、木は枝分かれします。ファイルシステム、HTML の DOM、データベースの索引（B木）、JSON、コンパイラの構文木はどれも木です。

上の図で用語を整理します。

• 根（root）：親を持たない唯一のノード。ここでは A。
• 親・子・兄弟：A の子は B と C で、B と C は兄弟（sibling）です。
• 葉（leaf）：子を持たないノード。I、J、K、L。それ以外は内部ノードです。
• 次数（degree）：ノードが持つ子の数。A・B・C は2、D は1。木の次数は各ノードの次数の最大値です。
• 深さ（depth）：根からそのノードまでの辺の数。A は0、D は2、I は3。
• 高さ（height）：根からいちばん深い葉までの辺の数。この木は3です。
• レベル：教科書によって0から数えるものと1から数えるものがあります。2021年の記事は1から数えていました。式を比べる前に数え方を確認しないと、1ずれた答えになりがちです。

子の数が決まっていない木：左の子・右の兄弟

子がいくつあるか分からない一般の木は、各ノードに「最初の子」と「次の兄弟」の2つのポインタだけを持たせる 左の子・右の兄弟（Left Child-Right Sibling） 表現で扱えます。

2021年版は警告なしでコンパイルできましたが、既定コンストラクタ Tree() { } が2つのポインタを初期化していませんでした。サンプルでは呼ばれないので表に出ませんでしたが、このコンストラクタで作ったノードはゴミのアドレスをたどります。メンバの既定値で初期化すればこの罠はなくなります。

#include <cstdio>

struct TreeNode {                     // left child, right sibling
    char data;
    TreeNode* child = nullptr;        // first child
    TreeNode* sibling = nullptr;      // next sibling on the same level
    explicit TreeNode(char d) : data(d) {}

    void append_child(TreeNode* c) {
        if (!child) { child = c; return; }
        TreeNode* t = child;
        while (t->sibling) t = t->sibling;
        t->sibling = c;
    }
    void print(int depth) const {
        std::printf("%*s%c\n", depth, "", data);
        if (child)   child->print(depth + 1);   // one level down
        if (sibling) sibling->print(depth);     // same level
    }
};

int main() {
    TreeNode root('A'), B('B'), C('C'), D('D'), E('E'), F('F');
    root.append_child(&B);
    B.append_child(&C);
    B.append_child(&D);
    root.append_child(&E);
    E.append_child(&F);
    root.print(0);
}

A
 B
  C
  D
 E
  F

2021年の実行結果の末尾にあった「続行するには何かキーを押してください」に当たる一文は、プログラムの出力ではなく Visual Studio のコンソールが付けたものなので省きました。

二分木の形：完全・パーフェクト・退化

二分木は各ノードの子が最大2つの木です。形によって名前があり、アルゴリズムはその形を前提にしています。

完全二分木（complete）：最後の段以外はすべて埋まり、最後の段は左から隙間なく詰まった木です（上図）。隙間がないので配列に無駄なく収まり、二分ヒープはこの形を使います。

パーフェクト二分木（perfect、「飽和二分木」と訳されることもあります）：内部ノードの子がすべて2つで、葉がすべて同じ段にある木です。高さ h ならノードはちょうど 2^(h+1) − 1 個。パーフェクト二分木は必ず完全二分木ですが、逆は成り立ちません。

2021年の記事はこれを「Full Binary Tree」と書き、「葉以外のすべてのノードの次数が2」と定義していました。この定義は full binary tree（全二分木） のもので、葉の深さがそろっている必要はありません。一方、図に描かれていたのは葉がそろった perfect の木でした。日本語でも訳語が揺れやすいところなので、英語名と定義をセットで覚えるのが確実です。

退化木（skewed / degenerate、偏った木）：どのノードも片側にしか子を持たない木です。実質は連結リストで、高さはノード数 − 1 になります。素の二分探索木に整列済みのキーを順に入れるとこの形になり、後半の計測で再帰を落とすのもこの形です。

4種類の走査を実際に動かす

2021年の記事は前順・中順・後順の3つだけで、レベル順は「説明を省く」としていました。ここでは根 A、その下に B と C、次の段に D・E・F・G、D の下に H と I を持つ9ノードの木で4つすべてを動かします。

赤い矢印は前順の訪問順です。2021年の記事にあった中順・後順の矢印図は矢印が交差して追いにくかったため、次の図に置き換えました。

深さ優先の3つは同じ関数で、printf の位置が違うだけです。レベル順は再帰の代わりにキューを使います。

void preorder(const Node* n)  { if (!n) return; std::printf("%c ", n->data); preorder(n->left); preorder(n->right); }
void inorder(const Node* n)   { if (!n) return; inorder(n->left); std::printf("%c ", n->data); inorder(n->right); }
void postorder(const Node* n) { if (!n) return; postorder(n->left); postorder(n->right); std::printf("%c ", n->data); }

void levelorder(const Node* root) {
    std::queue<const Node*> q;
    if (root) q.push(root);
    while (!q.empty()) {
        const Node* n = q.front(); q.pop();
        std::printf("%c ", n->data);
        if (n->left)  q.push(n->left);
        if (n->right) q.push(n->right);
    }
}

用途で覚えると忘れにくくなります。

明示的なスタックによる反復走査

再帰呼び出しは呼ぶたびに、小さくて大きさの決まったコールスタックにフレームを積みます。同じ処理をヒープ上の std::vector をスタック代わりにして書けば、深さの上限は実質なくなります。

void preorder_iter(const Node* root) {
    std::vector<const Node*> st;
    if (root) st.push_back(root);
    while (!st.empty()) {
        const Node* n = st.back(); st.pop_back();
        std::printf("%c ", n->data);
        if (n->right) st.push_back(n->right);   // right first, so left is popped first
        if (n->left)  st.push_back(n->left);
    }
}
void inorder_iter(const Node* root) {
    std::vector<const Node*> st;
    const Node* cur = root;
    while (cur || !st.empty()) {
        while (cur) { st.push_back(cur); cur = cur->left; }
        cur = st.back(); st.pop_back();
        std::printf("%c ", cur->data);
        cur = cur->right;
    }
}
void postorder_iter(const Node* root) {          // two-stack version
    std::vector<const Node*> st, out;
    if (root) st.push_back(root);
    while (!st.empty()) {
        const Node* n = st.back(); st.pop_back();
        out.push_back(n);
        if (n->left)  st.push_back(n->left);
        if (n->right) st.push_back(n->right);
    }
    for (auto it = out.rbegin(); it != out.rend(); ++it) std::printf("%c ", (*it)->data);
}

再帰版と反復版を同じ木で動かした実際の出力です。clang++ -std=c++17 -Wall -Wextra で警告なし、ASan・UBSan ビルドでもエラーはありませんでした。

pre   (rec):  A B D H I E C F G
pre   (iter): A B D H I E C F G
in    (rec):  H D I B E A F C G
in    (iter): H D I B E A F C G
post  (rec):  H I D E B F G C A
post  (iter): H I D E B F G C A
level:        A B C D E F G H I

前順・中順・後順は2021年の記事の結果と1文字まで同じです。2021年のプログラム自体も再実行し、同じ3行を得ました。

再帰は何段まで耐えるか（実測）

ここからが本題です。新しいノードごとに既存の根を左の子としてつなぎ、左にだけ N 段伸びた木を作ります。それを再帰の中順走査で数え、解放は再帰ではなくループで行います。

long count_rec(const Node* n) {                // in-order, recursive
    if (!n) return 0;
    long c = count_rec(n->left);
    c += 1;
    return c + count_rec(n->right);
}
// main: for (i < N) root = new Node{i, root, nullptr};
//       count_rec(root) or count_iter(root);
//       while (root) { Node* next = root->left; delete root; root = next; }

N を二分探索で動かし、最初に落ちる深さを探しました。ulimit -s は 8,176KB で、2回通して測っても同じ値でした。

• -O0：174,252段までは正常、174,313段で Segmentation fault（終了コード139）。メッセージもスタックトレースも出ません。
• -O2：261,367段まで正常。フレームが小さくなる分だけ深く潜れますが、問題が消えるわけではありません。右の子への呼び出しは末尾呼び出しにできても、左へ下る呼び出しはできないからです。
• ASan + UBSan（-O0）：40,164段で停止。サニタイザーのフレームは大きいので早く落ちますが、原因を教えてくれます。

AddressSanitizer:DEADLYSIGNAL
=================================================================
==64345==ERROR: AddressSanitizer: stack-overflow on address 0x00016f463ff8 (pc 0x0001001a09a0 bp 0x00016f464050 sp 0x00016f463f90 T0)
    #0 0x0001001a09a0 in count_rec(Node const*) depth.cpp
    #1 0x0001001a09cc in count_rec(Node const*) depth.cpp:11
    #2 0x0001001a09cc in count_rec(Node const*) depth.cpp:11

同じバイナリの反復版 count_iter は、3種類すべてのビルドで 1,000万段 の木に対して visited 10000000 nodes と出力し、正常に終了しました。

デストラクタも再帰する

走査を1行も書かなくても同じ壁に当たることがあります。子を std::unique_ptr<Node> left, right; で所有していると、根を破棄したときに左の子のデストラクタが呼ばれ、その中でさらに左の子のデストラクタが呼ばれ…と続きます。-O2 ビルドでは261,367段までは正常終了し、それより深いと main の閉じ括弧の時点で終了コード139で落ちました。標準出力がフラッシュされる前に落ちるため、直前に printf したはずの行すら表示されません。深くなりうる木は、解放もループで行うのが安全です。

再帰と反復の使い分け

• 高さが O(log n) に保証される木（赤黒木、ヒープ、平衡木）：再帰のほうが読みやすく、十分安全です。100万ノードでも高さは20〜40程度です。
• 高さが入力しだいの木（素の BST、ユーザーデータから作る木、パーサの出力）：反復版を使うか深さの上限を設けます。メイン以外のスレッドはスタックがさらに小さいことが多く、この Mac では pthread_attr_getstacksize が新しいスレッドに対して 512KB を返しました。限界はおよそ16分の1になります。
• ときどき落ちるセグフォルトを調べるとき：まず ASan ビルドで動かすのが近道です。あふれた関数名をすぐに示してくれます。

まとめ

• レベルや高さの数え方は教科書によって違います。0始まりか1始まりかを先に確認しましょう。
• full（子が0か2）と perfect（葉が同じ段）は別の概念で、2021年の記事はこれを混同していました。
• 前順・中順・後順は訪問のタイミングだけが違い、レベル順はキューで実装します。4つとも実行結果を載せました。
• 再帰走査のスタック使用量は木の高さに比例します。退化木では 8MB のスタックが -O0 で約17万段、-O2 で約26万段、ASan で約4万段で尽き、反復版は1,000万段でも問題ありませんでした。

二分木に順序の規則を加えると二分探索木、形の規則を加えるとヒープになります。木ではなく整列済み配列で探す方法は二分探索の記事で扱っています。