ad-3. 二分木と走査
1
金子邦彦
C 言語によるアルゴリズムとデータ構造)(全6回)
URL: https://www.kkaneko.jp/pro/ad/index.html
3-1. 二分木と走査
2
二分木とは
レコードを次の3つで構成
要素を格納するセル
左部分木を指すポインタを格納するセル
右部分木を指すポインタを格納するセル
3
左部分木
(root)
右部分木
二分木の走査法
二分木の走査には次の種類がある
先行順 (pre-order)
中間順 (in-order)
後行順 (post-order)
先行順 (pre-order)
根ノード,左部分木,右部分木の順
A
BC
DEF G
D, B, E, A, F, C, G
の順に処理を行う
中間順 (in-order)
左部分木,根ノード,右部分木の順
A
BC
DEF G
D, B, E, A, F, C, G
の順に処理を行う
左部分木を辿る
②根を辿る
③右部分木を辿る
後行順 (post-order)
左部分木,右部分木,根ノードの順
A
BC
DEF G
D, E, B, F, G, C, A
の順に処理を行う
3-2. 実習
8
実習の指示 資料:1017
次のことを理解しマスターする
二分木の作成
9
ここで作成する木
10
+
1*
23
実習
ウェブブラウザを起動する
C Tutor を使いたいので,次の URL を開く
http://www.pythontutor.com/
Internet Explorer でうまく動かない場合がある
うまく動かないときは Google Chrome を試してください
途中でServer Busy・・・」というメッセージが出る
とがある.
混雑している.少し(数秒から数十秒)待つと自動で表示
が変わる(変わらない場合には,操作をもう一度行ってみ
る)
日本語モードはない.英語で使う 11
C Tutor」をクリック
12
13
C (gcc4.8, C11)」になっている
エディタ
実行のためのボタン
最初から main メソッドの
ひな形が入っている
双方向リストの作成
次のプログラムを使う
14
次ページに続く
15
②「Visualize Execution」をクリック.
Last」をクリック.
結果を確認する.
Edit this code」をクリックして戻る
16
実行結果
17
レコード
レコード
レコード
レコード
レコード
実習の指示
資料:1827
次のことを理解しマスターする
先行順 (pre-order)
中間順 (in-order)
後行順 (post-order)
18
先行順 (pre-order)
プログラムを次のように書き換えなさい
19
次ページに続く
20
実行し,結果を確認しなさい
21
中間順 (in-order)
プログラムを次のように書き換えなさい
22
次ページに続く
23
実行し,結果を確認しなさい
24
後行順 (post-order)
プログラムを次のように書き換えなさい
25
次ページに続く
26
実行し,結果を確認しなさい
27