Subsections
2 ツリー構造とは
2.1 ツリー構造とは
同じような複数のデータを表す場合，配列やリスト，スタック，キューのようなデータ構 造を学習してきた．これらのデータ構造で教科書のFig.6-1のような，階層をもつデータ の集まりを表すことは，困難である．このように階層構造をもつデータを処理するときに 威力を発揮するのがツリー構造である．ツリーとは，tree(木)のことである．ツリー構造の例として，教科書では生き物やWindosのファイルシステムのツリー構造が書 かれている．諸君が学習で使っているUNIXのファイルシステムは，図 1のようになっている．
- [練習1]
- ツリー構造をしたデータは，他に何があるか?
![\includegraphics[keepaspectratio,scale=0.8]{figure/UNIX_file.eps}](img3.png)
2.2 ツリー構造を実現する方法
教科書[1]に書いてあるように，ツリー構造のデータ構造はリス トを少し変えるだけで実現できる．そこで，まずはリストのおさらいをしてから，ツリー 構造を実現する方法を示す．2.2.1 単方向リスト
リストは，図2のようなデータ構造である．一つの要素(element)はデータ とつながりを表すポインターからなり，構造体で表すことができる．リストは，各々の要 素のつながりしか分からないので，最初の要素を示すポインターが必要である．このよう なリストを使う場合，次のような宣言を行えば良い．
/* --- 単方向リストを表す構造体 ---*/
typedef struct tag_list_element{
struct tag_list_element *next;
int data;
}list_element;
list_element *top; /* 先頭を示すポインター */
![\includegraphics[keepaspectratio,scale=0.8]{figure/list.eps}](img4.png)
配列に比べ，リストはデータの追加と削除が容易である．データの追加と削除の方法は， 教科書 [1]のFig.6-3(p.163)に示してあるとおりである．
- [練習1]
- 配列のデータの追加と削除の方法を述べよ．
リストを使って，実際にデータの追加と削除を行うプログラムをリスト2 に示す．このプログラムの動作は以下の通りである．
- 入力した整数は，リストの形で記憶される．
- エレメント作成の後，直ちに，データが昇順に並ぶように，接続のポインター(next)を設定する．
- 負の整数で，データ入力が終了する．
- 入力されたデータを昇順に表示する．
- データを削除する．
- 残っているデータを昇順に表示する．
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <memory.h>
4
5 /* --- 単方向リストを表す構造体 ---*/
6 typedef struct tag_list_element{
7 struct tag_list_element *next;
8 int data;
9 }list_element;
10
11
12 list_element *top; /* 先頭を示すポインター */
13
14 /*======================================================*/
15 /* リストを作る関数 */
16 /*======================================================*/
17 list_element *creat_new_element(int num){
18 list_element *new_list;
19
20 new_list=(list_element *)malloc(sizeof(list_element));
21 new_list->data = num;
22 new_list->next = NULL;
23
24 return new_list;
25 }
26
27 /*======================================================*/
28 /* リストを挿入する関数 */
29 /*======================================================*/
30 void insert_list(int num){
31
32 list_element *new,*loop;
33
34 /*--- データがひとつもないとき ---*/
35 if(top==NULL){
36 top = creat_new_element(num);
37 return;
38 }
39
40 /*--- 先頭のデータよりも小さいとき ---*/
41 if(num < top->data){
42 new = creat_new_element(num);
43 new -> next = top;
44 top = new;
45 return;
46 }
47
48 loop=top;
49 while(1){
50 if(loop->next==NULL){
51 loop->next = creat_new_element(num);
52 break;
53 }
54
55 if(num<loop->next->data){
56 new=creat_new_element(num);
57 new->next=loop->next;
58 loop->next=new;
59 break;
60 }
61 loop=loop->next;
62 }
63 }
64
65
66 /*======================================================*/
67 /* リストを削除する関数 */
68 /*======================================================*/
69 void delete_list(int num){
70 list_element *loop;
71
72 if(top->data==num){
73 top=top->next;
74 return;
75 }
76
77 loop=top;
78
79 while(loop->next != NULL){
80 if(loop->next->data == num){
81 loop->next=loop->next->next;
82 return;
83 }
84 loop=loop->next;
85 }
86 }
87
88 /*======================================================*/
89 /* リストを表示する関数 */
90 /*======================================================*/
91 void print_data(){
92 list_element *elm;
93
94 elm=top;
95
96 while(elm!=NULL){
97 printf("%d ",elm->data);
98 elm=elm->next;
99 }
100
101 printf("\n");
102
103 }
104
105
106 /*======================================================*/
107 /* メイン関数 */
108 /*======================================================*/
109 int main(){
110 int in;
111
112 top=NULL;
113
114 /*--- キーボード入力とリストへの追加 ----*/
115 printf("正の整数のデータを追加します(負:入力終了)．\n");
116 do{
117 scanf("%d",&in);
118 if(in<0)break;
119 insert_list(in);
120 }while(1);
121
122
123 print_data();
124
125 /*--- リストからでーたの削除 ----*/
126 printf("整数のデータを削除します(負:入力終了)．\n");
127 do{
128 scanf("%d",&in);
129 if(in<0)break;
130 delete_list(in);
131 }while(1);
132
133 print_data();
134
135 return 0;
136 }
2.3 ツリー構造
ツリー構造は，図3のように表すことができる．一つのノードは，リスト同 様，構造体で表すことができる．構造体は，データと子を示すポインターを持つことにな る．リストでは先頭の要素を表すポインターが必要であったが，ツリー構造ではルートを 示すポインターが必要である．構造体の宣言は，以下のようにすればよいだろう．
/* --- ツリーのノードを表す構造体 ---*/
typedef struct tag_tree_node{
struct tag_tree_node *ko_1, *ko_2, *ko_3;
int data;
}tree_node;
tree_node *root; /* ルートを示すポインター */
このツリーを実現させるための構造体には，ひとつ問題がある．子の数が3と決められて いる．また，多くのデータでは子の数が不定であることが多い．そのため，必要なポイン ターの数が分からない．この解決方法については，次週の講義で説明する．ここでは，リ ストとほとんど同じ構造体で，ツリー構造が実現できることを理解して欲しい．
![\includegraphics[keepaspectratio,scale=0.8]{figure/tree.eps}](img5.png)
2.4 ツリー構造の各部の名称
ツリー構造にはいろいろ名称があり，それを表1と図 4に示す．なぜ，図3のようなデータ構造をツリー 構造と呼ぶか?．それは，この図を反対にしてみるのである．すると，根が一番下にきて， 枝や葉が上にあることが分かるであろう．まさに，木である．
![\includegraphics[keepaspectratio,scale=0.8]{figure/tree_structure.eps}](img6.png)
2.5 ツリー構造の要素の追加と削除
教科書 [1]のp.166-167の通り．ホームページ: Yamamoto's laboratory
著者: 山本昌志 Yamamoto Masashi
2006-01-16