1. No category

２分探 索木Ⅰ
２分探索木Ⅰ
０．目次
１．２分探索木とは
２．２分探索木の作成
３．２分探索木の走査
３．１
３．２
３．３
前走査
中走査
問題
問題１
問題２
後走査
４．２分探索木の表示
- 1 -
２分探 索木Ⅰ
１．２分探索木とは
木 はいくつかの節点と節点同士を結ぶ辺から構成される。
２ つ の 節 点 u,vが 直 接 辺 で 結 ば れ て い る と き 、 一 方 を 親 節 点 、 他 方 を 子 節 点 と い
う。ある節点の親節点は高々１つであり、子節点は０個以上である。節点の中に
は、親節点をもたない節点がただ１つあり、根という。また、子節点をもたない
節点を葉という。木は、つぎのように定義される。
（１）ひとつの節点は、木である。
（ ２ ） vが 節 点 で 、 T １ ,T ２ ,･･･,T ｋ が 木 で 、 そ れ ぞ れ の 木 の 根 が v １ ,v ２ ,･･･,v ｋ
と す る 。 こ の と き 、 vを v １ ,v ２ ,･･･,v ｋ の 親 と す る の は 、 木 で あ る 。
節 点 v １ ,v ２ ,･･･,v ｋ は 節 点 vの 子 と 呼 ば れ る 。
v
v１
v２
・・・
T１
vｋ
Tｋ
T２
２ 分 木は、どの節点も高々２個の子節点をもつ。２個の子節点の内、左に
書かれる子節点を根とする部分木を左部分木、右に書かれる子節点を根とする
部分木を右部分木という。
Ａ
Ｂ
Ｄ
Ｃ
Ｅ
Ｆ
Ｇ
Ｈ
節点：Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ，Ｇ，Ｈ
（Ａは根でもある）
辺：ＡＢ，ＡＣ，ＢＤ，ＢＥ，ＣＦ，ＦＧ，ＦＨ
（ＸＹのとき、Ｘが親、Ｙが子を意味する）
２分木の節点に集合Ｓの要素を割り当てる。各節点において、割り当てられた
要素の大きさが、左部分木のどの節点の要素よりも大きく、右部分木のどの節点
の要素よりも小さいとき、２ 分 探 索 木 という。
- 2 -
２分探 索木Ⅰ
２．２分探索木の作成
空の２分探索木から始める。挿入する要素と節点の要素を比較し、前者が小さ
い場合、左部分木に追加し、前者が大きい場合、右部分木に追加していく。
●手順
9個 の デ ー タ (55,33,11,99,44,77,22,66,88)で 手 順 を 示 す 。
（１）
（２）
55
（３）
55
55
33
33
11
（４）
（５）
55
33
99
55
33
11
99
11
（６）
（７）
55
33
11
44
55
99
44
33
77
99
11
44
77
22
（８）
（９）
55
33
11
55
99
44
22
33
77
11
66
99
44
22
77
66
88
２ 分 探 索 木 を 表 現 す る た め に 、 デ ー タ を 保 存 す る 変 数 info、 左 部 分 木 を 指 す ポ
イ ン タ left、 右 部 分 木 を 指 す ポ イ ン タ rightを も つ 構 造 体 を 用 意 す る 。 根 を 指 す
ポ イ ン タ 変 数 を rootと す る 。 ポ イ ン タ 変 数 rootは 空 の 同 じ 構 造 体 を 指 す 。
このようにすると、プログラムが簡潔になる。
root
Ｂ
NULL
Ａ
Ｄ
Ｂ
Ｃ
Ｅ
NULL
Ａ
NULL
- 3 -
Ｄ
NULL
Ｃ
NULL
NULL
Ｅ
NULL
２分探 索木Ⅰ
● プ ロ グ ラ ム ・ 非 再 帰 版 （ bt211.c）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
/* << bt211.c >> */
/* ２ 分 探 索 木 の 作 成 。 */
#include <stdio.h>
#include <stdlib.h>
struct NODE {
int info;
/* 節 点 が も つ デ ー タ 。 */
struct NODE *left; /* 左 の 子 節 点 を 指 す ポ イ ン タ 。 */
struct NODE *right; /* 右 の 子 節 点 を 指 す ポ イ ン タ 。 */
};
struct NODE *mktree();
int main() {
struct NODE *root;
/* ２ 分 探 索 木 の 作 成 。 */
root = mktree();
}
/* ２ 分 探 索 木 の 作 成 。 */
struct NODE *mktree() {
int data;
struct NODE *p,
/*
*q,
/*
*r,
/*
*root; /*
現 節 点 を 指 す ポ イ ン タ 変 数 。 */
現 節 点 の 親 節 点 を 指 す ポ イ ン タ 変 数 。 */
作 業 用 ポ イ ン タ 変 数 。 */
根 を 指 す ポ イ ン タ 変 数 。 */
/* 根 を 指 す ポ イ ン タ 変 数 と 空 の 構 造 体 の 作 成 。 */
root = (struct NODE *)malloc(sizeof(struct NODE));
root->left = NULL;
root->right = NULL;
while( 1 ) {
/* デ ー タ の 読 み 込 み 。 */
scanf("%d",&data);
if( data <= 0 ) { break; }
r = (struct NODE *)malloc(sizeof(struct NODE));
r->info = data;
r->left = NULL;
r->right = NULL;
root->info = data; /* ２ 分 探 索 木 に デ ー タ を 追 加 す る と き 、
空の構造体の左部分木に追加できるように
root->info=data と し て お く 。 */
/* 初 期 設 定 。 */
p = root->left;
q = root;
/* 追 加 す る 場 所 を 探 す 。 */
while( p != NULL ) {
/* 重 複 デ ー タ は 追 加 し な い 。 */
if( data == p->info ) { goto next; }
- 4 -
２分探 索木Ⅰ
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
/* デ ー タ dataが 現 在 の 節 点 の デ ー タ (p->info)以 下 の と き
左 部 分 木 へ 、 大 き い と き 右 部 分 木 へ 移 動 す る 。 */
q = p;
if( data <= p->info ) {
p = p->left;
} else {
p = p->right;
}
}
/* デ ー タ の 追 加 。 */
if( data <= q->info ) {
/* 左 部 分 木 と し て 追 加 。 */
q->left = r;
} else {
/* 右 部 分 木 と し て 追 加 。 */
q->right = r;
}
next:;
}
return root;
}
- 5 -
２分探 索木Ⅰ
３．２分探索木の走査
２分探索木の辺を反時計回りに（赤い線に沿って）なぞっていくと２分探索木
のすべての節点を訪問できる。
Ａ
Ｂ
Ｄ
Ｃ
Ｅ
Ｆ
Ｇ
Ｈ
２分探索木のすべての節点をたどる方法として、前走査、中走査、後走査の
３通り考えられる。
●前走査：まず、親節点を訪問する。
つぎに、左部分木のすべての節点を訪問する。
最後に、右部分木のすべての節点を訪問する。
①Ａ
②Ｂ
③Ｄ
⑤Ｃ
④Ｅ
⑥Ｆ
⑦Ｇ
訪問順：ＡＢＤＥＣＦＧＨ
- 6 -
⑧Ｈ
２分探 索木Ⅰ
●中走査：まず、左部分木のすべての節点を訪問する。
つぎに、親節点を訪問する。
最後に、右部分木のすべての節点を訪問する。
④Ａ
②Ｂ
①Ｄ
⑤Ｃ
③Ｅ
⑦Ｆ
⑥Ｇ
⑧Ｈ
訪問順：ＤＢＥＡＣＧＦＨ
●後走査：まず、左部分木のすべての節点を訪問する。
つぎに、右部分木のすべての節点を訪問する。
最後に、親節点を訪問する。
⑧Ａ
③Ｂ
①Ｄ
⑦Ｃ
②Ｅ
⑥Ｆ
④Ｇ
訪問順：ＤＥＢＧＨＦＣＡ
- 7 -
⑤Ｈ
２分探 索木Ⅰ
３．１
前走査
● プ ロ グ ラ ム ・ 再 帰 版 (bt311.c）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/* << bt311.c >> */
/* ２ 分 探 索 木 の 走 査 （ 前 走 査 ）。 */
#include <stdio.h>
#include <stdlib.h>
struct NODE {
int info;
/* 節 点 が も つ デ ー タ 。 */
struct NODE *left; /* 左 の 子 節 点 を 指 す ポ イ ン タ 。 */
struct NODE *right; /* 右 の 子 節 点 を 指 す ポ イ ン タ 。 */
};
void preorder(struct NODE *p);
struct NODE *mktree();
int main() {
struct NODE *root;
/* ２ 分 探 索 木 の 作 成 。 */
root = mktree();
/* 前 走 査 。 */
preorder(root->left); printf("\n");
}
/* 前 走 査 。 */
void preorder(struct NODE *p) {
if( p == NULL ) { return; }
printf(" %d",p->info);
preorder(p->left);
preorder(p->right);
}
- 8 -
２分探 索木Ⅰ
実行結果
% cc bt311.c
% ./a.out
55 22 88 11 33 77 99 44 66 0
55 22 11 33 44 88 77 66 99
① 55
② 22
③ 11
⑥ 88
④ 33
⑦ 77
⑤ 44 ⑧ 66
①から⑨の順に訪問する。
% ./a.out
11 22 33 44 55 66 77 88 99 0
11 22 33 44 55 66 77 88 99
% ./a.out
99 88 77 66 55 44 33 22 11 0
99 88 77 66 55 44 33 22 11
% ./a.out
22 11 55 44 33 99 88 77 66 0
22 11 55 44 33 99 88 77 66
- 9 -
⑨ 99
２分探 索木Ⅰ
３．２
中走査
● プ ロ グ ラ ム ・ 再 帰 版 （ bt321.c）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/* << bt321.c >> */
/* ２ 分 探 索 木 の 走 査 （ 中 走 査 ）。 */
#include <stdio.h>
#include <stdlib.h>
struct NODE {
int info;
/* 節 点 が も つ デ ー タ 。 */
struct NODE *left; /* 左 の 子 節 点 を 指 す ポ イ ン タ 。 */
struct NODE *right; /* 右 の 子 節 点 を 指 す ポ イ ン タ 。 */
};
void inorder(struct NODE *p);
struct NODE *mktree();
int main() {
struct NODE *root;
/* ２ 分 探 索 木 の 作 成 。 */
root = mktree();
/* 中 走 査 。 */
inorder(root->left); printf("\n");
}
/* 中 走 査 。 */
void inorder(struct NODE *p) {
if( p == NULL ) { return; }
inorder(p->left);
printf(" %d",p->info);
inorder(p->right);
}
- 10 -
２分探 索木Ⅰ
実行結果
% cc bt321.c
% ./a.out
55 22 88 11 33 77 99 44 66 0
11 22 33 44 55 66 77 88 99
⑤ 55
② 22
① 11
⑧ 88
③ 33
⑦ 77
④ 44 ⑥ 66
①から⑨の順に訪問する。
% ./a.out
11 22 33 44 55 66 77 88 99 0
11 22 33 44 55 66 77 88 99
% ./a.out
99 88 77 66 55 44 33 22 11 0
11 22 33 44 55 66 77 88 99
% ./a.out
22 11 55 44 33 99 88 77 66 0
11 22 33 44 55 66 77 88 99
- 11 -
⑨ 99
２分探 索木Ⅰ
３．３
問題１
問題
後走査
● プ ロ グ ラ ム ・ 再 帰 版 （ bt331.c）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/* << bt331.c >> */
/* ２ 分 探 索 木 の 走 査 （ 後 走 査 ）。 */
#include <stdio.h>
#include <stdlib.h>
struct NODE {
int info;
/* 節 点 が も つ デ ー タ 。 */
struct NODE *left; /* 左 の 子 節 点 を 指 す ポ イ ン タ 。 */
struct NODE *right; /* 右 の 子 節 点 を 指 す ポ イ ン タ 。 */
};
void postorder(struct NODE *p);
struct NODE *mktree();
int main() {
struct NODE *root;
/* ２ 分 探 索 木 の 作 成 。 */
root = mktree();
/* 後 走 査 。 */
postorder(①
); printf("\n");
}
/* 後 走 査 。 */
void postorder(struct NODE *p) {
if( p == ②
) { return; }
postorder(③
);
postorder(④
);
printf(" %d",p->info);
}
- 12 -
２分探 索木Ⅰ
実行結果
% cc bt331.c
% ./a.out
55 22 88 11 33 77 99 44 66 0
11 44 33 22 66 77 99 88 55
⑨ 55
22 ④
① 11
⑧ 88
③ 33
⑥ 77
② 44 ⑤ 66
①から⑨の順に訪問する。
% ./a.out
11 22 33 44 55 66 77 88 99 0
99 88 77 66 55 44 33 22 11
% ./a.out
99 88 77 66 55 44 33 22 11 0
11 22 33 44 55 66 77 88 99
% ./a.out
22 11 55 44 33 99 88 77 66 0
11 33 44 66 77 88 99 55 22
- 13 -
⑦ 99
２分探 索木Ⅰ
問題２
読み込んだデータから２分探索木を構成し、前走査、中走査、後走査でたどる
順を示せ。
例
入 力 デ ー タ ： 55 22 88 11 33 77 99 44 66
前 走 査 ： 55 22 11 33 44 88 77 66 99
中 走 査 ： 11 22 33 44 55 66 77 88 99
後 走 査 ： 11 44 33 22 66 77 99 88 55
（ １ ） 入 力 デ ー タ ： 44 11 33 77 66 55 99 88 22
前走査
⑤
中走査
⑥
後走査
⑦
- 14 -
２分探 索木Ⅰ
４．２分探索木の表示
２ 分 探 索 木 を Excelの グ ラ フ 機 能 を 使 っ て 表 示 す る 。
まず、各節点に座標を割り当てる。節点が交わらないように下図のように座標
を 決 め る 。 根 の 座 標 は (0,0)と す る 。
● (0,0)
● (-1/2,-1)
● (-3/4,-2)
● (1/2,-1)
● (-1/4,-2)
● (1/4,-2)
● (3/4,-2)
す な わ ち 、２ 分 探 索 木 の 深 さ が 一 つ 増 え る ご と に 、節 点 間 の 幅 を 1/2倍 に す る 。
こ の プ ロ グ ラ ム で 、 節 点 の 座 標 を 求 め る 。 た だ し 、 Excelの グ ラ フ 機 能 （ 散 布
図）を使って表示するため、前走査で節点を通過するたびに座標を出力する。
● プ ロ グ ラ ム ・ 再 帰 版 （ bt411.c）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/* << bt411.c >> */
/* ２ 分 探 索 木 の 走 査 （ 前 走 査 ）。 */
/* 節 点 の 座 標 を 出 力 す る 。 */
#include <stdio.h>
#include <stdlib.h>
struct NODE {
int info;
/* 節 点 が も つ デ ー タ 。 */
struct NODE *left; /* 左 の 子 節 点 を 指 す ポ イ ン タ 。 */
struct NODE *right; /* 右 の 子 節 点 を 指 す ポ イ ン タ 。 */
};
float width; /* 幅 。 */
void preorder(struct NODE *p, float v, float h);
struct NODE *mktree();
int main() {
struct NODE *root;
/* ２ 分 探 索 木 の 作 成 。 */
root = mktree();
/* 初 期 設 定 。 */
width = 1;
/* 前 走 査 。 */
preorder(root->left,0,0);
printf("\n");
- 15 -
２分探 索木Ⅰ
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
}
/* 前 走 査 に 従 っ て 、 節 点 の x座 標 v,y座 標 hを 出 力 す る 。 */
void preorder(struct NODE *p, float v, float h) {
if( p == NULL ) { return; }
/* 座 標 (v,-h)の 出 力 。 */
printf("%8.5f,%8.5f\n",v,-h);
width = width/2;
preorder(p->left,v-width,h+1);
/* 座 標 (v,-h)の 出 力 。 */
printf("%8.5f,%8.5f\n",v,-h);
preorder(p->right,v+width,h+1);
width = width*2;
/* 座 標 (v,-h)の 出 力 。 */
printf("%8.5f,%8.5f\n",v,-h);
}
実行結果
% cc bt411.c
% ./a.out
44 22 11 33 66 55 77 0
0.00000,-0.00000
-0.50000,-1.00000
-0.75000,-2.00000
-0.75000,-2.00000
-0.75000,-2.00000
-0.50000,-1.00000
-0.25000,-2.00000
-0.25000,-2.00000
-0.25000,-2.00000
-0.50000,-1.00000
0.00000,-0.00000
0.50000,-1.00000
0.25000,-2.00000
0.25000,-2.00000
0.25000,-2.00000
0.50000,-1.00000
0.75000,-2.00000
0.75000,-2.00000
0.75000,-2.00000
0.50000,-1.00000
0.00000,-0.00000
- 16 -
２分探 索木Ⅰ
●２分探索木の表示
① 節 点 の 座 標 を csvフ ァ イ ル （ 拡 張 子 を csvと す る ） に し て 保 存 す る 。
② Excelを 起 動 し 、 csvフ ァ イ ル を 読 み 込 む 。
③グラフ機能（散布図）使ってグラフを表示する。
余分な座標軸等は削除する。
x座標
0
-0.5
-0.75
-0.75
-0.75
-0.5
-0.25
-0.25
-0.25
-0.5
0
0.5
0.25
0.25
0.25
0.5
0.75
0.75
0.75
0.5
0
ｙ座標
0
-1
-2
-2
-2
-1
-2
-2
-2
-1
0
-1
-2
-2
-2
-1
-2
-2
-2
-1
0
44
22
66
11
33
- 17 -
55
77