二分探索木と二分探索の違い

質問

高校のときにCOBOLを用いた二分探索を習いました。

今大学でコンピューター科学を勉強しています。予習をしていたら二分探索木が出てきました。

添付画像のような二分木があるとき、a～jの各ノードに１～１０の整数のどの整数が入るか。
という問題ですが、ちんぷんかんぷんです。

二分探索木というのは、検索で用いる二分探索と同じ考えなのでしょうか。
もし、同じなら、１～１０の中央値の５がルートになりますよね。

このような問題の簡単な求め方があれば教えてください。お願いいたします。

回答No.3

jjon-com · ベストアンサー

節に格納される10種の数値を昇順に並べておく。
１，２，３，４，５，６，７，８，９，10

根ａに着目。
ａより小さい要素は４つ（ｂ，ｄ，ｅ，ｇ 順不同）で，
ａより大きい要素は５つ（ｃ，ｆ，ｈ，ｉ，ｊ 順不同）

よって，根ａ＝５
（小さい要素の群）根（大きい要素の群）
（１，２，３，４）５（６，７，８，９，10）

--------
（１，２，３，４）に対して，節ｂに着目。
ｂより小さい要素は２つ（ｄ，ｇ 順不同）で，
ｂより大きい要素は１つ（ｅ）

よって，節ｂ＝３
（小さい）節（大きい）
（１，２）３（４）
よって，節ｅ＝４

--------
（１，２）に対して，節ｄに着目。
ｄより大きい要素は１つ（ｇ）

よって，節ｄ＝１，節ｇ＝２

--------
（６，７，８，９，10）に対して，節ｃに着目。
ｃより小さい要素は４つ（ｆ，ｈ，ｉ，ｊ 順不同）

よって，節ｃ＝10
（小さい要素の群）節
（６，７，８，９）10

--------
（６，７，８，９）に対して，節ｆに着目。
ｆより小さい要素は１つ（ｈ）
ｆより大きい要素は２つ（ｉ，ｊ 順不同）

よって，節ｆ＝７
（小）節（大）
（６）７（８，９）
よって，節ｈ＝６

--------
（８，９）に対して，節ｉに着目。
ｉより小さい要素は１つ（ｊ）

よって，節ｉ＝９
（小）節
（８）９
よって，節ｊ＝８

回答No.2

bunjii

>添付画像のような二分木があるとき、a～jの各ノードに１～１０の整数のどの整数が入るか。
参考URLに整数値の違う例示がありますので、そこから類推してください。

参考URL：

http://ufcpp.net/study/algorithm/col_tree.html

回答No.1

asuncion

二分木の探索方法には、次の3パターンがあります。
１）行きがけ
２）通りがけ
３）帰りがけ

添付画像の二分木を各パターンで探索する際に各ノードをどういう順序で通るかは、調べてみてください。

＞添付画像のような二分木があるとき、a～jの各ノードに１～１０の整数のどの整数が入るか。

この問題を解くためのポイントは、「二分木を通りがけで探索すると、データの昇順(または降順)に探索する」です。