二分木の実装

Transcription

1 二分木の実装

2 この回の要点 二分木の C 言語による実装を理解する 再帰呼び出しによる木のなぞりの実装を理解する 関数ポインタを使った汎用処理の実装を理解する

3 実装コードの構成 汎用的構造 各ノードは void* を持つ 二分木のノード BinTreeNode.h BinTreeNode.cc 二分木 BinTree.h BinTree.cc テスト用 TestBinTree.cc BinTree BinTreeNode

4 BinTreeNode.h #ifndef BinTreeNode h #define BinTreeNode h /*** *** 二分木ノード ***/ #include <stdio.h> #include <stdlib.h> // ノード型 typedef struct BinTreeNodeTag { struct BinTreeNodeTag *parent; struct BinTreeNodeTag *left,*right; void *data; BinTreeNode; 続く

5 BinTreeNode.h // プロトタイプ宣言 BinTreeNode *makebintreenode(void*); BinTreeNode *makebintreenode(void*, BinTreeNode*,BinTreeNode*); void free(bintreenode*); void setleft(bintreenode*,bintreenode*); void setright(bintreenode*,bintreenode*); void setdata(bintreenode*,void*); #endif // BinTreeNode h

6 BinTreeNode.cc /*** *** 二分木ノードの実装 ***/ #include "BinTreeNode.h" // 生成 BinTreeNode *makebintreenode(void *d){ BinTreeNode *n=(bintreenode*)malloc(sizeof(bintreenode)); n->data=d; n->parent=n->left=n->right=null; return n; どこにもつながっていない 続く

7 BinTreeNode.cc // 子ノードを指定して生成 BinTreeNode *makebintreenode(void *d, BinTreeNode *nl,bintreenode *nr){ BinTreeNode *n=(bintreenode*)malloc(sizeof(bintreenode)); n->data=d; n->parent=null; 親はない setleft(n,nl); setright(n,nr); 左右の子を設定する return n; // 破棄 void free(bintreenode *n){ free((void*)n); 続く

8 BinTreeNode.cc // nの左にlを設定する void setleft(bintreenode *n,bintreenode *l){ n->left=l; if(l) l->parent=n; もし l が NULL でないなら 親をセットする // nの右にrを設定する void setright(bintreenode *n,bintreenode *r){ n->right=r; if(r) r->parent=n; もし r が NULL でないなら 親をセットする // n にデータを設定する void setdata(bintreenode *n,void *d){ n->data=d;

9 BinTreeNode の使い方 BinTreeNode *n1; n1=makebintreenode(makepd( 山田,19)); 単独ノードの作成 NULL BinTreeNode parent void* left right PD name= 山田 age=19 NULL NULL BinTreeNode *n2; n2=makebintreenode(makepd( 森,55));

10 BinTreeNode の使い方 子ノードを持つノードの作成 BinTreeNode *n3; n3=makebintreenode(makepd( 中村,32),n1,n2); NULL BinTreeNode parent void* left right PD name= 中村 age=32 BinTreeNode parent void* left right PD name= 山田 age=19 left parent void* BinTreeNode PD right name= 森 age=55 NULL NULL NULL NULL

11 BinTree.h #ifndef BinTree h #define BinTree h /*** *** 二分木 ***/ #include "BinTreeNode.h" // 二分木型 typedef struct { BinTreeNode *root; BinTree; 続く

12 BinTree.h // プロトタイプ宣言 BinTree *makebintree(); BinTree *makebintree(bintreenode*); void free(bintree*); void setroot(bintree*,bintreenode*); void traverse(bintree*,int,void(*)(void*)); #endif // BinTree h

13 BinTree.cc /*** *** 二分木 ***/ #include "BinTree.h" // 生成 BinTree *makebintree(){ BinTree *t=(bintree*)malloc(sizeof(bintree)); t->root=null; return t; 根がNULLは 空の木 // 根ノードを指定して生成 BinTree *makebintree(bintreenode *r){ BinTree *t=(bintree*)malloc(sizeof(bintree)); t->root=r; return t; 続く

14 BinTree.cc // 根ノードの設定 void setroot(bintree *t,bintreenode *r){ t->root=r; // 行きがけ順のなぞり void traversepreorder(bintreenode *n,void(*func)(void*)){ func(n->data); if(n->left) traversepreorder(n->left,func); if(n->right) traversepreorder(n->right,func); // 通りがけ順のなぞり void traverseinorder(bintreenode *n,void(*func)(void*)){ if(n->left) traverseinorder(n->left,func); func(n->data); if(n->right) traverseinorder(n->right,func); 続く

15 BinTree.cc // 帰りがけ順のなぞり void traversepostorder(bintreenode *n,void(*func)(void*)){ if(n->left) traversepostorder(n->left,func); if(n->right) traversepostorder(n->right,func); func(n->data); void traversepostordernode(bintreenode *n,void(*func)(void*)){ if(n->left) traversepostorder(n->left,func); if(n->right) traversepostorder(n->right,func); func(n); この関数は 木のノードを全部解放するために内部的に使用する プロトタイプ宣言されていないため 外からは呼び出すことが出来ない 続く

16 BinTree.cc // 破棄 ( 中のノードも破棄する ) void freebintreenode(void *n){ free((bintreenode*)n); void free(bintree *t){ traversepostordernode(t->root,freebintreenode); free((void*)t); // 木のなぞり void travrse(bintree *t,int m,void(*func)(void*)){ switch(m){ case 0: traversepreorder(t->root,func); break; case 1: traverseinorder(t->root,func); break; case 2: traversepostorder(t->root,func); break;

17 BinTree の使い方 BinTree *tree=makebintree(n6); 根ノード付き木の作成 BinTree root n6 n3 n5 n1 n2 n4

18 BinTree のなぞり void printpd(void *v){ PD *pd=(pd*)v; print(pd); printf( );... traverse(tree,0,printpd); 木をなぞりつつ 毎回この関数が呼び出される そのとき 引数としてノードの持つデータが渡される ( ただし void* として )

19 TestBinTree.cc /*** BinTree のテスト ***/ #include "BinTree.h" #include "PD.h" void printpd(void* v){ PD *pd=(pd*)v; // 渡されてきたデータをPD* に変換 print(pd); // pdのデータを表示 printf(" - "); // " - " を表示 int main(){ BinTreeNode *n1,*n2,*n3,*n4,*n5,*n6; n1=makebintreenode(makepd(" 山田 ",18)); n2=makebintreenode(makepd(" 森 ",55)); n3=makebintreenode(makepd(" 中村 ",32),n1,n2); n4=makebintreenode(makepd(" 石田 ",27)); n5=makebintreenode(makepd(" 今井 ",60),NULL,n4); n6=makebintreenode(makepd(" 牧 ",30),n3,n5);

20 TestBinTree.cc BinTree *tree=makebintree(n6); // 木を生成 printf("***pre*** n"); traverse(tree,0,printpd); // 行きがけ順 printf(" n"); printf("***in*** n"); traverse(tree,1,printpd); // 通りがけ順 printf(" n"); printf("***post*** n"); traverse(tree,2,printpd); // 帰りがけ順 printf(" n"); free(tree);

21 TestBinTree の結果 $ TestBinTree ***Pre*** 牧 (30) - 中村 (32) - 山田 (18) - 森 (55) - 今井 (60) - 石田 (27) - ***In*** 山田 (18) - 中村 (32) - 森 (55) - 牧 (30) - 今井 (60) - 石田 (27) - ***Post*** 山田 (18) - 森 (55) - 中村 (32) - 石田 (27) - 今井 (60) - 牧 (30) -

22 課題 右の個人情報の二分木構造を作成し表示せよ その後 40 歳以上の人の年齢を 5 歳増やし 再度表示せよ プログラムは add5pd.cc とすること 表示順は行きがけ順 以下の関数を作って使うこと printpd() : PD を表示する addpd() : PD のうち 40 歳以上の年齢を +5 する 森 (55) 山田 (19) 今井 (66) 提出方法 : ワードで作成し プログラムと実行結果を張り付けること ( 文字でも画像でもよい ) プログラムは自分で作ったコードだけでよい 提出先 :fuchida@ibe.kagoshima-u.ac.jp メールタイトル : アルゴリズム課題 提出期限 :2018 年 12 月 10 日 ( 日 ) 24:00 牧 (33) 久永 (53) 石田 (27) 川平 (48) 前田 (50) 中村 (35)