g**u 发帖数: 504 | 1 【 以下文字转载自 Computation 讨论区 】
发信人: gubu (法相), 信区: Computation
标 题: 问一个C++的binary search tree类实现问题
发信站: BBS 未名空间站 (Mon Jan 30 16:55:19 2012, 美东)
我想让search返回一个指向node的指针,下面代码编译有错误,不知道错在哪里?
错误提示是
error: expected constructor, destructor, or type conversion before ‘*’
token
search函数的实现如下:
template
BinarySearchTree::tree_node* BinarySearchTree::search(tree_node* p, T
d)
{
if(p==NULL||d==p->data)
return p;
else if(d>p->data)
return search(p->right,d);
else
return search(p->left,d);
}
下面是类的申明部分:
template
class BinarySearchTree
{
private:
struct tree_node
{
tree_node* left;
tree_node* right;
T data;
};
tree_node* root;
public:
BinarySearchTree()
{
root = NULL;
}
bool isEmpty() const { return root==NULL; }
void print_inorder();
void inorder(tree_node*);
void print_preorder();
void preorder(tree_node*);
void print_postorder();
void postorder(tree_node*);
void insert(T);
void remove(T);
tree_node* search(tree_node*,T);
void print_search(T);
}; |
d****n 发帖数: 1637 | 2 did you call this function out of main() ? |
g**u 发帖数: 504 | 3 yes, actually I call this function in another member function of the
BinarySearchTree class.
【在 d****n 的大作中提到】 : did you call this function out of main() ?
|
n*******e 发帖数: 62 | 4 你的tree_node 声明是私有的. 恐怕不能在公有函数接口用吧?
下面是类的申明部分:
template
class BinarySearchTree
{
〉〉〉〉〉〉〉private:
〉〉〉〉〉〉〉 struct tree_node
{
tree_node* left;
tree_node* right;
T data;
};
tree_node* root;
〉〉〉〉〉〉〉public:
。。。。。。。。。。。。
〉〉〉〉〉〉〉 tree_node* search(tree_node*,T);
void print_search(T);
};
【在 g**u 的大作中提到】 : yes, actually I call this function in another member function of the : BinarySearchTree class.
|
g**u 发帖数: 504 | 5 恩,后来我改成public了,还是不行,有jobhunting版的大牛跟我说不要用嵌套类,确
实不用嵌套类的话就可以了。但我还是想用嵌套类。其实我的search算法也就在
BinarySearchTree类里面用,我把它变成private了,但还是不行。修改后的类申明如
下:
template
class BinarySearchTree
{
public:
struct tree_node
{
tree_node* left;
tree_node* right;
T data;
};
public:
BinarySearchTree(){ root = NULL; }
bool isEmpty() const { return root==NULL; }
void insert(T);
void print_search(T);
private:
tree_node* search(tree_node*,T);
private:
tree_node* root;
};
那个search函数还是老样子如下:
template
BinarySearchTree::tree_node* BinarySearchTree::search(tree_node* p, T
d)
{
if(p==NULL||d==p->data)
return p;
else if(d>p->data)
return search(p->right,d);
else
return search(p->left,d);
}
【在 n*******e 的大作中提到】 : 你的tree_node 声明是私有的. 恐怕不能在公有函数接口用吧? : : 下面是类的申明部分: : template : class BinarySearchTree : { : 〉〉〉〉〉〉〉private: : 〉〉〉〉〉〉〉 struct tree_node : { : tree_node* left;
|
g**u 发帖数: 504 | 6 我把完整代码贴出来吧,这个是BSTree.h文件如下:
#include
#include
using namespace std;
template
class BinarySearchTree
{
public:
struct tree_node
{
tree_node* left;
tree_node* right;
T data;
};
public:
BinarySearchTree(){ root = NULL; }
bool isEmpty() const { return root==NULL; }
void insert(T);
void print_search(T);
private:
tree_node* search(tree_node*,T);
private:
tree_node* root;
};
template
void BinarySearchTree::insert(T d)
{
tree_node* t = new tree_node;
tree_node* parent;
t->data = d;
t->left = NULL;
t->right = NULL;
parent = NULL;
// is this a new tree?
if(isEmpty()) root = t;
else
{
//Note: ALL insertions are as leaf nodes
tree_node* curr;
curr = root;
// Find the Node's parent
while(curr!=NULL)
{
parent = curr;
if(t->data > curr->data) curr = curr->right;
else curr = curr->left;
}
if(t->data > parent->data)
parent->right = t;
else
parent->left = t;
}
}
template
void BinarySearchTree::print_search(T d)
{
if(search(root,d)==NULL)
cout<<" data not found"<
else
cout<<" data is found"<
}
template
BinarySearchTree::tree_node* BinarySearchTree::search(tree_node* p, T
d)
{
if(p==NULL||d==p->data)
return p;
else if(d>p->data)
return search(p->right,d);
else
return search(p->left,d);
}
还有很郁闷的是用了template之后,不能把这个类分写在BSTree.h和BSTree.cpp里了,
如果把类函数写到BSTree.cpp里,main函数里有调用那些函数的话编译就会出错。
【在 n*******e 的大作中提到】 : 你的tree_node 声明是私有的. 恐怕不能在公有函数接口用吧? : : 下面是类的申明部分: : template : class BinarySearchTree : { : 〉〉〉〉〉〉〉private: : 〉〉〉〉〉〉〉 struct tree_node : { : tree_node* left;
|
d****n 发帖数: 1637 | 7 In your search function, you need to use the typename keyword to give
the compiler the extra hint that BinarySearchTree::tree_node is a
type. Node in your class class is still an incomplete type with template
type in. In VC it may work without typename.(not tested)
template
typename BinarySearchTree::tree_node*
BinarySearchTree::search(tree_node* p, T d)
{
if(p==NULL||d==p->data)
return p;
else if(d>p->data)
return search(p->right,d);
else
return search(p->left,d);
}
it will work using g++ under linux.
【在 g**u 的大作中提到】 : 我把完整代码贴出来吧,这个是BSTree.h文件如下: : #include : #include : using namespace std; : template : class BinarySearchTree : { : public: : struct tree_node : {
|
n*******e 发帖数: 62 | |
g**u 发帖数: 504 | 9 Thanks! It works!
【在 d****n 的大作中提到】 : In your search function, you need to use the typename keyword to give : the compiler the extra hint that BinarySearchTree::tree_node is a : type. Node in your class class is still an incomplete type with template : type in. In VC it may work without typename.(not tested) : template : typename BinarySearchTree::tree_node* : BinarySearchTree::search(tree_node* p, T d) : { : if(p==NULL||d==p->data) : return p;
|
g**u 发帖数: 504 | |