【基本情報】コード掲載！科目B問9「木構造を走査するプログラム」について解説します

基本情報の午後試験はプログラム問題です．

科目B問題を解けるようになるにはプログラムを元に自分でコードを書いてみるのが1番良いでしょう．

今回は科目B問9「木構造を走査するプログラム」の解説とそのコードを紹介します．
プログラムを元にPythonで書き直しました．

Pythonで書いてみたので是非手元で実行してみてください

サンプル問題科目B 問9「木構造を走査するプログラム」
まとめ

サンプル問題科目B 問9「木構造を走査するプログラム」

問題文は以下のとおりです．
木構造に関する問題ですね．

サンプル問題[科目B]問9 木構造を走査するプログラム

プログラムをPythonで書き直す

問9に掲載されているプログラムを元にPythonで書き直しました．

tree = [
    [2,3],
    [4,5],
    [6,7],
    [8,9],
    [10,11],
    [12,13],
    [14],
    [],
    [],
    [],
    [],
    [],
    [],
    []
    ]

def order(n: int):
    # 要素数が2と等しいとき
    if (len(tree[n-1]) == 2):
        order(tree[n-1][0])
        print(n, end=', ') # 改行を「, 」に変換する
        order(tree[n-1][1])
    # 要素数が1と等しいとき
    elif (len(tree[n-1]) == 1):
        order(tree[n-1][0])
        print(n, end=', ')
    else:
        print(n, end=', ')
        
order(1)

プログラムを実行すると「8, 4, 9, 2, 10, 5, 11, 1, 12, 6, 13, 3, 14, 7」と表示されました．

この結果と一致する選択肢は「ウ」です．
答えも「ウ」なのでプログラムに誤りはなさそうですね．

ポイントを確認します．

ポイント1 木構造について

木構造について確認しましょう．

木構造は要素が親と子の関係を持つ階層的なデータ構造です．
各要素はノード（Node）と呼ばれます．

ノードはその特徴でそれぞれ呼び名が変わります．

ルートノード（Root Node）：木構造の1番上のノード．
親ノード（Parent Node）：他のノードに対して上位に位置し，直接的にノードへのリンクを持つノード
子ノード（Child Node）：親ノードから分岐するノード．親ノードとリンクしている．
葉ノード（Leaf Node）：子ノードを持たないノード，最下位に位置する．

ポイント2 トレースする

order関数は再帰関数なので処理が複雑です．
頭の中で処理を追うと混乱してしまうので書き出すのが良いでしょう．

def order(n: int): # n=1
    # 要素数が2と等しいとき
    if (len(tree[n-1]) == 2): # tree[0] = [2, 3]
        order(tree[n-1][0]) # tree[0][0] = 2

def order(n: int): # n=2
    # 要素数が2と等しいとき
    if (len(tree[n-1]) == 2): # tree[1] = [4, 5]
        order(tree[n-1][0]) # tree[1][0] = 4

def order(n: int): # n=4
    # 要素数が2と等しいとき
    if (len(tree[n-1]) == 2): # tree[3] = [8, 9]
        order(tree[n-1][0]) # tree[3][0] = 8

def order(n: int): # n=8 要素番号8は空のリストなので
    # 要素数が2と等しいとき
    if (len(tree[n-1]) == 2):
        order(tree[n-1][0])
        order(tree[n-1][1])
    # 要素数が1と等しいとき
    elif (len(tree[n-1]) == 1):
        order(tree[n-1][0])
        print(n, end=', ')
    # 要素数が0のとき
    else:
        print(n, end=', ') # 8が出力される

以上から1番初めに出力される値は8です．

n=8のときに8が出力されると分かりました．
処理はn=4に戻ります．

def order(n: int): # n=4
    # 要素数が2と等しいとき
    if (len(tree[n-1]) == 2): # tree[3] = [8, 9]
        order(tree[n-1][0]) # tree[3][0] = 8 が1番初めに出力される
        print(n) # n=4 次に出力される数字

order(tree[n-1][0])の結果8が出力されたので処理は次に進みます．
後の処理でprint(n)をしているので4が出力されます．

よって答えは「8, 4…」と続く「ウ」になります．