データ構造とアルゴリズム論

データ構造とアルゴリズム論
第9章 木構造
平成17年12月20日
森田 彦
基礎課題提出状況(12/13)
基礎課題提出状況(12/13) 平均=39.9 [全課題42題]
120
8章
100
度数(人数)
80
60
9名 このままでは危険!
40
20
4章以前
5章
6章
7章
0
0~24
25~31
32~37
提出数
38~39
40~42
8章の課題学習中→76.5%
応用課題提出状況(12/13)
応用課題提出状況(12/13) 平均16.0 全課題30題
35
度数(人数)
30
25
20
15
10
5
0
0~5
①30題:8名
6~10
11~15 16~20
提出数
②29題:5名
21~25
⑤28題:5名
26~30
木構造とは?
 連結リストは順序(のみ)を表現するデー
タ構造
 木構造は、階層構造を表現できるデータ
構造
木構造の表現
 階層を表現できるデータ構造
根
部分木
2
4
①~⑦:ノード
1
5
3
6
7
葉
<メリット>
データ間の階層関係を表現できる。
検索時に威力を発揮する。
学習のポイント
 木構造の作成の仕方(プログラミング
による)を学習する。
 木構造中のデータ走査の仕方を学
習する。
ここでは基礎を学習
幅広い応用→市販のテキストで
本章の学習の流れ
 9-1節 木構造とは?
木構造の定義(概念)の学習
 9-2節 プログラムによる2分木の表現
*2分木の作成→【基礎課題9-1】で理解。
*NodeクラスからTreeクラスへの発展→【基礎課題9-2】
で理解。
 9-3節 木のなぞり方(データ走査の仕方)
*行きがけ順、通りがけ順、帰りがけ順の3つの走査方
法→【応用課題9-A】で理解。
*【応用課題9-B】でプログラミング
 9-4節 2分木の応用
【応用課題9-C】で理解度チェック
第2回目テストのアナウンス
 日時:12/27 13:15~14:15 (13:10までに
着席しておいて下さい)
 実施形態:ペーパーテスト形式(テスト中
はPCを使用できません)
 参照等:テキスト、プリント、自作ノート参
照可
 出題範囲:第9章まで
 アドバイス:暗記ではなく、処理の流れを
“理解する”事に重点を置いて下さい。
学生成績簿の場合
学籍番号 氏名 データ構造とアルゴリズム論成績 ・・・
S04001 花形満 A ・・・
S04002 轟次郎 C ・・・
S04003 早川みどり D ・・・
S04004 伊達直人 B ・・・
・・・
学籍番号順に連なる連結リスト(あるいは配列)
として表現できる。
Windowsフォルダ構成
ローカルディスク(C:)
Documents and Settings
Administrator
Cookies
hiko
My
Documents
ProgJava
Drivers
VIDEO
MODEM
NETWORK
HXFSETUP.
EXE
ONBOARD
デスクトップ
マイピクチャ
木構造:データの検索が容易になる。