C++ | 31 | バイナツリー

<<前　 [TOP] 　次>>


Visual Studioで新規プロジェクトを作り、以下の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("C:\\test\\Data.txt",std::ios::in);

	while (fin>> buf1 >> buf2  >> buf3 >> buf4 >> zenki >> kouki >> report >> shutsuseki ){

                s1 = (char *)malloc( strlen(buf1) + 1 );
                strcpy_s(s1, strlen(buf1) + 1, buf1);

                s2 = (char *)malloc( strlen(buf2) + 1 );
                strcpy_s(s2, strlen(buf2) + 1,  buf2);

                s3 = (char *)malloc( strlen(buf3) + 1 );
                strcpy_s(s3, strlen(buf3) + 1, buf3);

                s4 = (char *)malloc( strlen(buf4) + 1 );
                strcpy_s(s4, strlen(buf4) + 1,  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]はCドライブの「test」フォルダに保存してあります。
【C:\test\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()関数は新しいセルのメモリの割り当てからツリー登録まですべて行うようにしています。


バイナリーツリーにはファイルから読み込んだ学生のデータを登録するようにしています。
これは成績をキー（鍵）にして登録します。
次に登録後キーボードから入力された値がツリーにあるか否かを表示し、ツリーにある場合にはその学生のデータをすべて表示します。


バイナツリー（二本木）はこれまでのデータ構造とは異なり、ソートなどにおいて最初から効率よくデータを格納するために考案されたものです。
その構成要素は双方向リンクリストと同じく、データへのポインタと自分自身を参照する２つのポインタからなっています。
違いは双方向リンクリストが同じ直線上の左右へのポインタによってつながっているのに対して、バイナツリーでは木のように広がっていく点にあります。


バイナツリーでは左側にデータを付け加えるか右側に付け加えるかをdataから導かれる値で判断します。
例えば学生のテストの点数で判断をするとします。
まず最初のデータは５０点だとすると、これが最初のツリーの根っこになります。
次にデータを登録する際にもし４０点ならば５０点より小さいので左に登録します。
次に４５点ならば５０点より小さいので左に行き、そこでは４０点が登録されているのでそれよりは大きいので右に登録します。


このように点数が小さいものは左に、点数が大きいものは右に登録するようにします。
うまくツリーが広がるように登録されればポインタをたどる回数はリンクリストよりも少なくなり、素早い登録が可能になります。

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;
　　　　　　　　}
　　　　}
}

実行結果を確認してください。

BtreeTest.cpp実行結果

↓↓クリックして頂けると励みになります。

<<前　 [TOP] 　次>>