0

我正在制作一个二进制搜索树（简称BST ），但遇到了一个我无法弄清楚的问题。

我将尝试减少代码量，但恐怕仍然需要相当多的时间。

节点：

template <typename Type>
class BSTNode {          // Binary Search Tree nodes
    private:
        int key;        // we search by key, no matter what type of data we have
        Type data;
        BSTNode *left;
        BSTNode *right;

    public:

        BSTNode (int, Type); 
        bool add (int, Type);
        Type search (int);
        BSTNode<Type> *remove (int, BSTNode*);   
        BSTNode<Type> *minNode (int);                                                
};

根：

template <typename Type>
class BST {                    // The binary search tree containing nodes
    private:
        BSTNode<Type> *root;   // Has reference to root node

    public:

        BST ();
        bool add (int, Type);
        Type search (int);
        bool remove (int);

};

我不知道要给出多少代码，因为我不想夸大其词，如果您需要更多代码，请说出来。

我都做递归搜索和删除

template<typename Type>
BSTNode<Type> *BSTNode<Type>::remove(int removeKey, BSTNode *parent) {

     // Here I try to remove nodes
     // Depending on the number of children a node has, I remove in different ways
     // The error occurs at removing a node with 2 children
     // here I look for smallest node greater than current node, replace current node, delete node I replaced WITH

    if (this->left != NULL && this->right != NULL){

        int *auxKey = &key;

        this = this->right->minNode(auxKey);  // replace

        return this->right->remove(this->key, this); // remove old node
    }
}

这是minNode：

template<typename Type>
Type *BSTNode<Type>::minNode (int oldKey) {
    if (this->left == NULL) {
        //oldKey = this->key;
        return this->data;
    } else
        return left->minNode();
}

这是发生错误的地方：

this = right->minNode(auxKey);

这会导致一系列错误，但我认为主要错误是：

error: invalid conversion from 'int*' to 'int' [-fpermissive]

我猜这是我忽略的一些简单的东西，但我就是找不到它，已经尝试了一段时间。

编辑：现在决定简单地传递key并minNode()忽略 oldKey 和 auxKey，修改 minNode 以返回指针。

新错误，同一个地方

lvalue required as left operand
4

1 回答 1

0

您的 minNode 函数接受一个表示旧键的 int 值，但您在 remove 函数（特别是 auxKey）中将一个 int* 传递给它。尝试传入旧键的值，而不是指向它的指针。或者，如果您想更新 in 参数以保持正确的值（您似乎正在尝试这样做），请将参数更改为参考参数。

希望这可以帮助！

于 2012-06-13T16:49:09.557 回答