Реализация AVL add с C++?

Question

Я пытаюсь реализовать дерево AVL и, похоже, имеет проблемы с тем, как я использую класс Node. Я получаю ошибку C4430: отсутствующий спецификатор типа со вторым getHeight. Я думал, что я задал тип как узел для поддерева?

template <typename T> 
class SetAVL 
{ 
public: 
int getHeight() 
{ 
    return getHeight(root); 
} 
// Complaining about this line 
int getHeight(const Node<T> *subtree) 
{ 
    // If we are at a leaf 
    if (subtree == NULL) 
     return 0; 

    return 1 + max(getHeight(subtree->left), getHeight(subtree->right)); 
} 

void add(Node<T> *item) 
{ 
    Node<T> *t = new Node<T>(item); 
    insert(root, t); 
} 

void insert(Node<T> *root, Node<T> *t) 
{ 
    if (root == NULL) 
     root = t; 
    else 
    { 
     if (t->item < root->item) 
      insert(root->left, t); 
     else if (t->item != root->item) 
      insert(root->right, t); 
     else 
      delete t; 
    } 
} 

protected: 
    template <typename T> 
    class Node 
    { 
    public: 
     T item; 
     Node *left; 
     Node *right; 
     int height; 

     Node(T item) 
     { 
      this->item = item; 
      this->left = NULL; 
      this->right = NULL; 
      this->height = 0; 
     } 
    } 

    Node<T> *root; 
    int treeSize; 
} 

Answer 1

Кажется нужно указать правильный тип для левой и правой точки

Node *left; 
Node *right; 

должен быть

Node<T> *left; 
Node<T> *right; 

я переехал определение узла перед его использованием. Кстати, вы потеряли ';' в конце определения узла класса.

template <typename T> 
class SetAVL 
{ 
protected: 
    template <typename T> 
    class Node 
    { 
    public: 
     T item; 
     Node<T> *left; 
     Node<T> *right; 
     int height; 

     Node(T item) 
     { 
      this->item = item; 
      this->left = NULL; 
      this->right = NULL; 
      this->height = 0; 
     } 
    }; 

    Node<T> *root; 
    int treeSize; 
public: 
    int getHeight() 
    { 
     return getHeight(root); 
    } 

    int getHeight(const Node<T> *subtree) 
    { 
     // If we are at a leaf 
     if (subtree == NULL) 
      return 0; 

     return 1 + max(getHeight(subtree->left), getHeight(subtree->right)); 
    } 

    void add(Node<T> *item) 
    { 
     Node<T> *t = new Node<T>(item); 
     insert(root, t); 
    } 

    void insert(Node<T> *root, Node<T> *t) 
    { 
     if (root == NULL) 
      root = t; 
     else 
     { 
      if (t->item < root->item) 
       insert(root->left, t); 
      else if (t->item != root->item) 
       insert(root->right, t); 
      else 
       delete t; 
     } 
    } 


}; 

Надеюсь, это поможет!