スライド 1 - 横浜国立大学富井研究室

アルゴリズムとデータ構造
補足資料12-2
「2分木」
横浜国立大学
理工学部
数物・電子情報系学科
富井尚志
struct tree {
int key;
struct tree *left;
struct tree *right;
};
key
left
21
NULL right NULL
の「ひな形」（型）
１．メモリに割当てる
p = (struct tree *)malloc(sizeof(struct tree));
２．その量は、”struct tree”型1個分
３．mallocの戻り値は、割当てたメモリの先頭アドレス
４．そのアドレス（参照先）の中身は “struct tree”型として、「キャスト」（型変換）
５．“struct tree”型へのポインタとして、アドレスを代入
この書き方は、憶えましょう。
結果は
↓これ（１個割当て）
p
key
left
right
要するに、
新しく「箱」ができる。
この箱に名前（変数名）はない。
だから、ポインタ変数pで指し示しておく必要がある。
#include<stdio.h>
#include<stdlib.h>
struct tree {
int key;
struct tree *left;
struct tree *right;
};
main()
{
struct tree *root, *new_node;
root=(struct tree *)malloc(sizeof(struct tree));
root->key= 1;
new_node = (struct tree *)malloc(sizeof(struct tree));
new_node->key = 2; new_node->left = NULL; new_node->right=NULL;
root->left = new_node;
new_node = (struct tree *)malloc(sizeof(struct tree));
new_node->key = 3; new_node->left = NULL; new_node->right=NULL;
root->right = new_node;
printf(“%d <-(left)- %d -(right)-> %d\n”, root->left->key, root->key, root->right->key);
printf(“root = %x, root->left=%x, root->right=%x\n”, root, root->left, root->right);
return 0;
}
#include<stdio.h>
#include<stdlib.h>
root
struct tree {
int key;
struct tree *left;
struct tree *right;
};
main()
{
struct tree *root, *new_node;
new_node
root=(struct tree *)malloc(sizeof(struct tree));
root->key= 1;
new_node = (struct tree *)malloc(sizeof(struct tree));
new_node->key = 2; new_node->left = NULL; new_node->right=NULL;
root->left = new_node;
new_node = (struct tree *)malloc(sizeof(struct tree));
new_node->key = 3; new_node->left = NULL; new_node->right=NULL;
root->right = new_node;
printf(“%d <-(left)- %d -(right)-> %d\n”, root->left->key, root->key, root->right->key);
printf(“root = %x, root->left=%x, root->right=%x\n”, root, root->left, root->right);
return 0;
}
#include<stdio.h>
#include<stdlib.h>
root
struct tree {
int key;
struct tree *left;
struct tree *right;
};
main()
{
struct tree *root, *new_node;
key
left
new_node
root=(struct tree *)malloc(sizeof(struct tree));
root->key= 1;
new_node = (struct tree *)malloc(sizeof(struct tree));
new_node->key = 2; new_node->left = NULL; new_node->right=NULL;
root->left = new_node;
new_node = (struct tree *)malloc(sizeof(struct tree));
new_node->key = 3; new_node->left = NULL; new_node->right=NULL;
root->right = new_node;
printf(“%d <-(left)- %d -(right)-> %d\n”, root->left->key, root->key, root->right->key);
printf(“root = %x, root->left=%x, root->right=%x\n”, root, root->left, root->right);
return 0;
}
right
#include<stdio.h>
#include<stdlib.h>
root
struct tree {
int key;
struct tree *left;
struct tree *right;
};
main()
{
struct tree *root, *new_node;
left
new_node
root=(struct tree *)malloc(sizeof(struct tree));
root->key= 1;
new_node = (struct tree *)malloc(sizeof(struct tree));
new_node->key = 2; new_node->left = NULL; new_node->right=NULL;
root->left = new_node;
new_node = (struct tree *)malloc(sizeof(struct tree));
new_node->key = 3; new_node->left = NULL; new_node->right=NULL;
root->right = new_node;
printf(“%d <-(left)- %d -(right)-> %d\n”, root->left->key, root->key, root->right->key);
printf(“root = %x, root->left=%x, root->right=%x\n”, root, root->left, root->right);
return 0;
}
1
key
right
#include<stdio.h>
#include<stdlib.h>
root
struct tree {
int key;
struct tree *left;
struct tree *right;
};
main()
{
struct tree *root, *new_node;
left
new_node
root=(struct tree *)malloc(sizeof(struct tree));
root->key= 1;
key
left
right
new_node = (struct tree *)malloc(sizeof(struct tree));
new_node->key = 2; new_node->left = NULL; new_node->right=NULL;
root->left = new_node;
new_node = (struct tree *)malloc(sizeof(struct tree));
new_node->key = 3; new_node->left = NULL; new_node->right=NULL;
root->right = new_node;
printf(“%d <-(left)- %d -(right)-> %d\n”, root->left->key, root->key, root->right->key);
printf(“root = %x, root->left=%x, root->right=%x\n”, root, root->left, root->right);
return 0;
}
1
key
right
#include<stdio.h>
#include<stdlib.h>
root
struct tree {
int key;
struct tree *left;
struct tree *right;
};
main()
{
struct tree *root, *new_node;
left
2
key
left NULL
rightNULL
new_node = (struct tree *)malloc(sizeof(struct tree));
new_node->key = 2; new_node->left = NULL; new_node->right=NULL;
root->left = new_node;
new_node = (struct tree *)malloc(sizeof(struct tree));
new_node->key = 3; new_node->left = NULL; new_node->right=NULL;
root->right = new_node;
printf(“%d <-(left)- %d -(right)-> %d\n”, root->left->key, root->key, root->right->key);
printf(“root = %x, root->left=%x, root->right=%x\n”, root, root->left, root->right);
}
right
new_node
root=(struct tree *)malloc(sizeof(struct tree));
root->key= 1;
return 0;
1
key
#include<stdio.h>
#include<stdlib.h>
root
struct tree {
int key;
struct tree *left;
struct tree *right;
};
main()
{
struct tree *root, *new_node;
left
2
key
left NULL
rightNULL
new_node = (struct tree *)malloc(sizeof(struct tree));
new_node->key = 2; new_node->left = NULL; new_node->right=NULL;
root->left = new_node;
new_node = (struct tree *)malloc(sizeof(struct tree));
new_node->key = 3; new_node->left = NULL; new_node->right=NULL;
root->right = new_node;
printf(“%d <-(left)- %d -(right)-> %d\n”, root->left->key, root->key, root->right->key);
printf(“root = %x, root->left=%x, root->right=%x\n”, root, root->left, root->right);
}
right
new_node
root=(struct tree *)malloc(sizeof(struct tree));
root->key= 1;
return 0;
1
key
#include<stdio.h>
#include<stdlib.h>
root
struct tree {
int key;
struct tree *left;
struct tree *right;
};
main()
{
struct tree *root, *new_node;
left
2
key
rightNULL
left
key
left NULL
new_node = (struct tree *)malloc(sizeof(struct tree));
new_node->key = 2; new_node->left = NULL; new_node->right=NULL;
root->left = new_node;
new_node = (struct tree *)malloc(sizeof(struct tree));
new_node->key = 3; new_node->left = NULL; new_node->right=NULL;
root->right = new_node;
printf(“%d <-(left)- %d -(right)-> %d\n”, root->left->key, root->key, root->right->key);
printf(“root = %x, root->left=%x, root->right=%x\n”, root, root->left, root->right);
}
right
new_node
root=(struct tree *)malloc(sizeof(struct tree));
root->key= 1;
return 0;
1
key
right
#include<stdio.h>
#include<stdlib.h>
root
struct tree {
int key;
struct tree *left;
struct tree *right;
};
main()
{
struct tree *root, *new_node;
left
2
key
left NULL
rightNULL
new_node = (struct tree *)malloc(sizeof(struct tree));
new_node->key = 2; new_node->left = NULL; new_node->right=NULL;
root->left = new_node;
new_node = (struct tree *)malloc(sizeof(struct tree));
new_node->key = 3; new_node->left = NULL; new_node->right=NULL;
root->right = new_node;
printf(“%d <-(left)- %d -(right)-> %d\n”, root->left->key, root->key, root->right->key);
printf(“root = %x, root->left=%x, root->right=%x\n”, root, root->left, root->right);
}
right
new_node
root=(struct tree *)malloc(sizeof(struct tree));
root->key= 1;
return 0;
1
key
key
left NULL
3
rightNULL
#include<stdio.h>
#include<stdlib.h>
root
struct tree {
int key;
struct tree *left;
struct tree *right;
};
main()
{
struct tree *root, *new_node;
left
2
key
left NULL
rightNULL
new_node = (struct tree *)malloc(sizeof(struct tree));
new_node->key = 2; new_node->left = NULL; new_node->right=NULL;
root->left = new_node;
new_node = (struct tree *)malloc(sizeof(struct tree));
new_node->key = 3; new_node->left = NULL; new_node->right=NULL;
root->right = new_node;
printf(“%d <-(left)- %d -(right)-> %d\n”, root->left->key, root->key, root->right->key);
printf(“root = %x, root->left=%x, root->right=%x\n”, root, root->left, root->right);
}
right
new_node
root=(struct tree *)malloc(sizeof(struct tree));
root->key= 1;
return 0;
1
key
key
left NULL
3
rightNULL
#include<stdio.h>
#include<stdlib.h>
root
struct tree {
int key;
struct tree *left;
struct tree *right;
};
main()
{
struct tree *root, *new_node;
root->key
1
key
root->left
left
root->right
right
new_node
root->right->key
root->left->key
root=(struct tree *)malloc(sizeof(struct tree));
root->key= 1;
2
key
left NULL
rightNULL
new_node = (struct tree *)malloc(sizeof(struct tree));
new_node->key = 2; new_node->left = NULL; new_node->right=NULL;
root->left = new_node;
root->left->left
new_node = (struct tree *)malloc(sizeof(struct tree));
new_node->key = 3; new_node->left = NULL; new_node->right=NULL;
root->right = new_node;
root->left->right
3
key
left NULL
rightNULL
root->right->left
root->right>right
printf(“%d <-(left)- %d -(right)-> %d\n”, root->left->key, root->key, root->right->key);
printf(“root = %x, root->left=%x, root->right=%x\n”, root, root->left, root->right);
return 0;
}
2 <-(left)- 1 –(right)-> 3
root = 40ea0820, root->left = 40ea0830, root->right = 40ea0840
#include<stdio.h>
#include<stdlib.h>
root
struct tree {
int key;
struct tree *left;
struct tree *right;
};
main()
{
struct tree *root, *new_node;
root->key
1
key
root->left
left
root->right
right
new_node
root->right->key
root->left->key
root=(struct tree *)malloc(sizeof(struct tree));
root->key= 1;
2
key
left NULL
rightNULL
new_node = (struct tree *)malloc(sizeof(struct tree));
new_node->key = 2; new_node->left = NULL; new_node->right=NULL;
root->left = new_node;
root->left->left
new_node = (struct tree *)malloc(sizeof(struct tree));
new_node->key = 3; new_node->left = NULL; new_node->right=NULL;
root->right = new_node;
root->left->right
3
key
left NULL
rightNULL
root->right->left
root->right>right
printf(“%d <-(left)- %d -(right)-> %d\n”, root->left->key, root->key, root->right->key);
printf(“root = %x, root->left=%x, root->right=%x\n”, root, root->left, root->right);
return 0;
}
2 <-(left)- 1 –(right)-> 3
root = 40ea0810, root->left = 40ea0820, root->right = 40ea0830
アドレス（32bit）,
4アドレス飛び
中身（1記憶単位=8bitを4領
域まとめて32bitで表示）
…
…
0x 40ea 0800
0x 40ea 0810
root
0x 123a 1263
0x 40ea 0804
0x 40ea 0808
1
key
root->left
left
root->right
right
0x 40ea 0830
new_node
0x 4c6f a750
0x 40ea 080c
0x 40ea 0810
key
1
0x 40ea 0814
left
0x 40ea 0820
0x 40ea 0818
right
0x 40ea 0830
root->right->key
root->left->key
key
left NULL
2
rightNULL
3
key
left NULL
rightNULL
0x 40ea 0834
0x 40ea 081c
0x 40ea 0820
key
2
0x 40ea 0824
left
0x 0000 0000
0x 40ea 0828
right
0x 0000 0000
0x 0000 0015
0x 40ea 082c
0x 40ea 0830
key
3
0x 40ea 0834
left
0x 0000 0000
0x 40ea 0838
right
0x 0000 0000
0x 0101 0000
0x 40ea 083c
…
root->key
…
root->left->left
root->right->left
root->left->right
root->right>right

Download Report