0

我一直在尝试实现 BST，但在编译时一直遇到以下错误：

bstavl.cpp: In member function ‘bool BSTree::find(int)’:
bstavl.cpp:114:15: error: request for member ‘find’ in ‘((BSTree*)this)->BSTree::root->BSTNode::left’, which is of non-class type ‘BSTNode*’
bstavl.cpp:120:16: error: request for member ‘find’ in ‘((BSTree*)this)->BSTree::root->BSTNode::right’, which is of non-class type ‘BSTNode*’

我正在实现一个 BSTNode 结构，并且类 BSTree 使用 BSTNode 指针作为根。这是类和结构的声明：

struct BSTNode {
//---------------------------------------------------------------------
//instance variables 
int value; 
bool deleted;
struct BSTNode *left;
struct BSTNode *right;
int height;

//---------------------------------------------------------------------
//constructors

//non argumented constructor
BSTNode() {
    this->value     = 0;
    this->height    = 0;
    this->left      = NULL;
    this->right     = NULL;
    this->deleted   = false;
}

//given value
BSTNode(int value) {
    this->value     = value;
    this->height    = 0;
    this->left      = NULL;
    this->right     = NULL;
    this->deleted   = false;
}

//given value, left pointer, right pointer
BSTNode(int value, BSTNode *left, BSTNode *right) {
    this->value     = value;
    this->height    = 0;
    this->left      = left;
    this->right     = right;
    this->deleted   = false;
}
};

//=====================================================================

class BSTree : public BSTNode {
BSTNode *root;

public: 
BSTree();
BSTree(int);
bool isEmpty(); //check if the bst is empty
void insert(int newValue); //inserts an int into the bst. Returns success
bool find(int value); //searches bst for int. True if int is in tree
void preorder(); //calls recursive transversal
void inorder(); //calls recursive traversal
void postorder(); //calls recursive transversal
int height(BSTNode *n);
int totalheight(); //returns tot height. height of empty tree = -1
int totaldepth(); //returns tot depth. depth of empty tree = -1
int avgheight(); //returns avg height of tree
int avgdepth(); //returns avg depth of tree
bool remove(int value); //deletes int. returns true if deleted

private:
struct BSTNode* insertRecursive(struct BSTNode *n, int newValue);
void inorderRecursive(BSTNode *n); //traverses tree in inorder
void preorderRecursive(BSTNode *n); //traverses tree in preorder
void postorderRecursive(BSTNode *n); //traverses tree in preorder

};

最后，这是 BSTree::find 的实现

bool BSTree::find(int findMe){
if (root->value == findMe)
    return true;
else if (findMe < root->value){
    if (root->left != NULL)
        root->left.find(findMe);
    else
        return false;
}//else if
else if (findMe > root->value){
    if (root->right != NULL)
        root->right.find(findMe);
    else 
        return false;
}//else if
}//find

您必须提供的任何建议都会很棒。我试过换行

root->right.find(findMe);

各种各样的事情，包括

(root->right).find(findMe); 
root->right->find(findMe);
(root->right)->find(findMe);

还有很多其他的，但编译时出错。我知道这可能是某个地方的简单修复，但我已经花了几个小时在这个愚蠢的简单功能上，没有任何进展，这真的让我感到沮丧。谢谢！

4

1 回答 1

0

它基本上归结为BSTNode没有find方法的事实。

并且您的find方法当前使用root的是BSTNode.

我建议您不要让树继承节点。由于树不是节点（它只包含一个节点），因此这种继承并不是特别好。

而是创建另一个类BSTGeneric，您的所有树实现都将从其继承（类似的方法find将在这里，因为它对于所有 BST 看起来都是一样的，其他方法可以在这里声明为纯虚拟）。

然后，对于每个当前递归函数，添加另一个接受BSTNode *参数的函数，该参数应该是私有的，并让当前函数简单地调用它。

所以，而不是：

public: void insert(int value)
{
  ...
  root->left->insert(value);
  ...
}

我们会有：

public: void insert(int value)
{
  insert(root, value);
}

private: void insert(BSTNode n, int value)
{
  ...
  insert(n.left, value);
  ...
}
于 2013-10-06T00:39:13.873 回答