平成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
したがって、正解は「ア」です。
※前順走査ではまず左部分木の節点をすべて走査し終わってから、右部分木の走査に移ります。
広告