• 検索結果がありません。

アルゴリズムとデータ構造 補足資料 12-3 「サンプルプログラム treeop1.c 」

N/A
N/A
Info
ダウンロード
Protected

Academic year: 2021

シェア "アルゴリズムとデータ構造 補足資料 12-3 「サンプルプログラム treeop1.c 」"

Copied!
67
0
0

読み込み中.... (全文を見る)

今ダウンロードする ( 67 ページ )

全文

(1)

アルゴリズムとデータ構造 補足資料

12-3

「サンプルプログラム

treeop1.c

」

横浜国立大学 理工学部 数物・電子情報系学科 富井尚志

(2)

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)

(3)

呼出

1: tree(6)

呼出

1

が完了して、

処理が戻ってきた時（実行後）のイメージ

int a[] = { 1, 2, 3, 4, 5, 6, EOD};

int main(void) {

struct tree *root;

root = tree( 6 );

略 }

root

ノード数 6 ランス木の完全バ

(4)

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 );

} }

呼出 1: main から n=6 で呼び出された

n=6 で呼び出し

→ 左部分木のノード数 nl = 3

右部分木のノード数 nr = 6-3-1 = 2 この木の根 : 1 個

newtree

1

ノード数3の 完全バランス

呼出2: tree(3)

呼出2 が完了して、

処理が戻ってきた時（実行後）のイメージ

(5)

tree(6) : 呼出 1

if ( n==0 ) 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

newtree

(6)

tree(6) : 呼出 1

if ( n==0 ) 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

newtree

tree(3) : 呼出 2

if ( n==0 ) 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 );

}

newtree

(7)

tree(6) : 呼出 1

if ( n==0 ) 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

newtree

tree(3) : 呼出 2

if ( n==0 ) 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 );

}

newtree

2

(8)

tree(6) : 呼出 1

if ( n==0 ) 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

newtree

tree(3) : 呼出 2

if ( n==0 ) 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 );

}

newtree

2

tree(1) : 呼出 3

if ( n==0 ) 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 );

}

newtree

(9)

tree(6) : 呼出 1

if ( n==0 ) 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

newtree

tree(3) : 呼出 2

if ( n==0 ) 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 );

}

newtree

2

tree(1) : 呼出 3

if ( n==0 ) 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 );

}

newtree

3

(10)

tree(6) : 呼出 1

if ( n==0 ) 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

newtree

tree(3) : 呼出 2

if ( n==0 ) 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 );

}

newtree

2

tree(1) : 呼出 3

if ( n==0 ) 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 );

}

newtree

3

tree(0) : 呼出 4

if ( n==0 ) 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 );

}

newtree

(11)

tree(6) : 呼出 1

if ( n==0 ) 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

newtree

tree(3) : 呼出 2

if ( n==0 ) 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 );

}

newtree

2

tree(1) : 呼出 3

if ( n==0 ) 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 );

}

newtree

3

tree(0) : 呼出 4

if ( n==0 ) 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 );

}

newtree

NULL

(12)

tree(6) : 呼出 1

if ( n==0 ) 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

newtree

tree(3) : 呼出 2

if ( n==0 ) 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 );

}

newtree

2

tree(1) : 呼出 3

if ( n==0 ) 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 );

}

newtree

N3

tree(0) : 呼出 4

if ( n==0 ) 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 );

}

newtree

NULL

(13)

tree(6) : 呼出 1

if ( n==0 ) 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

newtree

tree(3) : 呼出 2

if ( n==0 ) 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 );

}

newtree

2

tree(1) : 呼出 3

if ( n==0 ) 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 );

}

newtree

N3

U L L

tree(0) : 呼出 5

if ( n==0 ) 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 );

}

newtree

(14)

tree(6) : 呼出 1

if ( n==0 ) 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

newtree

tree(3) : 呼出 2

if ( n==0 ) 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 );

}

newtree

2

tree(1) : 呼出 3

if ( n==0 ) 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 );

}

newtree

N3

tree(0) : 呼出 5

if ( n==0 ) 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 );

}

newtree

NULL

(15)

tree(6) : 呼出 1

if ( n==0 ) 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

newtree

tree(3) : 呼出 2

if ( n==0 ) 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 );

}

newtree

2

tree(1) : 呼出 3

if ( n==0 ) 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 );

}

newtree

N3

U L L

N U L L

tree(0) : 呼出 5

if ( n==0 ) 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 );

}

newtree

NULL

(16)

tree(6) : 呼出 1

if ( n==0 ) 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

newtree

tree(3) : 呼出 2

if ( n==0 ) 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 );

}

newtree

2

tree(1) : 呼出 3

if ( n==0 ) 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 );

}

newtree

N3 N

(17)

tree(6) : 呼出 1

if ( n==0 ) 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

newtree

tree(3) : 呼出 2

if ( n==0 ) 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 );

}

newtree

2

tree(1) : 呼出 3

if ( n==0 ) 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 );

}

newtree

N3

U L L

N U L L

(18)

tree(6) : 呼出 1

if ( n==0 ) 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

newtree

tree(3) : 呼出 2

if ( n==0 ) 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 );

}

newtree

2

N3 N

(19)

tree(6) : 呼出 1

if ( n==0 ) 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

newtree

tree(3) : 呼出 2

if ( n==0 ) 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 );

}

newtree

2

N3

U L L

N U L L

tree(1) : 呼出 6

if ( n==0 ) 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 );

}

newtree

(20)

tree(6) : 呼出 1

if ( n==0 ) 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

newtree

tree(3) : 呼出 2

if ( n==0 ) 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 );

}

newtree

2

N3 N

tree(1) : 呼出 6

if ( n==0 ) 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 );

}

newtree

4

(21)

tree(6) : 呼出 1

if ( n==0 ) 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

newtree

tree(3) : 呼出 2

if ( n==0 ) 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 );

}

newtree

2

N3

U L L

N U L L

tree(1) : 呼出 6

if ( n==0 ) 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 );

}

newtree

N4

U L L

tree(0) : 呼出 7

if ( n==0 ) 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 );

}

newtree

NULL

(22)

tree(6) : 呼出 1

if ( n==0 ) 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

newtree

tree(3) : 呼出 2

if ( n==0 ) 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 );

}

newtree

2

N3 N

tree(1) : 呼出 6

if ( n==0 ) 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 );

}

newtree

N4 N

tree(0) : 呼出 8

if ( n==0 ) 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 );

newtree

UN LL

(23)

tree(6) : 呼出 1

if ( n==0 ) 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

newtree

tree(3) : 呼出 2

if ( n==0 ) 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 );

}

newtree

2

N3

U L L

N U L L

tree(1) : 呼出 6

if ( n==0 ) 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 );

}

newtree

N4

U L L

N U L L

(24)

tree(6) : 呼出 1

if ( n==0 ) 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

newtree

tree(3) : 呼出 2

if ( n==0 ) 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 );

}

newtree

2

N3 N N4 N

(25)

tree(6) : 呼出 1

if ( n==0 ) 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

newtree

tree(3) : 呼出 2

if ( n==0 ) 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 );

}

newtree

2

N3

U L L

N U L L

N4

U L L

N U L L

(26)

tree(6) : 呼出 1

if ( n==0 ) 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

newtree

tree(3) : 呼出 2

if ( n==0 ) 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 );

}

newtree

2

N3 N N4 N

(27)

tree(6) : 呼出 1

if ( n==0 ) 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

newtree

2

N3

U L L

N U L L

N4

U L L

N U L L

(28)

tree(6) : 呼出 1

if ( n==0 ) 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

newtree

2

N3 N N4 N

tree(2) : 呼出 9

if ( n==0 ) 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 );

}

newtree

(29)

tree(6) : 呼出 1

if ( n==0 ) 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

newtree

2

N3

U L L

N U L L

N4

U L L

N U L L

tree(2) : 呼出 9

if ( n==0 ) 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 );

}

newtree

5

(30)

tree(6) : 呼出 1

if ( n==0 ) 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

newtree

2

N3 N N4 N

tree(2) : 呼出 9

if ( n==0 ) 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 );

}

newtree

5

tree(1) : 呼出10

if ( n==0 ) 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 );

}

newtree

(31)

tree(6) : 呼出 1

if ( n==0 ) 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

newtree

2

N3

U L L

N U L L

N4

U L L

N U L L

tree(2) : 呼出 9

if ( n==0 ) 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 );

}

newtree

5

tree(1) : 呼出10

if ( n==0 ) 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 );

}

newtree

6

(32)

tree(6) : 呼出 1

if ( n==0 ) 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

newtree

2

N3 N N4 N

tree(2) : 呼出 9

if ( n==0 ) 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 );

}

newtree

5

tree(1) : 呼出10

if ( n==0 ) 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 );

}

newtree

N6

(33)

tree(6) : 呼出 1

if ( n==0 ) 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

newtree

2

N3

U L L

N U L L

N4

U L L

N U L L

tree(2) : 呼出 9

if ( n==0 ) 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 );

}

newtree

5

tree(1) : 呼出10

if ( n==0 ) 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 );

}

newtree

N6

U L L

N U L L

参照

今ダウンロードする ( PPTX - 67 ページ - 298.06 KB )

関連したドキュメント

複数需要モデル：

東京工業大学

均衡を近似的に求めるアルゴリズム

東京工業大学

多項式最適化入門

情報理工学研究科 情報・通信工学専攻. 2012/7/12

認定学校等一覧 ( 電気通信主任技術者資格 ) 令和 4 年 4 月 1 日現在 適用年月 平成 17 年 1 月の制度改正により それまで適用年月欄に記載された年月以降の卒業者が科目免除の対象であったものを 適用年月欄に記載された年月以降に入学し 認定に係る教育課程の単位を取得した者を科目免除の対

関東総合通信局 東京電機大学 工学部電気電子工学科 電気通信システム 昭和６２年３月以降

Microsoft Word - 【 公表用】2023年度入試概要（公表文）.docx

理工学部・情報理工学部・生命科学部・薬学部 AO 英語基準入学試験【4 月入学】 国際関係学部・グローバル教養学部・情報理工学部 AO

数理解析研究所 2011

 当図書室は、専門図書館として数学、応用数学、計算機科学、理論物理学の分野の文

無人運航ビジネスモデルの調査研究

清水 悦郎 国立大学法人東京海洋大学 学術研究院海洋電子機械工学部門 教授 鶴指 眞志 長崎県立大学 地域創造学部実践経済学科 講師 クロサカタツヤ 株式会社企 代表取締役.

ク リ ス チ ャ ン で す が ︑ お 寺 は 普 通 に 行 き ま す よ

静岡大学 静岡キャンパス 静岡大学 浜松キャンパス 静岡県立大学 静岡県立大学短期大学部 東海大学 清水キャンパス