二分探索木のサンプルコード

初めに

練習に二分探索木を使った、連想配列を作りました。
keyがstd::stringでdataがlongです。
自己責任でお使いください。

ソース

main.cpp

#include <cstdio>
#include <cmath>
#include <cstring>
#include <iostream>
#include <vector>
#include <fstream>
#include <string>
#include <sstream>


class tree2{	
	
public:
	
struct one_tree{
	std::string name;
	long data;
	one_tree* R_next;//大きい
	one_tree* L_next;//小さい
};

one_tree* tree_data;

one_tree* Get_one_tree(){
	one_tree* temp=new one_tree;
	temp->data=0L;
	temp->name="";
	temp->R_next=temp->L_next=NULL;
	return temp;
};


tree2(){
	tree_data=NULL;
}

one_tree* search(one_tree* tree_data2,std::string name){
	
	if(tree_data2==NULL){
		return NULL;
	}
	else{
		int temp=strcmp(tree_data2->name.c_str(),name.c_str());
		
		if(temp==0){
			return tree_data2;
		}
		else if(temp>0){
			return search(tree_data2->L_next,name);	
		}
		else if(temp<0){
			return search(tree_data2->R_next,name);			
		}
	}
	
}

one_tree* search(std::string name){
	
	if(tree_data==NULL){
		return NULL;
	}
	else{
		int temp=strcmp(tree_data->name.c_str(),name.c_str());
		
		if(temp==0){
			return tree_data;
		}
		else if(temp>0){
			return search(tree_data->L_next,name);
		}
		else if(temp<0){
			return search(tree_data->R_next,name);			
		}
	}
	
}
//検索関数

one_tree** search2(one_tree** tree_data3,one_tree* tree_data2,std::string name){
	
	if(tree_data2==NULL){
		return tree_data3;
	}
	else{
		int temp=strcmp(tree_data2->name.c_str(),name.c_str());
		
		if(temp>0){
				return search2(&(tree_data2->L_next),tree_data2->L_next,name);	
		}
		else if(temp<0){
				return search2(&(tree_data2->R_next),tree_data2->R_next,name);				
		}
	}
	
}

one_tree** search2(std::string name){
	
	if(tree_data==NULL){
		return &tree_data;
	}
	else{
		int temp=strcmp(tree_data->name.c_str(),name.c_str());
		
		if(temp>0){
			return search2(&(tree_data->L_next),tree_data->L_next,name);
		}
		else if(temp<0){
			return search2(&(tree_data->R_next),tree_data->R_next,name);			
		}
	}
	
}
//追加用検索関数

void add(std::string name,long data){
	
	if(search(name)==NULL){
		one_tree** temp=search2(name);
		*temp=Get_one_tree();
		(*temp)->name=name;
		(*temp)->data=data;
	}
	
}
//追加

void Dprint(one_tree* tree_data2){
	
	if(tree_data2==NULL)return;
	
	std::cout<<tree_data2->name<<","<<tree_data2->data<<std::endl;
	
	Dprint(tree_data2->R_next);
	Dprint(tree_data2->L_next);	
}

void Dprint(){
	
	if(tree_data==NULL)return;
	
	std::cout<<tree_data->name<<","<<tree_data->data<<std::endl;
	
	Dprint(tree_data->R_next);
	Dprint(tree_data->L_next);
}
//デバッグ用

void all_delete(one_tree* tree_data2){
	
	if(tree_data2==NULL)return;
	
	delete tree_data2;
	
	all_delete(tree_data2->R_next);
	all_delete(tree_data2->L_next);
		
};

void all_delete(){
	
	if(tree_data==NULL)return;
	
	delete tree_data;
	
	all_delete(tree_data->R_next);
	all_delete(tree_data->L_next);
};
//メモリー開放

~tree2(){
	all_delete();
}

};

使い方

main.cpp

//main.cppの続き
int main(){
    tree2 a;

    a.add("key",100);
    a.add("key2",130);

    std::cout << a.search("key")->data<<std::endl;//100


}

Q:メモリー、開放してないじゃん!

自作しましょう。(作るのが面倒だった)

2017年10月18日:追記

メモリーを開放するようにしました。