2

我正在尝试实现 AVL 树，但似乎在使用 Node 类时遇到了问题。我收到错误 C4430: missing type specifier with the second 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;
}
4

1 回答 1

2

似乎需要为左右点指定正确的类型

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


};

希望能帮助到你！

于 2012-06-04T02:06:00.137 回答