基本情報技術者 試験情報＆徹底解説 -新制度に完全対応-

以下の問題ですが解説を読んでも理解することができず恥ずかしながら質問させていただきます。

https://www.fe-siken.com/kakomon/18_aki/q12.html

説というのはまるで囲まれたすべての要素（記号も含む）を指すという認識なのですが間違っておりますでしょうか？

節から「節から上に戻るときに」「節から下りたときに」この時どの節から上る、下りるという判断はどのようにするのでしょうか。起点となる節はこういった基準で判断するなどの法則があるのでしょうか？

質問の意味がわかりずらかったらすみません、できる限り補足させていただきます。
よろしくお願いいたします。

> 節というのはまるで囲まれたすべての要素（記号も含む）を指すという認識

はい，それで正しいです。
node（ノード）に対応する日本語が「節，結節，結節点」になります。


> 起点となる節はこういった基準で判断するなどの法則があるのでしょうか？

二分木の場合，「根（root）である節」を起点として，たどり始めます。
リンク先の問題文では，木の最上位の（＋）が書かれた節が，根(root)です。


> 節から「節から上に戻るときに」「節から下りたときに」この時
> どの節から上る、下りるという判断はどのようにするのでしょうか。

問題文に登場する二分木の図を，
巨大な迷路を上から眺めた鳥観図だとイメージしてください。
すべての 節(node) や 枝(branch) は迷路の壁だとイメージしてください。

最上位の（＋）の左側の壁面に左手を触れ，
左手を壁から離さないようにして木の周りを歩き続けていくと，
すべての節と枝をたどって
最上位の（＋）の右側の壁面にまで戻ってくることができます。
歩き続けた経路が，図中の矢印で示されています。

上記によって，節に下りる，節から上に戻る，という行動が
自然とおこなわれています。

問題の矢印を書いた場合、
「節から上に戻るとき」は「節の右側を通る時」
「節から下りたとき」は「節の左側を通る時」とも言えます。

前者は深さ優先探索の帰りがけ順、後者は行きがけ順です。

ちなみにこのことを知っていれば科目Bサンプルの以下の問題は真面目にトレースしなくても解けます。

https://www.fe-siken.com/s/kakomon/sample/b9.html

左の子の再帰が終わったら節を出力しています。これは「左に行けるだけ行って行けなくなったら節を出力する」ので深さ優先探索の通りがけ順です。通りがけ順は一筆書きの矢印を書いて、節の下側を通るときに節を出力します。
節の下側を通った順番と答えの出力順が一致します。

jjon-comさんコメントありがとうございます。

起点は枝分かれの大元ということですね。

また下りる、上るという部分を含め問題の意味もやっとわかりました。
「節から上に戻るときに記号を書いていく」とは
矢印の経路を辿る際に記号を拾うか拾わないかという意味なんですね。

腹落ちできました。ありがとうございました。
※もし認識に間違いがあればご指摘いただければ嬉しいです。

まーぼさんコメントありがとうございます。

ご提示いただいた問題もやってみましたが解説でわからない部分が出てしまいました。

まず配列の添え字が0から始まらず1から始まるというのは問題文の
「配列 tree の要素番号1の要素は，節番号1の子の節番号から成る配列であり」
上記の部分で指定されている独自の仕様によるものという理解をしましたが
間違えていたらご指摘いただけたら嬉しいです。

そして解説の中で
「配列 tree[8] は要素を持たないので8を出力して終了し、呼出し元の order(4) の処理に戻る」
「order(4) は自身の節番号4を出力した後、2番目の要素（tree[4][2]）である節番号9を対象として order(9) を呼び出す」
という部分が理解できませんでした。

「配列 tree[8] は要素を持たないので8を出力して終了し」これはプログラムの１０行目の処理ですよね？ここからいきなり３行目に飛ぶのが理解できませんでした。どこかにそのような仕様が書かれているのでしょうか。

重ねての質問となり恐れ入ります。
もしお時間をいただけるようでしたらご教授いただけたら嬉しいです。

>「配列 tree[8] は要素を持たないので8を出力して終了し」これはプログラムの１０行目の処理ですよね？ここからいきなり３行目に飛ぶのが理解できませんでした。どこかにそのような仕様が書かれているのでしょうか。

関数内で他の関数を呼んだ場合、呼び出し元は他関数を呼び出した行で処理を停止して他関数が終了するのを待ちます。
※問題では同一のorder関数を呼び出していますが他関数と考えてOKです。

○関数Ａ
  関数Ｂの呼び出し
  ｘの出力

○関数Ｂ
  ｙの出力

この場合。
関数Ａ開始
  →関数Ｂ開始
    →関数Ｂ終了
  →関数Ａ再開
→関数Ａ終了の順で処理され
ｙｘと出力されます。

もう少しシンプルな問題で
https://www.ipa.go.jp/shiken/mondai-kaiotu/sg_fe/koukai/t6hhco0000003zx0-att/2023r05_fe_kamoku_b_qs.pdf
の2問目を解いてみると他関数の呼び出しは理解が深まると思います。

> 配列の添え字が0から始まらず1から始まるというのは問題文の
> （略）で指定されている独自の仕様によるものという理解をしました

二分木の添字を 0 からではなく 1 から始めるというのは，
例外的な独自仕様，というほどではなく，よく登場する例です。

親子間を移動する計算式が次のようになり，
添字を 0 から始める場合の計算式よりも分かりやすいので。

----
親ノードを指す添字が p ならば，その直下の
左の子ノードの添字は p*2 で，右の子ノードの添字は p*2+1

（左右を問わず）子ノードの添字が c ならば，その直上の
親ノードの添字は c/2（小数切捨て）
----

この掲示板では過去にこんな回答も寄せられています。

[4849] 科目Bサンプル問題9木構造の走査について
https://www.fe-siken.com/bbs/4849.html

擬似言語は基本的に配列の要素番号は1から始まると思っていいです。

https://www.ipa.go.jp/shiken/syllabus/ps6vr7000000i9dp-att/shiken_yougo_ver5_0.pdf

ITパスポートの擬似言語の記述形式の配列のところを見るとどちらも配列の要素番号が1から始まる例が出ているのでこちらが一般的なのだと思います。もちろん問題文の中でどこから始まるかは明示されると思います。

>配列 tree[8] は要素を持たないので8を出力して終了し、呼出し元の order(4) の処理に戻る

order(4)を呼び出すと

order(8)
4を出力
order(9)

という風になりますよね。order(8)は8を出力、order(9)は9を出力ですから

8を出力
4を出力
9を出力

となります。

order(4)がorder(8)を呼び出してorder(8)が終了してもorder(4)にはまだ処理が残っているわけですからその処理を実行しなければいけません。これが呼び出し元に戻るということです。

ちなみに
選択肢アは幅優先探索の出力順
イは深さ優先探索の行きがけ順
ウは深さ優先探索の通りがけ順
エは深さ優先探索の帰りがけ順
です。

ちょうど四択なので出題側としても出しやすい問題だと思います。

再帰関数は「簡単な問題に分割している」と考えてみてください。

いきなりorder(1)を考えるのは大変です。関数orderの引数で出力結果が簡単に分かるものはなんでしょうか？それはorderの引数が二分木の葉のノードの節番号のときです。葉のノードの節番号のときはその節番号を出力するだけですからとても簡単です。

では少し難しい問題order(4)を考えてみましょう。節番号4のノードは子を２つ持つので、

order(左の子の節番号）
4を出力
order(右の子の節番号）

となります。節番号は左の子が8、右の子が9ですから
order(4)は
order(8)
4を出力
order(9)
となります。
8と9は葉のノードの節番号ですから、一番簡単な問題でしたよね。ということは
order(4)は
8を出力
4を出力
9を出力となり、order(4)という問題も解けたことになります。

order(4)が解けたからまた少し難しいorder(2)を解いてみよう…と続きます。

電タックさんコメントありがとうございます。

＞問題では同一のorder関数を呼び出していますが他関数と考えてOKです。
再帰処理のところで混乱してしまいました。
他関数と考えるとスッキリ腹落ちできました。
ありがとうございます。

jjon-comさんコメントありがとうございます。

＞二分木の添字を 0 からではなく 1 から始めるというのは，
＞例外的な独自仕様，というほどではなく，よく登場する例です。

そうなんですね。ありがとうございます。勉強になりました。

＞[4849] 科目Bサンプル問題9木構造の走査について
＞https://www.fe-siken.com/bbs/4849.html

こちらリサーチ不足失礼致しました。
参考にさせていただきます。

まーぼさんコメントありがとうございます。

＞擬似言語は基本的に配列の要素番号は1から始まると思っていいです。

ありがとうございます。資料の方でも確認できました。

＞order(左の子の節番号）
＞4を出力
＞order(右の子の節番号）

こちらを提示していただいたことで
図とOrder関数がつながっていることが理解できました。

いただいた他の情報もありがとうございます。
まだ理解できておりませんが
少しずつ繰り返し考えてみます。

皆様たくさんの貴重な情報、お時間をいただきましてありがとうございます。
いただいた情報も学習してみます。
また不明点が出た際は書き込ませていただきますのでよろしくお願いいたします。