私はAVLツリーを実装し、テンプレートがどのように機能するかを理解しようとしているので、ツリーにさまざまなタイプのデータを格納できます。現在、intしか格納できませんが、必要に応じて他のタイプも格納できるようにしたいと思います。このためにテンプレートをどのように使用しますか?
今、これは私が持っているクラスです:
struct Avlnode{
int data;
int balfact;
Avlnode *left;
Avlnode *right;
};
class Avltree{
public:
Avltree();
~Avltree( );
Avlnode* insert(int i, bool* j);
static Avlnode* buildtree ( Avlnode *root, int data, bool *h ) ;
void display( Avlnode *root );
Avlnode* deldata ( Avlnode* root, int data, bool *h );
static Avlnode* del ( Avlnode *node, Avlnode* root, bool *h );
static Avlnode* balright ( Avlnode *root, bool *h );
static Avlnode* balleft ( Avlnode* root, bool *h );
void setroot ( Avlnode *avl );
static void deltree ( Avlnode *root );
private:
Avlnode *root;
int items;
};
そしてそれらは定義されています:
Avltree::Avltree( ){
root = NULL;
items = 0;
}
Avlnode* Avltree::insert( int data, bool *h ){
root = buildtree( root, data, h );
return root;
}
Avlnode* Avltree::buildtree( Avlnode *root, int data, bool *h ){
Avlnode *node1, *node2;
if( root == NULL ){
root = new Avlnode;
root -> data = data;
root -> left = NULL;
root -> right = NULL;
root -> balfact = 0;
*h = true;
return( root );
}
if ( data < root -> data ){
root -> left = buildtree( root -> left, data, h );
// If left subtree is higher
if( *h ){
switch ( root -> balfact ){
case 1:
node1 = root -> left;
if ( node1 -> balfact == 1 ){
//cout << "\nRight rotation.";
root -> left = node1 -> right;
node1 -> right = root;
root -> balfact = 0;
root = node1;
}
else{
//cout << "\nDouble rotation, left then right." ;
node2 = node1 -> right;
node1 -> right = node2 -> left;
node2 -> left = node1;
root -> left = node2 -> right;
node2 -> right = root;
if ( node2 -> balfact == 1 )
root -> balfact = -1;
else
root -> balfact = 0;
if ( node2 -> balfact == -1 )
node1 -> balfact = 1;
else
node1 -> balfact = 0;
root = node2;
}
root -> balfact = 0;
*h = false;
break;
case 0:
root -> balfact = 1;
break;
case -1:
root -> balfact = 0;
*h = false;
}
}
}
if ( data > root -> data ){
root -> right = buildtree ( root -> right, data, h );
if ( *h ){
switch ( root -> balfact ){
case 1:
root -> balfact = 0;
*h = false;
break;
case 0:
root -> balfact = -1;
break;
case -1:
node1 = root -> right;
if ( node1 -> balfact == -1 ){
//cout << "\nLeft rotation.";
root -> right = node1 -> left;
node1 -> left = root;
root -> balfact = 0;
root = node1;
}
else{
//cout << "\nDouble rotation, right then left.";
node2 = node1 -> left;
node1 -> left = node2 -> right;
node2 -> right = node1;
root -> right = node2 -> left;
node2 -> left = root;
if ( node2 -> balfact == -1 )
root -> balfact = 1;
else
root -> balfact = 0;
if ( node2 -> balfact == 1 )
node1 -> balfact = -1;
else
node1 -> balfact = 0;
root = node2;
}
root -> balfact = 0;
*h = false;
}
}
}
return ( root );
}
void Avltree::display ( Avlnode* root ){
if ( root != NULL ){
display ( root -> left );
cout << root -> data << "\t";
display ( root -> right );
}
}
Avlnode* Avltree::deldata ( Avlnode *root, int data, bool *h ){
Avlnode *node;
if ( root -> data == 13 )
cout << root -> data ;
if ( root == NULL ){
//cout << "\nNo such data.";
return ( root );
}
else{
if ( data < root -> data ){
root -> left = deldata ( root -> left, data, h ) ;
if ( *h )
root = balright ( root, h ) ;
}
else{
if ( data > root -> data ){
root -> right = deldata ( root -> right, data, h ) ;
if ( *h )
root = balleft ( root, h );
}
else{
node = root;
if ( node -> right == NULL ){
root = node -> left ;
*h = true ;
delete ( node ) ;
}
else{
if ( node -> left == NULL ){
root = node -> right ;
*h = true ;
delete ( node ) ;
}
else{
node -> right = del ( node -> right, node, h ) ;
if ( *h )
root = balleft ( root, h ) ;
}
}
}
}
}
return ( root ) ;
}
Avlnode* Avltree :: del ( Avlnode *succ, Avlnode *node, bool *h ){
Avlnode *temp = succ ;
if ( succ -> left != NULL ){
succ -> left = del ( succ -> left, node, h ) ;
if ( *h )
succ = balright ( succ, h ) ;
}
else{
temp = succ ;
node -> data = succ -> data ;
succ = succ -> right ;
delete ( temp ) ;
*h = true ;
}
return ( succ ) ;
}
Avlnode* Avltree :: balright ( Avlnode *root, bool *h ){
Avlnode *temp1, *temp2 ;
switch ( root -> balfact ){
case 1 :
root -> balfact = 0 ;
break ;
case 0 :
root -> balfact = -1 ;
*h = false ;
break ;
case -1 :
temp1 = root -> right ;
if ( temp1 -> balfact <= 0 ){
cout << "\nLeft rotation." ;
root -> right = temp1 -> left ;
temp1 -> left = root ;
if ( temp1 -> balfact == 0 ){
root -> balfact = -1 ;
temp1 -> balfact = 1 ;
*h = false ;
}
else{
root -> balfact = temp1 -> balfact = 0 ;
}
root = temp1 ;
}
else{
cout << "\nDouble rotation, right then left." ;
temp2 = temp1 -> left ;
temp1 -> left = temp2 -> right ;
temp2 -> right = temp1 ;
root -> right = temp2 -> left ;
temp2 -> left = root ;
if ( temp2 -> balfact == -1 )
root -> balfact = 1 ;
else
root -> balfact = 0 ;
if ( temp2 -> balfact == 1 )
temp1 -> balfact = -1 ;
else
temp1 -> balfact = 0 ;
root = temp2 ;
temp2 -> balfact = 0 ;
}
}
return ( root ) ;
}
Avlnode* Avltree::balleft ( Avlnode *root, bool *h ){
Avlnode *temp1, *temp2 ;
switch ( root -> balfact ){
case -1 :
root -> balfact = 0 ;
break ;
case 0 :
root -> balfact = 1 ;
*h = false ;
break ;
case 1 :
temp1 = root -> left ;
if ( temp1 -> balfact >= 0 ){
cout << "\nRight rotation." ;
root -> left = temp1 -> right ;
temp1 -> right = root ;
if ( temp1 -> balfact == 0 ){
root -> balfact = 1 ;
temp1 -> balfact = -1 ;
*h = false ;
}
else{
root -> balfact = temp1 -> balfact = 0 ;
}
root = temp1 ;
}
else{
cout << "\nDouble rotation, left then right." ;
temp2 = temp1 -> right ;
temp1 -> right = temp2 -> left ;
temp2 -> left = temp1 ;
root -> left = temp2 -> right ;
temp2 -> right = root ;
if ( temp2 -> balfact == 1 )
root -> balfact = -1 ;
else
root -> balfact = 0 ;
if ( temp2-> balfact == -1 )
temp1 -> balfact = 1 ;
else
temp1 -> balfact = 0 ;
root = temp2 ;
temp2 -> balfact = 0 ;
}
}
return ( root ) ;
}
void Avltree::setroot ( Avlnode *avl ){
root = avl ;
}
Avltree::~Avltree( ){
deltree ( root ) ;
}
void Avltree::deltree ( Avlnode *root ){
if ( root != NULL ){
deltree ( root -> left ) ;
deltree ( root -> right ) ;
}
delete ( root ) ;
}