在头文件中引用ADT

Question

我正试图在c++中实现二叉搜索树(用于大学课程)，并且我在访问。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

如果在类定义之外定义函数，则在定义类的封闭名称空间中搜索用作返回类型的非限定名称节点。

在函数声明器和函数体中，从类定义开始搜索非限定名节点(前提是函数中使用的名称没有在一个封闭块中重新声明)。否则，从这个嵌套块开始搜索名称)。