アルゴリズムとデータ構造
補足資料12-3
「サンプルプログラムtreeop1.c」
横浜国立大学
理工学部
数物・電子情報系学科
富井尚志
struct tree *tree( int n )
{
struct tree *newtree;
int x, nl, nr;
if ( n==0 )
return( NULL );
else {
nl = n/2; nr = n-nl-1;
/* 完全バランス木では左右の部分木の節点数の差は高々1 */
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
}
ノード数nの完全バランス木を構成し、
その木へのポインタを返す関数 tree(n)
int a[] = { 1, 2, 3, 4, 5, 6, EOD};
root
int main(void)
{
struct tree *root;
root = tree( 6 );
ノード数6
の完全バラ
ンス木
略
}
呼出1: tree(6)
呼出1 が完了して、
処理が戻ってきた時（実行後）のイメージ
struct tree *tree( int n )
呼出1: mainからn=6 で呼び出された
{
struct tree *newtree;
int x, nl, nr;
n=6 で呼び出し
if ( n==0 )
return( NULL );
else {
→ 左部分木のノード数 nl = 3
右部分木のノード数 nr = 6-3-1 = 2
この木の根: 1個
nl = n/2; nr = n-nl-1;
/* 完全バランス木では左右の部分木の節点数の差は高々1 */
newtree
1
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
}
呼出2: tree(3)
ノード数
3の完全
バランス
木
呼出2 が完了して、
処理が戻ってきた時（実行後）のイメージ
tree(6) : 呼出1
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
1
tree(6) : 呼出1
tree(3) : 呼出2
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
1
tree(6) : 呼出1
tree(3) : 呼出2
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
1
2
tree(6) : 呼出1
tree(3) : 呼出2
tree(1) : 呼出3
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
1
2
tree(6) : 呼出1
tree(3) : 呼出2
tree(1) : 呼出3
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
1
2
3
tree(6) : 呼出1
tree(3) : 呼出2
tree(1) : 呼出3
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
tree(0) : 呼出4
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
1
2
3
tree(6) : 呼出1
tree(3) : 呼出2
tree(1) : 呼出3
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
tree(0) : 呼出4
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
1
2
3
tree(6) : 呼出1
tree(3) : 呼出2
tree(1) : 呼出3
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
tree(0) : 呼出4
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
1
2
3
NU
LL
tree(6) : 呼出1
tree(3) : 呼出2
tree(1) : 呼出3
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
tree(0) : 呼出5
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
1
2
3
NU
LL
tree(6) : 呼出1
tree(3) : 呼出2
tree(1) : 呼出3
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
tree(0) : 呼出5
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
1
2
3
NU
LL
tree(6) : 呼出1
tree(3) : 呼出2
tree(1) : 呼出3
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
tree(0) : 呼出5
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
1
2
3
NU
LL
NU
LL
tree(6) : 呼出1
tree(3) : 呼出2
tree(1) : 呼出3
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
1
2
3
NU
LL
NU
LL
tree(6) : 呼出1
tree(3) : 呼出2
tree(1) : 呼出3
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
1
2
3
NU
LL
NU
LL
tree(6) : 呼出1
tree(3) : 呼出2
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
1
2
3
NU
LL
NU
LL
tree(6) : 呼出1
tree(3) : 呼出2
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
tree(1) : 呼出6
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
1
2
3
NU
LL
NU
LL
tree(6) : 呼出1
tree(3) : 呼出2
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
tree(1) : 呼出6
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
1
2
3
NU
LL
4
NU
LL
tree(6) : 呼出1
tree(3) : 呼出2
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
tree(1) : 呼出6
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
1
tree(0) : 呼出7
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
2
3
NU
LL
4
NU
LL
NU
LL
tree(6) : 呼出1
tree(3) : 呼出2
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
tree(1) : 呼出6
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
1
tree(0) : 呼出8
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
2
3
NU
LL
4
NU
LL
NU
LL
NU
LL
tree(6) : 呼出1
tree(3) : 呼出2
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
tree(1) : 呼出6
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
1
2
3
NU
LL
4
NU
LL
NU
LL
NU
LL
tree(6) : 呼出1
tree(3) : 呼出2
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
1
2
3
NU
LL
4
NU
LL
NU
LL
NU
LL
tree(6) : 呼出1
tree(3) : 呼出2
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
1
2
3
NU
LL
4
NU
LL
NU
LL
NU
LL
tree(6) : 呼出1
tree(3) : 呼出2
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
1
2
3
NU
LL
4
NU
LL
NU
LL
NU
LL
tree(6) : 呼出1
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
1
2
3
NU
LL
4
NU
LL
NU
LL
NU
LL
tree(6) : 呼出1
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
tree(2) : 呼出9
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
1
2
3
NU
LL
4
NU
LL
NU
LL
NU
LL
tree(6) : 呼出1
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
tree(2) : 呼出9
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
1
2
5
3
NU
LL
4
NU
LL
NU
LL
NU
LL
tree(6) : 呼出1
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
tree(2) : 呼出9
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
tree(1) : 呼出10
1
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
2
5
3
NU
LL
4
NU
LL
NU
LL
NU
LL
tree(6) : 呼出1
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
tree(2) : 呼出9
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
tree(1) : 呼出10
1
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
2
5
3
NU
LL
4
NU
LL
NU
LL
6
NU
LL
tree(6) : 呼出1
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
tree(2) : 呼出9
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
tree(1) : 呼出10
1
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
2
5
3
NU
LL
4
NU
LL
NU
LL
6
NU
LL
NU
LL
tree(6) : 呼出1
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
tree(2) : 呼出9
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
tree(1) : 呼出10
1
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
2
5
3
NU
LL
4
NU
LL
NU
LL
6
NU
LL
NU
LL
NU
LL
tree(6) : 呼出1
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
tree(2) : 呼出9
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
tree(1) : 呼出10
1
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
2
5
3
NU
LL
4
NU
LL
NU
LL
6
NU
LL
NU
LL
NU
LL
tree(6) : 呼出1
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
tree(2) : 呼出9
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
1
2
5
3
NU
LL
4
NU
LL
NU
LL
6
NU
LL
NU
LL
NU
LL
tree(6) : 呼出1
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
tree(2) : 呼出9
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
1
2
5
NU
LL
3
NU
LL
4
NU
LL
NU
LL
6
NU
LL
NU
LL
NU
LL
tree(6) : 呼出1
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
tree(2) : 呼出9
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
1
2
5
NU
LL
3
NU
LL
4
NU
LL
NU
LL
6
NU
LL
NU
LL
NU
LL
tree(6) : 呼出1
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
1
2
5
NU
LL
3
NU
LL
4
NU
LL
NU
LL
6
NU
LL
NU
LL
NU
LL
tree(6) : 呼出1
if ( n==0 )
newtree
return( NULL );
else {
nl = n/2; nr = n-nl-1;
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
1
2
5
NU
LL
3
NU
LL
4
NU
LL
NU
LL
6
NU
LL
NU
LL
NU
LL
root
1
2
5
NU
LL
3
NU
LL
4
NU
LL
NU
LL
6
NU
LL
NU
LL
NU
LL
int a[] = { 1, 2, 3, 4, 5, 6, EOD};
root
int main(void)
{
struct tree *root;
root = tree( 6 );
ノード数6
の完全バラ
ンス木
略
}
呼出1: tree(6)
呼出1 が完了して、
処理が戻ってきた時（実行後）のイメージ
int a[] = { 1, 2, 3, 4, 5, 6, EOD};
root
int main(void)
{
struct tree *root;
1
2
root = tree( 6 );
NU
LL
略
}
5
3
NU
LL
4
NU
LL
NU
LL
6
NU
LL
NU
LL
NU
LL
詳細トレース
int a[] = { 1, 2, 3, 4, 5, 6, EOD};
root
int main(void)
{
struct tree *root;
root = tree( 6 );
ノード数6
の完全バラ
ンス木
略
}
呼出1: tree(6)
呼出1 が完了して、
処理が戻ってきた時（実行後）のイメージ
struct tree *tree( int n )
呼出1: mainからn=6 で呼び出された
{
struct tree *newtree;
int x, nl, nr;
n=6 で呼び出し
if ( n==0 )
return( NULL );
else {
→ 左部分木のノード数 nl = 3
右部分木のノード数 nr = 6-3-1 = 2
この木の根: 1個
nl = n/2; nr = n-nl-1;
/* 完全バランス木では左右の部分木の節点数の差は高々1 */
newtree
1
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
}
呼出2: tree(3)
ノード数
3の完全
バランス
木
呼出2 が完了して、
処理が戻ってきた時（実行後）のイメージ
struct tree *tree( int n )
呼出2: 呼出1からn=3
{
struct tree *newtree;
int x, nl, nr;
n=3 で呼び出し
if ( n==0 )
return( NULL );
else {
で呼び出された
→ 左部分木のノード数 nl = 1
右部分木のノード数 nr = 3-1-1 = 1
この木の根: 1個
nl = n/2; nr = n-nl-1;
/* 完全バランス木では左右の部分木の節点数の差は高々1 */
newtree
2
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
}
呼出3: tree(1)
ノード数
1の完全
バランス
木
呼出3 が完了して、
処理が戻ってきた時（実行後）のイメージ
struct tree *tree( int n )
呼出3: 呼出2からn=1
{
struct tree *newtree;
int x, nl, nr;
n=1 で呼び出し
if ( n==0 )
return( NULL );
else {
で呼び出された
→ 左部分木のノード数 nl = 0
右部分木のノード数 nr = 1-0-1 = 0
この木の根: 1個
nl = n/2; nr = n-nl-1;
/* 完全バランス木では左右の部分木の節点数の差は高々1 */
newtree
3
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
}
呼出4: tree(0)
ノード数
0の完全
バランス
木
呼出4 が完了して、
処理が戻ってきた時（実行後）のイメージ
struct tree *tree( int n )
呼出4: 呼出3からn=0
{
struct tree *newtree;
int x, nl, nr;
n=0 で呼び出し
if ( n==0 )
return( NULL );
で呼び出された
→ これより下に木はない
呼出3にNULL を返す。
else {
nl = n/2; nr = n-nl-1;
/* 完全バランス木では左右の部分木の節点数の差は高々1 */
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
}
struct tree *tree( int n )
呼出3: 呼出2からn=1
{
struct tree *newtree;
int x, nl, nr;
n=1 で呼び出し
if ( n==0 )
return( NULL );
else {
で呼び出された
→ 左部分木のノード数 nl = 0
右部分木のノード数 nr = 1-0-1 = 0
この木の根: 1個
nl = n/2; nr = n-nl-1;
/* 完全バランス木では左右の部分木の節点数の差は高々1 */
newtree
3
}
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
NU
LL
}
呼出4: tree(0)
呼出4 が完了して、
処理が戻ってきた
struct tree *tree( int n )
呼出3: 呼出2からn=1
{
struct tree *newtree;
int x, nl, nr;
n=1 で呼び出し
if ( n==0 )
return( NULL );
else {
で呼び出された
→ 左部分木のノード数 nl = 0
右部分木のノード数 nr = 1-0-1 = 0
この木の根: 1個
nl = n/2; nr = n-nl-1;
/* 完全バランス木では左右の部分木の節点数の差は高々1 */
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
newtree
3
}
NU
LL
NU
LL
}
呼出5: tree(0)
呼出5 が完了して、
処理が戻ってきた
struct tree *tree( int n )
呼出3: 呼出2からn=1
{
struct tree *newtree;
int x, nl, nr;
n=1 で呼び出し
if ( n==0 )
return( NULL );
else {
で呼び出された
→ 左部分木のノード数 nl = 0
右部分木のノード数 nr = 1-0-1 = 0
この木の根: 1個
nl = n/2; nr = n-nl-1;
/* 完全バランス木では左右の部分木の節点数の差は高々1 */
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
呼出2に、ポインタ newtreeの値を返す。
}
newtree
すなわち、
3
NU
LL
NU
LL
この部分木が返される。
struct tree *tree( int n )
呼出2: 呼出1からn=3
{
struct tree *newtree;
int x, nl, nr;
n=3 で呼び出し
if ( n==0 )
return( NULL );
else {
で呼び出された
→ 左部分木のノード数 nl = 1
右部分木のノード数 nr = 3-1-1 = 1
この木の根: 1個
nl = n/2; nr = n-nl-1;
/* 完全バランス木では左右の部分木の節点数の差は高々1 */
newtree
2
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
}
呼出3: tree(1)
ノード数
の完全
バランス
木
呼出3 が完了して、
処理が戻ってきた
struct tree *tree( int n )
呼出2: 呼出1からn=3
{
struct tree *newtree;
int x, nl, nr;
n=3 で呼び出し
if ( n==0 )
return( NULL );
else {
で呼び出された
→ 左部分木のノード数 nl = 1
右部分木のノード数 nr = 3-1-1 = 1
この木の根: 1個
nl = n/2; nr = n-nl-1;
/* 完全バランス木では左右の部分木の節点数の差は高々1 */
newtree
2
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
}
3
NU
LL
NU
LL
呼出3: tree(1)
呼出3 が完了して、
処理が戻ってきた
struct tree *tree( int n )
呼出2: 呼出1からn=3
{
struct tree *newtree;
int x, nl, nr;
n=3 で呼び出し
if ( n==0 )
return( NULL );
else {
で呼び出された
→ 左部分木のノード数 nl = 1
右部分木のノード数 nr = 3-1-1 = 1
この木の根: 1個
nl = n/2; nr = n-nl-1;
/* 完全バランス木では左右の部分木の節点数の差は高々1 */
newtree
2
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
}
3
NU
LL
呼出6: tree(1)
NU
LL
ノード数
1の完全
バランス
木
呼出6 が完了して、
処理が戻ってきた時のイメージ
struct tree *tree( int n )
呼出6: 呼出2からn=1
{
struct tree *newtree;
int x, nl, nr;
n=1 で呼び出し
if ( n==0 )
return( NULL );
else {
で呼び出された
→ 左部分木のノード数 nl = 0
右部分木のノード数 nr = 1-0-1 = 0
この木の根: 1個
nl = n/2; nr = n-nl-1;
/* 完全バランス木では左右の部分木の節点数の差は高々1 */
newtree
4
}
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
NU
LL
}
呼出7: tree(0)
呼出7が完了して、
処理が戻ってきた
struct tree *tree( int n )
呼出6: 呼出2からn=1
{
struct tree *newtree;
int x, nl, nr;
n=1 で呼び出し
if ( n==0 )
return( NULL );
else {
で呼び出された
→ 左部分木のノード数 nl = 0
右部分木のノード数 nr = 1-0-1 = 0
この木の根: 1個
nl = n/2; nr = n-nl-1;
/* 完全バランス木では左右の部分木の節点数の差は高々1 */
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
newtree
4
}
NU
LL
NU
LL
}
呼出8: tree(0)
呼出8が完了して、
処理が戻ってきた
struct tree *tree( int n )
呼出6: 呼出2からn=1
{
struct tree *newtree;
int x, nl, nr;
n=1 で呼び出し
if ( n==0 )
return( NULL );
else {
で呼び出された
→ 左部分木のノード数 nl = 0
右部分木のノード数 nr = 1-0-1 = 0
この木の根: 1個
nl = n/2; nr = n-nl-1;
/* 完全バランス木では左右の部分木の節点数の差は高々1 */
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
}
newtree
呼出6完了
この部分木を呼出2に返す
4
NU
LL
NU
LL
struct tree *tree( int n )
呼出2: 呼出1からn=3
{
struct tree *newtree;
int x, nl, nr;
n=3 で呼び出し
if ( n==0 )
return( NULL );
else {
で呼び出された
→ 左部分木のノード数 nl = 1
右部分木のノード数 nr = 3-1-1 = 1
この木の根: 1個
nl = n/2; nr = n-nl-1;
/* 完全バランス木では左右の部分木の節点数の差は高々1 */
newtree
2
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
}
3
NU
LL
呼出6: tree(1)
NU
LL
ノード数
1の完全
バランス
木
呼出6 が完了して、
処理が戻ってきた時のイメージ
struct tree *tree( int n )
呼出2: 呼出1からn=3
{
struct tree *newtree;
int x, nl, nr;
n=3 で呼び出し
if ( n==0 )
return( NULL );
else {
で呼び出された
→ 左部分木のノード数 nl = 1
右部分木のノード数 nr = 3-1-1 = 1
この木の根: 1個
nl = n/2; nr = n-nl-1;
/* 完全バランス木では左右の部分木の節点数の差は高々1 */
newtree
2
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
}
3
NU
LL
4
NU
LL
NU
LL
NU
LL
呼出6: tree(1)
呼出6 が完了して、
処理が戻ってきた
struct tree *tree( int n )
呼出2: 呼出1からn=3
{
struct tree *newtree;
int x, nl, nr;
n=3 で呼び出し
if ( n==0 )
return( NULL );
else {
で呼び出された
→ 左部分木のノード数 nl = 1
右部分木のノード数 nr = 3-1-1 = 1
この木の根: 1個
nl = n/2; nr = n-nl-1;
/* 完全バランス木では左右の部分木の節点数の差は高々1 */
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
newtree
}
呼出2: 完了
2
この部分木を呼出1に返す
3
NU
LL
4
NU
LL
NU
LL
NU
LL
struct tree *tree( int n )
呼出1: mainからn=6 で呼び出された
{
struct tree *newtree;
int x, nl, nr;
n=6 で呼び出し
if ( n==0 )
return( NULL );
else {
→ 左部分木のノード数 nl = 3
右部分木のノード数 nr = 6-3-1 = 2
この木の根: 1個
nl = n/2; nr = n-nl-1;
/* 完全バランス木では左右の部分木の節点数の差は高々1 */
newtree
1
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
}
呼出2: tree(3)
ノード数
3の完全
バランス
木
呼出2 が完了して、
処理が戻ってきた時（実行後）のイメージ
struct tree *tree( int n )
呼出1: mainからn=6 で呼び出された
{
struct tree *newtree;
int x, nl, nr;
n=6 で呼び出し
if ( n==0 )
return( NULL );
else {
→ 左部分木のノード数 nl = 3
右部分木のノード数 nr = 6-3-1 = 2
この木の根: 1個
nl = n/2; nr = n-nl-1;
/* 完全バランス木では左右の部分木の節点数の差は高々1 */
newtree
1
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
}
2
呼出2: tree(3)
3
NU
LL
4
NU
LL
NU
LL
NU
LL
呼出2 が完了して、
処理が戻ってきた時（実行後）のイメージ
struct tree *tree( int n )
呼出1: mainからn=6 で呼び出された
{
struct tree *newtree;
int x, nl, nr;
n=6 で呼び出し
if ( n==0 )
return( NULL );
else {
→ 左部分木のノード数 nl = 3
右部分木のノード数 nr = 6-3-1 = 2
この木の根: 1個
nl = n/2; nr = n-nl-1;
/* 完全バランス木では左右の部分木の節点数の差は高々1 */
newtree
1
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
}
}
2
呼出9: tree(2)
3
NU
LL
4
NU
LL
NU
LL
NU
LL
ノード数
2の完全
バランス
木
呼出9 が完了して、
処理が戻ってきた時（実行後）のイメージ
struct tree *tree( int n )
呼出1: mainからn=6 で呼び出された
{
struct tree *newtree;
int x, nl, nr;
n=6 で呼び出し
if ( n==0 )
return( NULL );
else {
→ 左部分木のノード数 nl = 3
右部分木のノード数 nr = 6-3-1 = 2
この木の根: 1個
nl = n/2; nr = n-nl-1;
/* 完全バランス木では左右の部分木の節点数の差は高々1 */
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
newtree
1
}
}
2
5
NU
LL
3
NU
LL
4
NU
LL
NU
LL
6
NU
LL
NU
LL
NU
LL
呼出9: tree(2)
略
呼出9 が完了して、
処理が戻ってきた
struct tree *tree( int n )
呼出1: mainからn=6 で呼び出された
{
struct tree *newtree;
int x, nl, nr;
n=6 で呼び出し
if ( n==0 )
return( NULL );
else {
→ 左部分木のノード数 nl = 3
右部分木のノード数 nr = 6-3-1 = 2
この木の根: 1個
nl = n/2; nr = n-nl-1;
/* 完全バランス木では左右の部分木の節点数の差は高々1 */
newtree = (struct tree *)malloc(sizeof(struct tree));
newtree->key = get_data( );
newtree->left = tree( nl ); /* 再帰的に左部分木を生成 */
newtree->right = tree( nr ); /* 再帰的に右部分木を生成 */
return( newtree );
newtree
1
}
}
2
呼出1: 完了
5
NU
LL
3
NU
LL
4
NU
LL
NU
LL
6
NU
LL
NU
LL
NU
LL
mainに部分木を返す
int a[] = { 1, 2, 3, 4, 5, 6, EOD};
root
int main(void)
{
struct tree *root;
root = tree( 6 );
ノード数6
の完全バラ
ンス木
略
}
呼出1: tree(6)
呼出1 が完了して、
処理が戻ってきた時（実行後）のイメージ
int a[] = { 1, 2, 3, 4, 5, 6, EOD};
root
int main(void)
{
struct tree *root;
1
2
root = tree( 6 );
NU
LL
略
}
5
3
NU
LL
4
NU
LL
NU
LL
6
NU
LL
NU
LL
NU
LL

ニッポンバラタナゴから考える持続可能な地域づくり

講座番号1 笑学英語

スライド タイトルなし

- 1 - 発展途上国支援を考えてきました！ 去る (土)，有志9名が国際協力

データベース

アルゴリズムと データ構造

2015/4～6月時間のパンフレットをダウンロード

松前柔道塾だより - 学校法人東海大学

ユーザプリファレンスに基づく転送制御を 行う アプリ

卒業研究関係の話題 （Tree decomposition)