由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
CS版 - 问一个C++的binary search tree类实现问题 (转载)
相关主题
问一个C++的binary search tree类实现问题 (转载)面试时候C++ pop之前是空 大家怎么处理。。返回什么。。 假设stack 元素都是int形的。
问一个C++的binary search tree类实现问题leetcode上Symmetric Tree这道题怎么用iterative的方法做?
这段C++程序有错吗?拓扑排序
一小段程序,请诸位牛帮忙找下bug,谢谢![转载] 请问excel的null是什么符号?
相关话题的讨论汇总
话题: node话题: tree话题: search话题: null
进入CS版参与讨论
1 (共1页)
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
10
Thanks!

【在 n*******e 的大作中提到】
: http://stackoverflow.com/questions/495021/why-can-templates-onl
1 (共1页)
进入CS版参与讨论
相关主题
拓扑排序这段C++程序有错吗?
[转载] 请问excel的null是什么符号?一小段程序,请诸位牛帮忙找下bug,谢谢!
问一个C++的binary search tree类实现问题 (转载)面试时候C++ pop之前是空 大家怎么处理。。返回什么。。 假设stack 元素都是int形的。
问一个C++的binary search tree类实现问题leetcode上Symmetric Tree这道题怎么用iterative的方法做?
相关话题的讨论汇总
话题: node话题: tree话题: search话题: null