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