如何在C++中使用模板<typename>

Question

我正在實現一個AVL樹並試圖瞭解模板如何工作，以便我可以在我的樹中存儲不同類型的數據。現在我只能存儲int，但我希望能夠存儲其他類型，如果我需要。我將如何使用模板？

眼下這是I類有：

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

Answer 1

首先要Avlnode類模板：

template<typename T> 
struct Avlnode{ 
    typedef value_type T; 
    value_type data; 
    value_type balfact; 
    Avlnode<T> *left; 
    Avlnode<T> *right; 
}; 

然後，使Avltree一個班級模板：

template <typename T> 
class Avltree{ 
public: 
typedef T value_type; 
typedef node_type Avlnode<T>; 
Avltree(); 
~Avltree(); 
node_type* insert(const T& i, bool* j); 
static node_type* buildtree (node_type*root, const T& data, bool *h) ; 
void display(node_type*root); 
node_type* deldata (node_type* root, const T& data, bool *h); 
static node_type* del (node_type* node, node_type* root, bool *h); 
.... 
private: 
node_type *root; 
T items; 
}; 

然後，以實例：

Avltree<float> treeF; 
bool smth = true; 
typename AvlTree<float>::node_type* node = treeF.insert(0.5, &smth); 

雖然我會建議供參考，而不是指針傳遞bools。