c++ - 用 C++ 实现 AVL 添加？

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


};

希望对您有所帮助!