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