2026-09-03
tree_count.c
struct tree {
struct tree *left, *right;
};
size_t count(const struct tree *t) {
}
二分木のノード数を返す count を書いてください。t が NULL なら 0 です。渡される木は、右の子をたどる方向に100万段つながっていることがあります。左の子をたどる方向は浅いものとして、呼び出しの深さが右方向の段数に比例しない書き方にしてください。
入力例 1
count(NULL)
出力例 1
0
入力例 2
count(&(struct tree){})
出力例 2
1
入力例 3
count(&(struct tree){&(struct tree){}, &(struct tree){}})
出力例 3
3
Reference
size_t count(const struct tree *t) {
size_t n = 0;
for (; t != NULL; t = t->right)
n += 1 + count(t->left);
return n;
}
素直に再帰で書くと return 1 + count(t->left) + count(t->right); です。右の子への呼び出しは足し算の途中にあり、戻ってきた値に足す仕事が残るので末尾呼び出しではありません。右方向に100万段あれば、100万個のフレームが同時に積まれます。
足し算を累積値 n に移すと、右の子へ進むことが各段の最後の仕事になります。この末尾呼び出しを、引数を書き換えて先頭に戻るループにしたのが参考実装です。t = t->right で右へ進む間はフレームが増えず、再帰するのは左の子だけなので、スタックの深さは左方向の深さで決まります。
末尾呼び出しの形の再帰関数にしただけでは足りません。C の規格は末尾呼び出しの最適化を求めておらず、最適化なしのビルドでは末尾呼び出しでもフレームを積みます1。ループにしておけば、どのビルドでも深さは変わりません。
掲載したのは参考実装で、唯一の正解ではありません。左右どちらの方向にも深くなる木を扱うなら、配列などで自前のスタックを持ち、再帰をなくす書き方になります。
- GCC と Clang は
-O2などの最適化で末尾呼び出しをジャンプに置き換えますが、これは処理系の最適化であって保証ではありません。C23 の規格には、末尾呼び出しを強制する構文はありません。