头文件：
#ifndef AVLTREE_H
#define AVLTREE_H
template
class avlNode
{
public:
T element;
avlNode *left;
avlNode *right;
int tree_height;
avlNode(const T&item, avlNode *lt, avlNode *rt, int th = 0) :element(item), left(lt), right(rt), tree_height(th){}
};
template
class avlTree
{
public:
avlTree();
void rotateLeftChild(avlNode *&node);
void doubleRotateLeftChild(avlNode *&node);
void rotateRightChild(avlNode *&node);
void doubleRotateRightChild(avlNode *&node);
void insert(const T & item,avlNode *&node);
int height(avlNode *node){ return (node == NULL) ? -1 : node->tree_height; }
private:
avlNode<T> *root;
};
#endif
源文件：
#include "avlTree.h"
template
void avlTree::insert(const T &item,avlNode *&node)
{
if (node==NULL)
{
node = new avlNode(item, NULL, NULL);
}
else if (node->element
{
insert(item, node->right);
if (height(node->right)-height(node->left)==2)
{
if (node->right->element
{
rotateRightChild(node);
}
else doubleRotateRightChild(node);
}
}
else if (node->element>item)
{
insert(item, node->left);
if (height(node->left)-height(node->right)==2)
{
if (node->left->element>item)
{
rotateLeftChild(node);
}
else doubleRotateLeftChild(node);
}
}
node->tree_height = max(height(node->left), height(node->right)) + 1;
}
template
void avlTree::rotateLeftChild(avlNode *&node)
{
avlNode *temp = node->left;
node->left = temp->right;
temp->right = node;
node->tree_height = max(height(node->left), height(node->right)) + 1;
temp->tree_height = max(height(temp->left), node->tree_height) + 1;
node = temp;
}
template
void avlTree::rotateRightChild(avlNode *&node)
{
avlNode *temp = node->right;
node->right = temp->left;
temp->left = node;
node->tree_height = max(height(node->left), height(node->right)) + 1;
temp->tree_height = max(node->tree_height, height(temp->right)) + 1;
node = temp;
}
template
void avlTree::doubleRotateLeftChild(avlNode *&node)
{
rotateRightChild(node->left);
rotateLeftChild(node);
}
template
void avlTree::doubleRotateRightChild(avlNode *&node)
{
rotateLeftChild(node->right);
rotateRightChild(node);
}
编译报错：error C2955: “avlNode”: 使用 类 模板 需要 模板 参数列表，但是只指示insert成员函数那里有问题，
