学生向けプログラミング入門 | 無料

学生向けにプログラミングを無料で解説。Java、C++、Ruby、PHP、データベース、Ruby on Rails, Python, Django

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

void 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()関数は新しいセルのメモリの割り当てからツリー登録まですべて行うようにしています。


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


バイナツリー(二本木)はこれまでのデータ構造とは異なり、ソートなどにおいて最初から効率よくデータを格納するために考案されたものです。
その構成要素は、双方向リンクリストと同じく、データへのポインタと、自分自身を参照する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があれば1を返し、なければ0を返します。 */

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



実行結果です。





<<前  [TOP]  次>>