HOME»基本情報技術者平成15年秋期»午前問12
基本情報技術者平成15年秋期 午前問12
問12
2分木の走査の方法には，その順序によって次の三つがある。
- 前順：節点，左部分木，右部分木の順に走査する。
- 間順：左部分木，節点，右部分木の順に走査する。
- 後順：左部分木，右部分木，節点の順に走査する。
- abchidefjgk
- abechidfjgk
- hcibdajfegk
- hicdbjfkgea
分類
テクノロジ系 » アルゴリズムとプログラミング » データ構造
正解
ア
解説
前順走査なので、節点 → 左部分木 → 右部分木の順に見ていきます。
まず、節点とその子に着目します。
a → b → e
したがって、出力順は
a → b（を節点とする部分木） → e（を節点とする部分木）
なので、はじめにaが出力されます。
次に、左側のbを節点とする部分木は、
b → c → d
したがって、出力順は
b → c（を節点とする部分木） → d
なので、bが出力されます。
次に、cを節点とする部分木は、
c → h → i
なので、cが出力されます。ここまでに出力されたのは
a → b → c
したがって、正解は「ア」です。
※前順走査ではまず左部分木の節点をすべて走査し終わってから、右部分木の走査に移ります。
まず、節点とその子に着目します。
a → b → e
したがって、出力順は
a → b（を節点とする部分木） → e（を節点とする部分木）
なので、はじめにaが出力されます。
次に、左側のbを節点とする部分木は、
b → c → d
したがって、出力順は
b → c（を節点とする部分木） → d
なので、bが出力されます。
次に、cを節点とする部分木は、
c → h → i
なので、cが出力されます。ここまでに出力されたのは
a → b → c
したがって、正解は「ア」です。
※前順走査ではまず左部分木の節点をすべて走査し終わってから、右部分木の走査に移ります。