基本情報技術者試験の科目BをJavaとPythonのプログラムで考える　No.19

基本情報技術者試験で出題されるプログラム言語が疑似言語に変更されましたね。合格に向けて学習を進めるにおいては、やはり普段から使っているプログラム言語に置き換えて考えてみたいですよね。
このサイトでは、IPA情報処理推進機構で公開されている科目Bのプログラミングの問題を中心に、疑似言語をJavaとPythonのコードに置き換えて解説していきます。
１日１問の解説を発信していく予定です。基本情報技術者試験の合格を目指されている方のお役に立てれば幸いです。

---

基本情報技術者試験 科目 B サンプル問題（2022年12月公開）

https://www.ipa.go.jp/shiken/syllabus/henkou/2022/ssf7ph000000h5tb-att/fe_kamoku_b_set_sample_qs.pdf

問９　二分木

二分木とは
木の形をしたデータの整理方法の一つです。

木には根っこがあって、そこから枝が伸びていきますよね。
二分木では、1つの「親」の部分（これを「根」と呼びます）が、
最大で2つまでの「子ども」を持つことができます。
この「親」と「子ども」の関係が、木が上から下に広がるように続いていきます。
「親」と「子ども」のそれぞれを「節」と呼びます。

このプログラムは、処理対象となっている「節」が有する「子」の数によって３つの処理に分岐します。

① その「節」が２つの「子」を持つ場合の処理
　　・配列の要素の１つ目の節番号（左の子）を探索する
　　・自身の節番号を出力する
　　・配列の要素の２つ目の節番号（右の子）を探索する

② その「節」が１つの「子」を持つ場合の処理
　　・配列の要素の１つ目の節番号（左の子）を探索する
　　・自身の節番号を出力する

③ その「節」が「子」を持たない場合の処理
　　・自身の節番号を出力する

節番号1を「根」とすると、次のように処理が進みます。

order(1)　左へ
order(2)    左へ
order(4)　左へ
order(8)    8出力、親に戻る

order(4)    4を出力、右へ
order(9)    9出力、親に戻る、親に戻る

order(2)    2を出力、右へ
order(5)　 左へ
order(10)  10を出力、親に戻る

order(5)     5を出力、右へ
order(11)   11を出力、親に戻る、親に戻る、親に戻る

order(1)　  1を出力、右へ
order(3)      左へ
order(6)      左へ
order(12)    12出力、親に戻る

order(6)      6を出力、右へ
order(13)   13を出力、親に戻る、親に戻る
　
order(3)      3を出力、右へ
order(7)     左へ
order(14)    14を出力、親に戻る

order(7)      7 を出力 、親に戻る、親に戻る
order(1)

　

１．Javaのコードで考えてみよう

package kamokuB;

public class R4_Sample09 {
	static int[][] tree = { {}, { 0, 2, 3 }, { 0, 4, 5 }, { 0, 6, 7 }, { 0, 8, 9 },
			{ 0, 10, 11 }, { 0, 12, 13 }, { 0, 14 }, {}, {}, {},
			{}, {}, {}, {} }; // {}は要素数0の配列

    static void order(int n){
    	//① その「節」が２つの「子」を持つ場合の処理
        if(tree[n].length-1 == 2){
            order(tree[n][1]);
            System.out.print(n + " ");
            order(tree[n][2]);
        //② その「節」が２つの「子」を持つ場合の処理    
        }else if(tree[n].length-1 == 1){
            order(tree[n][1]);   
            System.out.print(n + " ");
        //③ その「節」が「子」を持たない場合の処理
        } else
            System.out.print(n + " ");
    }

    public static void main(String[] args) {
		order(1);
	}
}

２．Pythonのコードで考えてみよう

# 2022年12月公開問題9

tree = [[], [0, 2, 3], [0, 4, 5], [0, 6, 7], [0, 8, 9],
       [0, 10, 11], [0, 12, 13], [0, 14], [], [], [],
       [], [], [], []]  # []は要素数0のリスト

def order(n):
    #① その「節」が２つの「子」を持つ場合の処理
    if len(tree[n]) - 1 == 2:
        order(tree[n][1])
        print(n, end=" ")
        order(tree[n][2])
    #② その「節」が２つの「子」を持つ場合の処理
    elif len(tree[n]) - 1 == 1:
        order(tree[n][1])
        print(n, end=" ")
    #③ その「節」が「子」を持たない場合の処理
    else:
        print(n, end=" ")

order(1)

いかがでしょうか。
二分木もよく使用されるデータ構造の一つですので、しっかりと理解しておきましょう。