↓↓クリックして頂けると励みになります。
【27 | ファイルへの書き込み】 << 【ホーム】 >> 【29 | 関数ポインター】
C++の「バイナリーツリー」は、データを効率的に格納し、検索や挿入、削除などの操作を高速に行うためのデータ構造です。
バイナリーツリーは、各ノードが最大で2つの子ノードを持つツリー構造であり、左の子ノードは親ノードより小さな値を持ち、右の子ノードは親ノードより大きな値を持ちます。
この性質により、データが整列された状態で格納されることが重要です。
C++において、バイナリーツリーを実装する際には、通常、ポインターを使用して各ノードを表します。
これにより、ツリーの挿入、削除、検索などの操作を行う際に、効率的にツリーを操作できます。
また、バイナリーツリーはバイナリーサーチツリー（BST）とも呼ばれ、データの検索において特に高速な性能を発揮します。
Visual Studio Codeで以下のcppファイルを作成して下さい。
新規作成 【BtreeTest.cpp】
#include<iostream> #include <stdio.h> #include <stdlib.h> #include<string.h> #include<fstream> /*header of BTREE*/ typedef struct BTREE { struct BTREE *left; struct BTREE *right; void *name; void *nyuugaku_nen; void *kumi; void *gakunen; int point; }Btree; static Btree *root=NULL; Btree *newCell(int point,void *name,void *nyuugaku_nen,void *kumi,void *gakunen); Btree *addCell(int point, void *name, void *nyuugaku_nen, void *kumi, void *gakunen); int search( int newl); Btree *newCell(int point,void *name,void *nyuugaku_nen,void *kumi,void *gakunen){ Btree *p; p = (Btree *)malloc(sizeof(Btree)); p->left=NULL; p->right=NULL; p->name=name; p->nyuugaku_nen=nyuugaku_nen; p->kumi=kumi; p->gakunen=gakunen; p->point=point; return p; } Btree *addCell(int point, void *name, void *nyuugaku_nen, void *kumi, void *gakunen) { Btree **bp,*newl=NULL; bp=&root; if(root==NULL) { root=(Btree*)malloc(sizeof(Btree)); root= newCell(point, name,nyuugaku_nen,kumi,gakunen); } else { while(true){ if(*bp==NULL) { newl=(Btree*)malloc(sizeof(Btree)); newl= newCell(point, name,nyuugaku_nen,kumi,gakunen); *bp=newl; break; } if((*bp)->point < point) { bp=&(*bp)->left; } else { bp=&(*bp)->right; } } } return newl; } /*Treeに値newlがあれば1を返し、無ければ0を返す。*/ int search( int newl) { Btree *bp=root; while(1) { if(root==NULL){ return 0; } if(root->point==newl){ return 1; } else if(root->point < newl) { root=root->left; } else { root=root->right; } } } int main() { char *s1; char *s2; char *s3; char *s4; int point; int input; char buf1[512]; char buf2[512]; char buf3[512]; char buf4[512]; int zenki; int kouki; int report; int shutsuseki; std::ifstream fin; fin.open("Data.txt",std::ios::in); while (fin>> buf1 >> buf2 >> buf3 >> buf4 >> zenki >> kouki >> report >> shutsuseki ){ s1 = (char *)malloc( strlen(buf1) + 1 ); strcpy(s1, buf1); s2 = (char *)malloc( strlen(buf2) + 1 ); strcpy(s2, buf2); s3 = (char *)malloc( strlen(buf3) + 1 ); strcpy(s3, buf3); s4 = (char *)malloc( strlen(buf4) + 1 ); strcpy(s4, buf4); point =(zenki+(kouki/2)+(report*2)+(shutsuseki*20/15))/2; addCell(point,s1,s2,s3,s4); } std::cout << "検索したい点数を入力してください-->"; std::cin >> input; std::cin.clear(); std:: cin.ignore(); int flag = search(input); if(flag==1) { std::cout << (char *)(root->name) << std::endl; std::cout << (char *)(root->nyuugaku_nen) << std::endl; std::cout << (char *)(root->kumi) << std::endl; std::cout << (char *)(root->gakunen) << std::endl; std::cout << root->point << std::endl; } else { std::cout << "入力された点数はリストにありません" << std::endl; } }
以下の内容の「Data.txt」を読み込んでいます。
【Data.txt】
yamada 2001 1 1 70 65 15 15 suzuki 2001 2 3 80 90 10 13 satou 2001 3 2 80 60 13 12 tanaka 2000 11 1 65 70 12 15
バイナツリーにデータをポインタを使って登録するような一般的なプログラムです。
ただしバイナツリーに登録に必要な値は整数とし、以下のように登録する際にはデータへのポインタとその値とを引数に与えるようにしています。
なお便利にするため、addCell()関数は新しいセルのメモリの割り当てからツリー登録まですべて行うようにしています。
バイナリーツリーにはファイルから読み込んだ学生のデータを登録するようにしています。
これは成績をキー（鍵）にして登録します。
次に登録後キーボードから入力された値がツリーにあるか否かを表示し、ツリーにある場合にはその学生のデータをすべて表示します。
バイナツリー（二本木）はこれまでのデータ構造とは異なり、ソートなどにおいて最初から効率よくデータを格納するために考案されたものです。
その構成要素は双方向リンクリストと同じく、データへのポインタと自分自身を参照する2つのポインタからなっています。
違いは双方向リンクリストが同じ直線上の左右へのポインタによってつながっているのに対して、バイナツリーでは木のように広がっていく点にあります。
バイナツリーでは左側にデータを付け加えるか右側に付け加えるかをdataから導かれる値で判断します。
例えば学生のテストの点数で判断をするとします。
まず最初のデータは50点だとすると、これが最初のツリーの根っこになります。
次にデータを登録する際にもし40点ならば50点より小さいので左に登録します。
次に45点ならば50点より小さいので左に行き、そこでは40点が登録されているのでそれよりは大きいので右に登録します。
このように点数が小さいものは左に、点数が大きいものは右に登録するようにします。
うまくツリーが広がるように登録されればポインタをたどる回数はリンクリストよりも少なくなり、素早い登録が可能になります。
struct BTREE { struct BTREE *left, *right; int point; }; typedf struct BTREE Btree; static BTree *root=NULL;
バイナツリーにおいても木の根っこへのポインタは保持していなければなりません。
上の例ではstaticに保持するようにしていますが、呼び出す側のプログラムで保持する場合もあります。
この例では格納するデータは直接pointに整数型で入れていますが、当然ポインタを使って「void *data;」のように本来は持つべきです。
最初は要素がないのでrootにはNULLを入れておきます。
バイナツリーの要素は次のようにして生成します。
Btree *newCell( int point ) { Btree *bp; bp = (Btree *)malloc(sizeof(Btree)); bp->point = point; bp->left=NULL; bp->right = NULL; return bp; }
こうして生成したツリーに追加するには、以下のような手順になります。
1.rootがNULLならばそこにぶら下げます。
2.そうでなければpointを比較して、小さければ左に進み大きければ右に進みます。
3.以上を繰り返してNULLポインタであればそこに登録します。
こうして作成したバイナツリーは検索に利用することができます。
検索手順は与えられた値と現在のポインタの示す要素に格納されている値とを比較し、小さければ左に進み大きければ右に進みます。
同じ値があればそこで検索は終了し、進むべき道がなければ該当する値は存在しないことになります。
/* Treeに値newlがあれば１を返し、なければ０を返します。 */ int search( int newl ) { Btree *bp = root; while(1) { if(bp==NULL){ return 0; } if(bp->point == newl){ return 1; } else if(bp->point < newl) { bp = bp->left; } else{ bp=bp->right; } } }
実行結果を確認してください。
~/Desktop/Programming/CPP $ cd "/Users/**/Desktop/Programming/CPP/" && g++ BtreeTest.cpp -o BtreeTest && "/Users/**/Desktop/Programming/CPP/"BtreeTest 検索したい点数を入力してください-->81 suzuki 2001 2 3 81
【27 | ファイルへの書き込み】 << 【ホーム】 >> 【29 | 関数ポインター】
↓↓クリックして頂けると励みになります。
