基本情報技術者試験基礎・応用
条件を読む・根拠を説明する
二分木の再帰計数
条件を整理し、答えを選んでから解き方を確認しましょう。
空木のNは0、非空木は1+N(左)+N(右)。根の左部分木のN=3、右部分木のN=2のとき全体のNはどれか。
答え・解き方を読む
6
図で見る
根の1個と二つの部分木を足す
図を拡大して見る ↗左右の箱は個別の節点を省略した部分木です。左右の値だけを足して根の1個を落とさないようにします。
図は問題の関係を整理する模式図です。記号には各問題の数値を当てはめます。寸法・面積・時間の縮尺や、実施工の全条件は表していません。
考える順序
- 1左右部分木は根を含まない
- 2左3と右2に根自身の1を加える
- 31+3+2=6となる
選択肢ごとの理由
- 比較 · 5
根自身の1が不足しています。
- 比較 · 3
木全体でなく一方の部分木の値です。
- 比較 · 7
左右はそれぞれ全ノード数なので余分な根は足しません。
- 正解 · 6
左右部分木は根を含まない。左3と右2に根自身の1を加える。1+3+2=6となる。