二分探索木のデータ構造と、C言語による生成・探索・挿入
の実装。
【学習内容の構成】
1. リストの併合：tail ポインタを用いた2つのリストの結合
操作
2. 二分探索木の構造：節点(node)と枝(branch)による木構
造、左部分木・右部分木の再帰的構造
3. C言語での表現：構造体 BTNode による節点の表現と
new_node 関数による生成
4. 探索と挿入：探索キーと節点値の比較による左右への分
岐、再帰関数による要素挿入
5. 二分木の走査法：先行順(pre-order)、中間順(in-order)、
後行順(post-order)
• 前提：C言語の構造体、ポインタ、再帰関数
• 意義：整列可能なデータ集合に対する効率的な探索アルゴ
リズムの理解
2
例題１．リストの併合
• ２つのリストを併合するプログラムを動かしてみ
る
•3
NULL
NULL
head1
tail1
tail1 があると，リストの併合に便利
head2
tail2
NULL
head1
tail1
•4
#include "stdio.h"
#include <math.h>
struct data_list {
int data;
struct data_list *next;
};
void print_list(struct data_list *p)
{
struct data_list *x;
if ( p == NULL ) {
return;
}
printf( "%d", p->data );
x = p->next;
while( x != NULL ) {
printf( ", %d", x->data );
x = x-> next;
}
printf( "¥n" );
}
struct data_list *new_list(int x)
{
struct data_list *c = new(struct data_list);
c->data = x;
c->next = NULL;
return c;
}
void insert_list(struct data_list *p, int x)
{
struct data_list *c = new(struct data_list);
c->data = p->data;
c->next = p->next;
p->data = x;
p->next = c;
}
int _tmain()
{
int ch;
struct data_list *head1;
struct data_list *tail1;
struct data_list *head2;
struct data_list *tail2;
head1 = new_list( 6789 );
insert_list( head1, 45 );
tail1 = head1->next; // ２個目の要素を作った時点で head1->next と tail1 が等しい
insert_list( head1, 123 );
head2 = new_list( 789 );
insert_list( head2, 56 );
tail2 = head2->next; // ２個目の要素を作った時点で head2->next と tail2 が等しい
insert_list( head2, 1234 );
printf( "併合前¥n" );
print_list( head1 );
print_list( head2 );
//
tail1->next = head2;
tail1 = tail2;
printf( "併合後¥n" );
print_list( head1 );
printf( "Enter キーを1,2回押してください. プログラムを終了します¥n");
ch = getchar();
ch = getchar();
return 0;
}
tail1->next = head2;
tail1 = tail2;
•5
実行結果の例
二分探索木 (binary search tree)
• 整列可能な任意個数のデータ集合に対し、効率良
い探索（二分探索）を行うためのデータ構造
• 整列前：35 46 21 13 61 40 69
• 整列後（昇順）：13 21 35 40 46 61 69
• 節点から出る枝が高々２本の木構造（二分木）を
作り、各節点にデータを置く
•6
二分探索木の構造
• 節点(node)と枝(branch)
• 枝はデータ間の（親子）関係を表す
• 節点に入る（親からの）枝は１本
• 節点から出ていく（子への）枝は０または１または２
本
•7
親
子
節点(node)
枝(branch)
子
子
親
二分探索木の構造（つづき）
• 根(root)： 親を持たない節点
• 葉(leaf)： 子を持たない節点
• 部分木(subtree)： 任意の節点から下のすべての枝
と節点
•8
部分木(subtree)
根(root)
葉(leaf)
二分探索木の再帰的構造
• 左部分木、右部分木も二分木をなす
• 親節点に対する処理が、子節点に対する処理に帰
着されることが多い
（例）探索において，子へ移動し，親での処理と
同様の処理を繰り返す
→再帰関数を用いて自然に表現できる。
•9
右部分木左部分木
右部分木左部分木
二分探索木の各ノードを
C言語の構造体で表現
•10
// ２分木のノード
struct BTNode
{
BTNode *left;
BTNode *right;
int value;
};
left right
value
left right
value
left right
value
１個の
構造体
int value の部分は，格納
すべきデータに応じて変わる
二分探索木の節点(node) の
生成関数 new_node
•11
#include "stdio.h"
#include <math.h>
struct BTNode
{
BTNode *left;
BTNode *right;
int value;
};
struct BTNode *new_node(int x, struct BTNode *y, struct BTNode *z)
{
struct BTNode *w = new BTNode();
w->value = x;
w->left = y;
w->right = z;
return w;
}
int _tmain()
{
int ch;
BTNode *root;
root = new_node( 100, NULL, NULL );
printf( "Enter キーを1,2回押してください. プログラムを終了します¥n");
ch = getchar();
ch = getchar();
return 0;
}
メンバ value, left, right に値をセット
例題２，３，４で使用
例題２．二分探索木の生成
• データの配置のしかた
• 左側のすべての子は親より小さく
• 右側のすべての子は親より大きく
•12
35
21
13 40 61
46
69
new_node を７回呼び出して，節点を7個作る
•13
#include "stdio.h"
#include <math.h>
struct BTNode
{
BTNode *left;
BTNode *right;
int value;
};
void print_data( struct BTNode *root )
{
if ( root->left != NULL ) {
print_data( root->left );
}
printf( "%d¥n", root->value );
if ( root->right != NULL ) {
print_data( root->right );
}
}
struct BTNode *new_node(int x, struct BTNode *y, struct BTNode *z)
{
struct BTNode *w = new BTNode();
w->value = x;
w->left = y;
w->right = z;
return w;
}
int _tmain()
{
int ch;
BTNode *root;
root = new_node( 35,
new_node( 21,
new_node(13, NULL, NULL),
NULL),
new_node( 46,
new_node(40, NULL, NULL),
new_node(61,
NULL,
new_node(69, NULL, NULL))));
print_data( root );
printf( "Enter キーを1,2回押してください. プログラムを終了します¥n");
ch = getchar();
ch = getchar();
return 0;
}
２分木の生成
in-order で要素を表示
（in-order については後述）
•14
実行結果の例
• in-order での表示
•15
void print_data( struct BTNode *root )
{
if ( root->left != NULL ) {
print_data( root->left );
}
printf( "%d¥n", root->value );
if ( root->right != NULL ) {
print_data( root->right );
}
}
35
21
13 40 61
46
69
最初に左部分木
次に自分（節点）
最後に右部分木
例題３．二分探索木における探索
• 指定された要素が存在するかを探す
４０ → 有り
４１ → 無し
•16
35
21
13 40 61
46
69
二分探索木における探索
• 根(root)から始める。
• 探索キーの値と，各節点のデータを比較し目標と
なるデータを探す
• 探索キーよりも節点のデータが小さいときは，右側の
子に進む
• 探索キーよりも節点のデータが大きいときは，左側の
子に進む
•17
探索の例
（例） 節点40を探す場合
• 根の値(35)と，探索キー(40)を比較
• 探索キーの方が大きいので，右側の子節点へ移る
• 次に移った節点の値(46)と探索キー(40)を比較し
• 探索キーの方が小さいので，左の子節点へ移る
• 次に移った節点(40)が，目標の節点である
•18
35
21
13 40 61
46
69
•19
#include "stdio.h"
#include <math.h>
struct BTNode
{
BTNode *left;
BTNode *right;
int value;
};
struct BTNode *find_node(int x, struct BTNode *root)
{
BTNode *node;
node = root;
while( ( node != NULL ) && ( x != node->value ) ) {
if ( x < node-> value ) {
node = node->left;
}
else {
node = node->right;
}
}
return node;
}
struct BTNode *new_node(int x, struct BTNode *y, struct BTNode *z)
{
struct BTNode *w = new BTNode();
w->value = x;
w->left = y;
w->right = z;
return w;
}
int _tmain()
{
int ch;
BTNode *root;
BTNode *y;
root = new_node( 35,
new_node( 21,
new_node(13, NULL, NULL),
NULL),
new_node( 46,
new_node(40, NULL, NULL),
new_node(61,
NULL,
new_node(69, NULL, NULL))));
y = find_node( 40, root );
if ( y == NULL ) {
printf( "40 は無し¥n" );
}
else {
printf( "40 は有り¥n" );
}
printf( "Enter キーを1,2回押してください. プログラムを終了します¥n");
ch = getchar();
ch = getchar();
return 0;
}
２分木の生成
探索（見つからなければ NULL
を返す）
探索を行う関数
•20
struct BTNode *find_node(int x, struct BTNode *root)
{
BTNode *node;
node = root;
while( ( node != NULL ) && ( x != node->value ) ) {
if ( x < node-> value ) {
node = node->left;
}
else {
node = node->right;
}
}
return node;
}
•21
実行結果の例
例題４．二分探索木への挿入
• 要素の挿入を行う関数を作る
35 46 21 13 61 40 69 を挿入すると，
例題１と同じ二分探索木ができる
•22
35
21
13 40 61
46
69
二分探索木への挿入
• 二分探索木に新たなデータを挿入する
• 挿入すべき位置を探す
• （find_nodeと同じ要領）
• 新たな節点を生成
• 挿入位置として見つかった節点において、新たな節点
をポイントするようにポインタを書き換える
•23
•24
#include "stdio.h"
#include <math.h>
struct BTNode
{
BTNode *left;
BTNode *right;
int value;
};
void print_data( struct BTNode *root )
{
if ( root->left != NULL ) {
print_data( root->left );
}
printf( "%d¥n", root->value );
if ( root->right != NULL ) {
print_data( root->right );
}
}
struct BTNode *new_node(int x, struct BTNode *y, struct BTNode *z)
{
struct BTNode *w = new BTNode();
w->value = x;
w->left = y;
w->right = z;
return w;
}
struct BTNode *insert_node(struct BTNode *node, int x)
{
if ( node == NULL ) {
return new_node(x, NULL, NULL);
}
else if ( x < node->value ) {
node->left = insert_node(node->left, x);
return node;
}
else if ( x > node->value ) {
node->right = insert_node(node->right, x);
return node;
}
else {
return node;
}
}
int _tmain()
{
int ch;
BTNode *root;
root = new_node( 35, NULL, NULL );
insert_node( root, 46 );
insert_node( root, 21 );
insert_node( root, 13 );
insert_node( root, 61 );
insert_node( root, 40 );
insert_node( root, 69 );
print_data( root );
printf( "Enter キーを1,2回押してください. プログラムを終了します¥n");
ch = getchar();
ch = getchar();
return 0;
}
最初は，節点を１個含む二分探索木を作り，
その後，残りの要素を挿入する
挿入を行う関数
•25
struct BTNode *insert_node(struct BTNode *node, int x)
{
if ( node == NULL ) {
return new_node(x, NULL, NULL);
}
else if ( x < node->value ) {
node->left = insert_node(node->left, x);
return node;
}
else if ( x > node->value ) {
node->right = insert_node(node->right, x);
return node;
}
else {
return node;
}
}
•26
実行結果の例
二分木とは
レコードを次の３つで構成
• 要素を格納するセル
• 左部分木を指すポインタを格納するセル
• 右部分木を指すポインタを格納するセル
27
左部分木
根(root)
右部分木
二分木の走査法
二分木の走査には次の種類がある
• 先行順 (pre-order)
• 中間順 (in-order)
• 後行順 (post-order)
28
先行順 (pre-order)
• 根ノード，左部分木，右部分木の順
A
B
C
D
E
F G
A, B, D, E, C, F, G
の順に処理を行う
29
中間順 (in-order)
• 左部分木，根ノード，右部分木の順
A
B
C
D
E
F G
D, B, E, A, F, C, G
の順に処理を行う
①左部分木を辿る
②根を辿る
③右部分木を辿る
30
後行順 (post-order)
• 左部分木，右部分木，根ノードの順
A
B
C
D
E
F G
D, E, B, F, G, C, A
の順に処理を行う
31
