コンピュータ基礎演習 ースタックー

コンピュータ基礎演習
ー双方向リストー
岩井 儀雄
[email protected]
復習:リスト構造(1)

連結リストとは?

リストに含まれる各要素をつなぎ合わせた
もの
データ
データ
データ
DATA[0]
DATA[1]
DATA[2]
…
DATA[N]
データ
未使用
データ
…
データ
IDX[0]
IDX[1]
IDX[2]
…
IDX[N]
2
-1
N
…
EOD
復習:リスト構造(2)

構造体を用いたリストの表現
struct CELL {
struct CELL *next; /* 次のデータへのポインタ */
DATATYPE data;
/* 格納されるデータ */
};
復習:リスト構造(3)

連結リストの操作









要素の挿入 (insert)
要素の削除 (erase)
リストの連結(concatenate)
リストの分断 (split)
要素の探索 (find)
空リストの生成 (create)
要素数 (size)
先頭要素を見る (front)
最後尾要素を見る(tail)
復習:リスト構造(4)

連結リストの派生データ構造
連結リスト linked list
header
A
B
C
B
C
循環リスト circular list
header
A
後ろに移動し続ければ,先頭に戻れる
連結リストの問題点

各セルは次のセルへのポインタのみを持つ.


セル間の移動は1方向のみ
前後に自由に移動できるリスト構造

Doubly-linked list(双方向連結リスト,双方向
リスト,2重連結リスト)
双方向リスト
doubly-linked list
Doubly-linked list
header
A

C
各セルは2つのポインタを持つ



B
次のセルへのポインタ
前のセルへのポインタ
前後のセルへのポインタを持っているので前後に移動可能
双方向リスト
doubly-linked list(2)
リストの末尾も分かっていると tail() などの実装が容易
header
A
B
C
header を利用する
最後のセルが header を指すようにする
header の前のセルを指すポインタが最後のセルを指すようにする
双方向リスト
doubly-linked list(3)
空リストの表現
header
header の前後のポインタが header 自身を指す.
双方向リストの利点

利点



双方向リストでは,セルは前後のポインタを持っ
ているため,制約を受けず挿入,削除などの操作
が可能
一方,連結リストでは,一般に挿入,削除などの
操作に制約がある.
例)挿入の場合


連結リストでは,指定したセルの直後には挿入で
きるが直前には挿入できない
連結リストでは,直前のセルへのポインタを持つ
などの工夫が必要
双方向リストの欠点


連結リストと比べるとポインタを1つ余計に持
つ必要がある
取り扱うデータが小さい場合(例えば,整数),
2このポインタを持つため記憶容量に対して
オーバーヘッドが大きい(データサイズが大き
い場合は問題ではない)
トレードオフ問題
操作の自由さ⇔余分なデータサイズ
最近は,記憶容量が向上してきたので操作の自由さ(設計の自由さ)
が優先されつつある
双方向リストのセル(C言
語)
struct CELL {
struct CELL *prev; /* 前のデータへのポインタ */
struct CELL *next; /* 次のデータへのポインタ */
DATATYPE data;
/* 格納されるデータ */
};
空リスト(要素)生成の実装
(C言語)
struct CELL *create(DATATYPE data) {
struct CELL *p = (struct CELL*)malloc(sizeof(struct CELL));
p->prev = p;
p->next = p;
p->data = data;
return p;
}
prev
p
next
data
要素挿入の実装

指定された要素の次の位置に挿入


連結リストとほぼ同様
指定された要素の前の位置に挿入

前のセルに移動して,次の要素に挿入
B
header
A
C
要素挿入指定された要素の次
の位置に挿入
void insert( struct CELL *pos, struct CELL *val ) {
val->next = pos->next;
val->next->prev = val;
pos->next = val;
val->prev = pos;
}
val
pos
B
header
A
C
要素挿入指定された要素の次
の位置に挿入
void insert( struct CELL *pos, struct CELL *val ) {
val->next = pos->next;
val->next->prev = val;
pos->next = val;
val->prev = pos;
}
val
pos
B
header
A
C
要素挿入指定された要素の次
の位置に挿入
void insert( struct CELL *pos, struct CELL *val ) {
val->next = pos->next;
val->next->prev = val;
pos->next = val;
val->prev = pos;
}
val
pos
B
header
A
C
要素挿入指定された要素の次
の位置に挿入
void insert( struct CELL *pos, struct CELL *val ) {
val->next = pos->next;
val->next->prev = val;
pos->next = val;
val->prev = pos;
}
val
pos
B
header
A
C
要素挿入指定された要素の次
の位置に挿入
void insert( struct CELL *pos, struct CELL *val ) {
val->next = pos->next;
val->next->prev = val;
pos->next = val;
val->prev = pos;
}
val
pos
B
header
A
C
指定された要素の前の位置に
挿入

前のセルに移動して,次の要素に挿入
void insert_before( struct CELL *pos, struct CELL *val ) {
insert( pos->prev, val );
}
挿入ポイントを前のセルに移動
要素削除の実装

指定された要素の次を削除


連結リストとほぼ同様
指定された要素を削除する
指定された要素を削除する
struct CELL *erase( struct CELL *pos
pos->prev->next = pos->next;
pos->next->prev = pos->prev;
pos->prev = pos->next = pos;
return pos;
}
) {
pos
B
header
A
C
指定された要素を削除する
struct CELL *erase( struct CELL *pos
pos->prev->next = pos->next;
pos->next->prev = pos->prev;
pos->prev = pos->next = pos;
return pos;
}
) {
pos
B
header
A
C
指定された要素を削除する
struct CELL *erase( struct CELL *pos
pos->prev->next = pos->next;
pos->next->prev = pos->prev;
pos->prev = pos->next = pos;
return pos;
}
) {
pos
B
header
A
C
指定された要素を削除する
struct CELL *erase( struct CELL *pos
pos->prev->next = pos->next;
pos->next->prev = pos->prev;
pos->prev = pos->next = pos;
return pos;
}
) {
pos
B
header
A
C
指定された要素を削除する
struct CELL *erase( struct CELL *pos
pos->prev->next = pos->next;
pos->next->prev = pos->prev;
pos->prev = pos->next = pos;
return pos;
}
) {
B
header
A
C
tail の実装

リストの最後尾を返す


循環しているので header を見分ける必要
がある.
Header が分かれば,その前のセルへのポ
インタでよい.
struct CELL *tail( struct CELL *header ) {
return header->prev; /* 事前条件として header は
リストのヘッダであること */
}
多重リスト構造
multi link structure


セルに2つ以上のポインタを持たせ,
同時に複数のリストに所属できるよう
にしたデータ構造
例)大学での学生の成績を管理する表

2次元配列でも表現可能
short seiseki[MAX_GAKUSEI][MAX_KAMOKU];
seiseki[x][y]
学生番号 x の学生の課目 y の成績
未受講 -1
2次元配列を用いた場合
0
0
90
1
72
2
3
学 4
籍
番
号
1
2
3
4
83
90
52
53
25
23
44
55
課目数
….
例)成績管理表

学生総数2,000人,授業課目数400,平
均受講課目数 10
平均履修者数 → 2000x10/400 = 50名
配列の大きさ → 2000x400xsizeof(short) = 約1.6MB
データ量
→ 2000x 10xsizeof(short) = 約40KB
配列の使用効率 → 2.5%(無駄が多い)
疎な配列を効率良く表現できる → 多重リスト構造
多重リスト構造

基本アイデア

データのある要素をセルで表現し,それら
をポインタでつなぐ
上のセル
左のセル
DATA
下のセル
右のセル
コンピュータ基礎演習
ー木構造,二分木ー
岩井 儀雄
[email protected]
木構造

階層構造を表すためのデータ構造

一般世界


会社組織,家系図(祖父母,父母,兄弟),
本の構成(章,節,段落)
計算機の世界


階層化ディレクトリ(UNIX)
コンパイラによる構文解析
木 (tree)
レベル 0
レベル 1
木の深さ
根 root … 最上位ノード
節 node
レベル 2
レベル 3
レベル 4
枝 branch
葉 leaf…下位ノードがない
部分木 (subtree)
ある節を根とする木
部分木 (subtree)
ある節を根とする木
木に関する用語





親(parent)
子(child)
兄弟(sibling)
先祖(ancestor)
子孫(descendant)
このノードに注目
木に関する用語





親(parent)
子(child)
兄弟(sibling)
先祖(ancestor)
子孫(descendant)
このノードに注目
木に関する用語





親(parent)
子(child)
兄弟(sibling)
先祖(ancestor)
子孫(descendant)
自分自身は先祖であり
子孫である.
木の再帰的定義


単一の節はそれ自体が木である.この節はこの木の根でも
ある.
k個の木T1~Tkがあり,それぞれの根を節n1~nkとする.節n
を節n1~nkの親にすると節nを根とする新しい木Tが得られ
る.このとき,木T1~Tkは,木Tの部分木(subtree)であると
いう.部分木の根n1~nkは節nの子であるという.
n
単一の節からなる木
n1
n2
T1
T2
nk
…
Tk
部分木から新しい木を構成
節の順序

節の子には左から右に順序をつける
a
a
b
c
兄
弟
構造は同じだが
異なる木
c
b
兄
弟
ADT Tree





節の親を返す(parent)
節の最も左の子を返す(leftmost_child)
節の次の弟を返す(right_sibling)
根を返す(root)
節を作成する(create)
2分木(binary tree)

定義


空の木は2分木である
次のいずれかを満たす節のみからなる木は,
2分木である.




子を持たない
左の子を1つだけもつ
右の子を1つだけもつ
左の子と右の子を1つずつもつ
2分木
2分木では右の子と左の子を区別する
例)下の木は互いに異なる

a
b
d
a
c
b
a
b
c
d
右の子
d
左の子
普通の木(左右の子を区別しない) 2分木(左右の子を区別する)
c
左部分木と右部分木

左部分木


左の子を根とする木
右部分木

右の子を根とする木
左部分木
a
b
c
d
右部分木
配列を用いた2分木の実装
(C言語)

N番目の節の左の子のデータは,2N+1番目,
右の子のデータは2N+2番目に格納
#define MAXNODES 7
struct NODE { DATATYPE data; };
struct NODE[MAXNODES];
a
b
c
d
[0]
[1]
[2]
a
b
c
[3]
[4]
[5]
[6]
d
木の最大深さLとすると節の最大数は2L+1-1
配列を用いた2分木の実装
(C言語)(2)

左の子,右の子の添え字(インデックス)を格納
#define MAXNODES 7
struct NODE {
DATATYPE data;
int leftchild, rightchild; };
struct NODE[MAXNODES];
a
b
c
d
[0]
[1]
[2]
[3]
[4]
[5]
[6]
data
a
b
c
d
leftchild
1
0
0
0
0
0
0
rightchild
2
3
0
0
0
0
0
木の最大深さLとすると節の最大数は2L+1-1
配列による2分木の
実装の利点,欠点

利点


最大深さが分かっている場合,実装が簡単
欠点


最大深さが分からない場合,最大見積もり
深さを利用して設計するので,記憶装置の
使用効率が低下することがある
挿入削除を繰り返すと,空き領域の探索,
データの移動が伴うため,実行効率が悪い
構造体へのポインタを利用し
た2分木の実装(C言語)
struct NODE {
DATATYPE data;
struct NODE *leftchild; /* 左の子へのポインタ */
struct NODE *rightchild; /* 右の子へのポインタ */
struct NODE *parent;
/* 親へのポインタ
*/
};
struct NODE *parent
struct NODE
struct NODE *leftchild
struct NODE
struct NODE *rightchild
struct NODE
ADT Tree の実装(C言語)
struct NODE *parent( struct NODE *node ) {
return node->parent; /* ノードの親を返す */
}
struct NODE *leftmost_child(struct NODE *node) {
return node->leftchild; /* 左の子を返す */
}
struct NODE *right_sibling(struct NODE *node) {
if (node->parent != 0) { /* 親がいれば */
if (node->parent->leftchild != node) return NULL;
else return node->parent->rightchild; /* 右の子を返す */
} else return NULL;
}
struct NODE *root(struct NODE *node) {
struct NODE *p = node;
while (p->parent != NULL) p = p->parent; /* 親がいなくなるまで */
return p;
}
ADT Tree の実装(2)(C言
語)
/* 節を作成する */
struct NODE *create( DATATYPE val, struct NODE *par,
struct NODE *left, struct NODE *right ) {
struct NODE *p = (struct NODE *)malloc(sizeof(struct NODE));
p->data = val;
/* DATA の設定 */
p->parent = par; /* 親の登録 */
p->leftchild = left; left->parent = p;
/* 左の子の登録 */
p->rightchild = right; right->parent = p; /* 右の子の登録 */
}
/* 単一の節からなる木 T1, T2 の作成コード */
struct NODE *T1 = create( val, NULL, NULL, NULL );
struct NODE *T2 = create( val, NULL, NULL, NULL );
/* T1, T2 を部分木に持つ木 T の作成コード */
struct NODE *T = create( val, NULL, T1, T2 );
木のなぞり(traverse)

a


木の節を1つ残らず訪問
立ち寄った順に順序づけ可能
3種類のなぞりの方法

b
c


d
行きがけ順 pre-order
通りがけ順 in-order
帰りがけ順 post-order
行きがけ順

a
b
c
まず最初に節に立ち寄ってか
ら部分木をなぞる
1. 根に立ち寄る
2. 左部分木をなぞる
3. 右部分木をなぞる
a→b→d→c
d
行きがけ順

a
b
節
c
d
左部分木 右部分木
節aに立ち寄る
行きがけ順

a
節
b
節

c
d 右部分木
左部分木 右部分木
節aに立ち寄る
左部分木をなぞる
行きがけ順

a
節

節aに立ち寄る
左部分木をなぞる


節
b
c
節
d 右部分木
左部分木 右部分木

節bに立ち寄る
左部分木をなぞる(なし)
右部分木をなぞる
行きがけ順

a
節

節aに立ち寄る
左部分木をなぞる


節
b
c 節

節bに立ち寄る
左部分木をなぞる(なし)
右部分木をなぞる


節
d 右部分木


左部分木 右部分木
節dに立ち寄る
左部分木をなぞる(なし)
右部分木をなぞる(なし)
右部分木をなぞる
行きがけ順

a
節

節aに立ち寄る
左部分木をなぞる



節
b
節bに立ち寄る
左部分木をなぞる(なし)
右部分木をなぞる

c 節


節

d 右部分木
右部分木をなぞる


左部分木 右部分木
節dに立ち寄る
左部分木をなぞる(なし)
右部分木をなぞる(なし)

節cに立ち寄る
左部分木をなぞる(なし)
右部分木をなぞる(なし)
通りがけ順
a
b
c
1. 左部分木をなぞる
2. 根に立ち寄る
3. 右部分木をなぞる
b→d→a→c
d
通りがけ順

a
b
c
d
左部分木
右部分木
左部分木をなぞる
通りがけ順

左部分木をなぞる

a


b
c
d
右部分木
左部分木をなぞる(なし)
節bに立ち寄る
右部分木をなぞる
通りがけ順

左部分木をなぞる

a


左部分木をなぞる(なし)
節bに立ち寄る
右部分木をなぞる


b
c
d

左部分木をなぞる(なし)
節dに立ち寄る
右部分木をなぞる(なし)
通りがけ順

左部分木をなぞる

a


左部分木をなぞる(なし)
節bに立ち寄る
右部分木をなぞる


b
c


d
左部分木をなぞる(なし)
節dに立ち寄る
右部分木をなぞる(なし)
節aに立ち寄る
通りがけ順

左部分木をなぞる

a


左部分木をなぞる(なし)
節bに立ち寄る
右部分木をなぞる


b
c



d
左部分木をなぞる(なし)
節dに立ち寄る
右部分木をなぞる(なし)
節aに立ち寄る
右部分木をなぞる
通りがけ順

左部分木をなぞる

a


左部分木をなぞる(なし)
節bに立ち寄る
右部分木をなぞる


b
c



d
左部分木をなぞる(なし)
節dに立ち寄る
右部分木をなぞる(なし)
節aに立ち寄る
右部分木をなぞる



左部分木をなぞる(なし)
節cに立ち寄る
右部分木をなぞる(なし)
通りがけ順

左部分木をなぞる

a


左部分木をなぞる(なし)
節bに立ち寄る
右部分木をなぞる


b
c



d
節aに立ち寄る
右部分木をなぞる


b→d→a→c
左部分木をなぞる(なし)
節dに立ち寄る
右部分木をなぞる(なし)

左部分木をなぞる(なし)
節cに立ち寄る
右部分木をなぞる(なし)
帰りがけ順
a
b
c
1. 左部分木をなぞる
2. 右部分木をなぞる
3. 根に立ち寄る
d→b→c→a
d
帰りがけ順

a
b
c
d
左部分木
右部分木
左部分木をなぞる
帰りがけ順

左部分木をなぞる

a

b
c
d
左部分木をなぞる(なし)
右部分木をなぞる
帰りがけ順

左部分木をなぞる

a

左部分木をなぞる(なし)
右部分木をなぞる


b
c
d

左部分木をなぞる(なし)
右部分木をなぞる(なし)
節dに立ち寄る
帰りがけ順

左部分木をなぞる

a

左部分木をなぞる(なし)
右部分木をなぞる


b
c


d
左部分木をなぞる(なし)
右部分木をなぞる(なし)
節dに立ち寄る
節bに立ち寄る
帰りがけ順

左部分木をなぞる

a

左部分木をなぞる(なし)
右部分木をなぞる


b
c



d
左部分木をなぞる(なし)
右部分木をなぞる(なし)
節dに立ち寄る
節bに立ち寄る
右部分木をなぞる
帰りがけ順

左部分木をなぞる

a

左部分木をなぞる(なし)
右部分木をなぞる



b
c


節bに立ち寄る
右部分木をなぞる

d
左部分木をなぞる(なし)
右部分木をなぞる(なし)
節dに立ち寄る


左部分木をなぞる(なし)
右部分木をなぞる(なし)
節cに立ち寄る
帰りがけ順

左部分木をなぞる

a

左部分木をなぞる(なし)
右部分木をなぞる



b
c





節bに立ち寄る
右部分木をなぞる

d
左部分木をなぞる(なし)
右部分木をなぞる(なし)
節dに立ち寄る
左部分木をなぞる(なし)
右部分木をなぞる(なし)
節cに立ち寄る
節aに立ち寄る
帰りがけ順

左部分木をなぞる

a

左部分木をなぞる(なし)
右部分木をなぞる



b
c



d→b→c→a


節bに立ち寄る
右部分木をなぞる

d
左部分木をなぞる(なし)
右部分木をなぞる(なし)
節dに立ち寄る
左部分木をなぞる(なし)
右部分木をなぞる(なし)
節cに立ち寄る
節aに立ち寄る
木のなぞりの実装

再帰呼び出しのできる言語なら,手順
をそのままコーディングするだけで良
い.
2分木のなぞりの実装
(C言語)
void preorder(struct NODE *p) { /* 行きがけ順 */
if (p == NULL) return;
/* 立ち寄ったときの処理をいれる */
preorder( p->leftchild );
preorder( p->rightchild );
}
void inorder(struct NODE *p) { /* 通りがけ順 */
if (p == NULL) return;
inorder( p->leftchild );
/* 立ち寄ったときの処理をいれる */
inorder( p->rightchild );
}
void postorder(struct NODE *p) { /* 帰りがけ順 */
if (p == NULL) return;
postorder( p->leftchild );
postorder( p->rightchild );
/* 立ち寄ったときの処理をいれる */
}
コンピュータ基礎演習
ー二分探索木ー
岩井 儀雄
[email protected]
2分探索木
(binary search tree)


任意の節xで,左部分木TL(x)に含
まれる要素Nは節Xの要素N(x)よ
り小さい.
右部分木TR(x)に含まれる要素N
は節xの要素N(x)より大きい.
例) a < b < c <d
c
右部分木
左部分木
a
d
b

x, l, r l  T L(x), r  T R(x)  N(l) < N(x)  N(x) < N(r)
2分探索木の利点


順序 < が定義された集合を表現可
集合への追加,削除,探索などの操作
が O(log n) で可能
Strict Partial Order ‘<’

非反射律: irreflexivity

推移律:transivity

x x < x must be false

x,y,z x < y  y < z  x < z
上の2つの条件を満たす2項関係を
strict partial order (狭義半順序)という
同値 equivalence‘~’



反射律: reflexivity
x x ~ x
対称律: symmetry

x x ~ y  y ~ x
推移律: transitivity

x x ~ y  y ~ z  x ~ z
2分探索木の操作

探索 (search)


挿入 (insert)


指定された要素と等価な要素の位置を返す
指定された要素と等価な要素を2分探索木
の条件を満たすように挿入する
削除 (erase)

指定された要素と等価な要素を2分探索木
の条件を満たすように削除する
2分探索木の実装(C言語)
struct NODE {
DATATYPE data;
struct NODE *leftchild; /* 左の子へのポインタ */
struct NODE *rightchild; /* 右の子へのポインタ */
};
2分探索木で必要な演算
データ要素を順序づける演算 ‘<’ (strict partial order)
データが等価かどうかの演算 ‘~’ (equivalence)
int lessthan(DATATYPE a, DATATYPE b); /* 偽なら0,真なら!0 */
int equal(DATATYPE a, DATATYPE b);
/* 偽なら0,真なら!0 */
探索(search)の実装




struct
if
if
if
現在の節の要素と等しい→探索終わり
現在の節の要素より小さい→左部分木を探索
現在の節の要素より大きい→右部分木を探索
節がない→要素なし(NULLを返す)
NODE *search(DATATYPE data,struct NODE *node) {
(node == NULL) return NULL; /* データなし */
(equal(data,node->data)) return node; /* データ発見 */
(lessthan(data,node->data))
return search(data,node->leftchild); /* 左部分木を探索 */
else return search(data,node->rightchild); /* 右部分木を探索 */
}
挿入(insert)の実装(C言語)
struct NODE *create(DATATYPE data) { /* 新規ノード作成 */
struct NODE *p = (struct NODE *)malloc(sizeof(struct NODE));
node->data = data; node->leftchild = node->rightchild = NULL;
return p;
}
struct
if
if
if
NODE *insert(DATATYPE data,struct NODE *node) {
(node == NULL) return create(data);
/* 新規データ */
(equal(data,node->data)) return node; /* 既にデータあり */
(lessthan(data,node->data))
node->leftchild = insert( data, node->leftchild );
else node->rightchild = insert( data, node->rightchild );
return node;
}
削除(erase)の実装


削除すべき要素が葉ならば削除
削除すべき要素が内部節ならば問題


右部分木の最小値をその削除すべき要素と置き換える.
右部分木の最小値があった位置は1つ以下の子なので削除可
d
この節を単純に削除
すると木が壊れる
b
a
e
c
この節は葉であるから
単純に削除OK
削除(erase)の実装


削除すべき要素が葉ならば削除
削除すべき要素が内部節ならば問題


右部分木の最小値をその削除すべき要素と置き換える.
右部分木の最小値があった位置は1つ以下の子なので削除可
d
右部分木の最小値と入替
a
c
e
d
この節は葉であるから
単純に削除OK
右部分木の最小値をその削除すべき
要素と置き換える

2分探索木の条件

x, l, r l  T L(x), r  T R(x)  N(l) < N(x)  N(x) < N(r)
削除対象の節を x,右部分木TRの最小値を m とすると,
 < m < N(r), r  T (x)
N(x)
R

l, r l  T L(x), r  T R(x)  N(l) < m  m < N(r)
2分探索木の条件を壊さないことが分かる
木の最小値を削除しその値を
返す


右部分木の根を渡せば,右部分木の最小値を削除できる.
返り値で削除対象節の値を書き換える
data
min
最小値の左の子はいない
data
木の最小値を削除しその値を
返す


右部分木の根を渡せば,右部分木の最小値を削除できる.
返り値で削除対象節の値を書き換える
data
min
最小値の左の子はいない
data
木の最小値を削除しその値を
返す(C言語)
struct NODE *erasemin(struct NODE **node) {
if ((*node)->leftchild == NULL) {
struct NODE *ret = *node;
/* 返り値 */
*node = (*node)->rightchild; /* ポインタ変更 */
ret->rightchild = NULL;
return ret; /* 削除した節を返す */
} else
return erasemin( &((*node)->leftchild) );
}
要素の削除(C言語)
struct NODE *erase( DATATYPE data, struct NODE **node ) {
struct NODE *x = *node;
if (x == NULL) return NULL;
if (equal(data,x->data)) { /* 等価なデータ発見,削除 */
/* 子の有無を調査,1つだけならそのままつなぐ */
if (x->leftchild == NULL) *node = x->rightchild;
else if (x->rightchild == NULL) *node = x->leftchild;
else { /* 両側に子がある場合は erasemin を呼ぶ */
x = erasemin( &x->rightchild );
(*node)->data = x->data;
}
x->leftchild = x->rightchild = NULL;
return x;
} else if (lessthan(data,x->data))
return erase( data, &x->leftchild) ); /* 左部分木を探索 */
else
return erase( data, &x->rightchild) ); /* 右部分木を探索 */
}