c++ - 在头文件中引用 ADT

Question

我正在尝试用 C++ 实现二叉搜索树(用于大学类(class))，但在访问我在 .h 文件中定义的结构时遇到了一些困难。
这是我的 .h 文件:

class BST
{
    protected:
        struct node 
        {
            int data;
            node* left;
            node* right;
        };
        node* insert(int x, node* t);
        node* root;
       
    public:
        BST();
        void insert(int x);
};

和实现文件:

    node* BST::insert(int x, node* t)
    {
        if(t == NULL)
        {
            t = new node;
            t->data = x;
            t->left = t->right = NULL;
        }
        else if(x < t->data)
            t->left = insert(x, t->left);
        else if(x > t->data)
            t->right = insert(x, t->right);
        return t;
    }

节点结构在 .h 文件中定义，用作插入函数的返回类型。它也在插入函数本身中使用。我的问题是当前的方法签名导致 2 个错误:

unknown type name 'node'

随着:

cannot initialize return object of type int* with an lvalue of type BST::node *

但是，如果我将方法签名更改为:

    BST::node* BST::insert(int x, node* t)

错误已解决。我明白为什么这会解决有关返回类型的错误，但在函数本身中，我有一个使用该数据类型的变量:

t = new node

如果前面没有额外的 BST::，怎么知道节点是什么数据类型？

Answer 1

如果您在类定义之外定义函数，则在定义类的封闭命名空间中搜索用作返回类型的非限定名称节点。
在函数声明符和函数体内，从类定义开始搜索非限定名称节点(假设函数中使用的名称未在封闭块之一中重新声明。否则名称将从该嵌套块开始搜索)。