二分木の実装

Algorithms and Data Structures on C
二分木の実装
Algorithms and Data Structures on C
この回の要点
• 二分木のＣ言語による実装を理解する
• 再帰呼び出しによる木のなぞりの実装を理解する
• 関数ポインタを使った汎用処理の実装を理解する
Algorithms and Data Structures on C
実装コードの構成
• 汎用的構造
• 各ノードはvoid*を持つ
• 二分木のノード
• BinTreeNode.h
• BinTreeNode.cc
• 二分木
• BinTree.h
• BinTree.cc
• テスト用
• TestBinTree.cc
Algorithms and Data Structures on C
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;
続く
Algorithms and Data Structures on C
BinTreeNode.h
// プロトタイプ宣言
BinTreeNode *makeBinTreeNode(void*);
BinTreeNode *makeBinTreeNode(void*,
BinTreeNode*,BinTreeNode*);
void freeBinTreeNode(BinTreeNode*);
void setLeft(BinTreeNode*,BinTreeNode*);
void setRight(BinTreeNode*,BinTreeNode*);
void setData(BinTreeNode*,void*);
#endif // __BinTreeNode__h
Algorithms and Data Structures on C
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;
}
続く
Algorithms and Data Structures on C
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 freeBinTreeNode(BinTreeNode *n){
free(n);
}
続く
Algorithms and Data Structures on C
BinTreeNode.cc
// nの左にlを設定する
void setLeft(BinTreeNode *n,BinTreeNode *l){
n->left=l;
if(l) l->parent=n;
}
// nの右にrを設定する
void setRight(BinTreeNode *n,BinTreeNode *r){
n->right=r;
if(r) r->parent=n;
}
// nにデータを設定する
void setData(BinTreeNode *n,void *d){
n->data=d;
}
Algorithms and Data Structures on C
BinTreeNodeの使い方
BinTreeNode *n1;
n1=makeBinTreeNode(makePD(“山田”,19));
NULL
BinTreeNode
parent
name=“山田”
age=19
void*
left
NULL
PD
right
NULL
BinTreeNode *n2;
n2=makeBinTreeNode(makePD(“森”,55));
単独ノードの
作成
Algorithms and Data Structures on C
BinTreeNodeの使い方
子ノードを持つ
ノードの作成
BinTreeNode *n3;
n3=makeBinTreeNode(makePD(“中村”,32),n1,n2);
NULL
BinTreeNode
parent
void*
left
parent
right
PD
parent
name=“山田”
age=19
void*
NULL
name=“中村”
age=32
BinTreeNode
BinTreeNode
left
PD
right
NULL
name=“森”
age=55
void*
left
NULL
PD
right
NULL
Algorithms and Data Structures on C
BinTree.h
#ifndef __BinTree__h
#define __BinTree__h
/***
*** 二分木
***/
#include "BinTreeNode.h"
// 二分木型
typedef struct {
BInTreeNode *root;
} BinTree;
続く
Algorithms and Data Structures on C
BinTree.h
// プロトタイプ宣言
BinTree *makeBinTree();
BinTree *makeBinTree(BinTreeNode*);
void freeBinTree(BinTree*);
void setRoot(BinTree*,BinTreeNode*);
void traverse(BinTree*,int,void(*)(void*));
#endif // __BinTree__h
Algorithms and Data Structures on C
BinTree.cc
/***
*** 二分木
***/
#include "BinTree.h"
// 生成
BinTree *makeBinTree(){
BinTree *t=(BinTree*)malloc(sizeof(BinTree));
t->root=NULL;
return t;
}
// 根ノードを指定して生成
BinTree *makeBinTree(BinTreeNode *r){
BinTree *t=(BinTree*)malloc(sizeof(BinTree));
t->root=r;
return t;
}
続く
Algorithms and Data Structures on C
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);
}
続く
Algorithms and Data Structures on C
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 traversePostOrderN(BinTreeNode *n,void(*func)(void*)){
if(n->left) traversePostOrder(n->left,func);
if(n->right) traversePostOrder(n->right,func);
func(n);
この関数は、木のノードを全部解放するために
}
内部的に使用する。
続く
Algorithms and Data Structures on C
BinTree.cc
// 破棄（中のノードも破棄する）
void freeBinTreeNode(void *n){
freeBinTreeNode((BinTreeNode*)n);
}
void freeBinTree(BinTree *t){
traversePostOrderN(t->root,freeBinTreeNode);
free(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;
}
}
Algorithms and Data Structures on C
BinTreeの使い方
根ノード付き
木の作成
BinTree *tree=makeBinTree(n6);
BinTree
root
n6
n5
n3
n1
n2
n4
Algorithms and Data Structures on C
BinTreeのなぞり
void printPD(void *pd){
print((PD*)pd);
printf(“ – ”);
}
...
traverse(tree,0,printPD);
木をなぞりつつ、毎回この関数が呼び出される。
そのとき、引数としてノードの持つデータが渡され
る。（ただしvoid*として）
Algorithms and Data Structures on C
TestBinTree.cc
/*** BinTreeのテスト ***/
#include "BinTree.h"
#include "PD.h"
void printPD(void* 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);
Algorithms and Data Structures on C
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");
freeBinTree(tree);
}
Algorithms and Data Structures on C
TestBinTreeの結果
$ TestBinTree
***Pre***
牧(30) - 中村(32) - 山田(18) - 森(55) - 今井(60) - 石田(27) ***In***
山田(18) - 中村(32) - 森(55) - 牧(30) - 今井(60) - 石田(27) ***Post***
山田(18) - 森(55) - 中村(32) - 石田(27) - 今井(60) - 牧(30) -
Algorithms and Data Structures on C
課題141215
• 右の個人情報の木構造を作成し表示せよ。
その後、40歳以上の人の年齢を5歳増や
し、再度表示せよ。
• “Add5PD.cc”とすること。
• 表示順は行きがけ順
• 以下の関数を作って使うこと
山田
(19)
• printPD() : PDを表示する
• addPD() : PDのうち40歳以上の年齢を+5する
森
(55)
• 提出方法：ワードで作成し、プログラムと実行結果を
張り付けること。（文字でも画像でもよい）
•
久永
(53)
プログラムは自分で作ってコードだけでよい。
• 提出先：[email protected]
• メールタイトル：”アルゴリズム課題141215”
• 提出期限：2014年12月21日（日）
牧
(33)
今井
(66)
中村
(35)
川平
(48)
石田
(27)
前田
(50)

Download Report