修了試験 2026-06-14実施分 基本情報技術者試験 問6

解説

正解は3です。 行きがけ順（先行順）の深さ優先探索では、節点を訪問したあと、その子を左から順に、子孫をすべてたどってから次の子へ進みます。 問題文の「木の根の左の葉から」は、根から出発して、左側の枝から順に葉へ向かってたどるという意味に読みます。 図の木は、根の下に左・中央・右の3つの部分木があり、●は中央の部分木の右側の節点の左の子です。 【計算】 根を0番目とします。 左の部分木では、左の子が1番目、その左の葉が2番目、右の子が3番目、その下の2つの葉が4番目と5番目です。 中央の部分木では、中央の子が6番目、その左の子が7番目、その下の葉が8番目です。 中央の子の真ん中の葉が9番目、右の子が10番目です。 右の子の下の左の葉（●）が11番目です。 【選択肢別解説】 1：× 9番目は、中央の部分木の真ん中にある葉です。 ●はそのあとに訪問されます。 2：× 10番目は、●の親にあたる節点です。 行きがけ順では親を先に訪問するので、●はその次になります。 3：○ 上のとおりに数えると、●は11番目に探索されます。 4：× 12番目は、●の右隣にある兄弟の葉です。 ●は左の子なので、それより先に訪問されます。 【ポイント】 行きがけ順は「自分、左の部分木、右の部分木」の順で、親は必ず子より先に訪問されます。 節点の数え漏れを防ぐため、部分木ごとに番号を区切って数えると確実です。