スライド 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 #include 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 %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 #include 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 %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 #include 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 %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 #include 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 %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 #include 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 %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 #include 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 %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 #include 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 %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 #include 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 %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 #include 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 %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 #include 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 %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 #include 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 %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 3 root = 40ea0820, root->left = 40ea0830, root->right = 40ea0840

#include #include 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 %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 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