Binary Treeの実装

shu — Tue, 23 Sep 2008 11:43:00 +0000

今日はアルゴリズム、データ構造の勉強。
BinaryTreeのInsert部分だけ作ってみた

#include 

template class BinaryTree
{
template  class Element{
public:
Element()
:parent(NULL),child_less(NULL),child_more(NULL)
{
};
~Element(){ 
delete child_less;
delete child_more;
};

Element* parent;
Element* child_less;
Element* child_more;
T  obj;
};
public:
BinaryTree(void)
:m_first(NULL)
{
}

~BinaryTree(void){
delete m_first;
};

int Insert(const T& obj){
Element *el = new Element();
el->obj = obj;

if( !m_first ){
m_first = el;
return 1;
}

return CheckAndInsertObject( m_first , el ); 
};

private:
Element* m_first;

int CheckAndInsertObject( Element* target_el, Element* new_el ){
if( !target_el ){
return 0;
}

if( target_el->obj < new_el->obj ){
if( target_el->child_more ){
return CheckAndInsertObject( target_el->child_more , new_el );
}
else{
target_el->child_more = new_el;
new_el->parent = target_el;
return 1;
}

}
else if( target_el->obj > new_el->obj ){
if( target_el->child_less ){
return CheckAndInsertObject( target_el->child_less , new_el );
}
else{
target_el->child_less = new_el;
new_el->parent = target_el;
return 1;
}
}

delete new_el;
return 0;

};
};

JugglerShu.Net » Data Structure

Binary Treeの実装