c++ - 如何用对象数据在二叉搜索树中实现deletenode？

Question

我已经实现了删除方法，但由于某种原因，即使我为它调用了删除方法，被删除的节点仍然存在于树中。

class Leaf {
    Item* data;
    Leaf* left;
    Leaf* right;
    friend class binaryTree;

    Leaf(Item* data, Leaf* left = 0, Leaf* right = 0) :
            data(data), left(left), right(right) {
    }

    ~Leaf() {
        delete left;
        delete right;
    }

    Leaf* remove(Item* data, Leaf* parent) {
        if (data < this->data) {
            if (left != 0)
                return left->remove(data, this);
            else
                return 0;
        } else if (data > this->data) {
            if (right != 0)
                return right->remove(data, this);
            else
                return 0;
        } else {
            if (left != 0 && right != 0) {
                this->data = right->minValue();
                return right->remove(this->data, this);
            } else if (parent->left == this) {
                parent->left = (left != 0) ? left : right;
                return this;
            } else if (parent->right == this) {
                parent->right = (left != 0) ? left : right;
                return this;
            }
        }
        return 0;
    }

    Item* minValue() {
        if (left == 0)
            return data;
        else
            return left->minValue();
    }
};

这是树：

class binaryTree {
    Leaf* root;
public:
Item* search(string neptun, Leaf* node) {
        if (!node) {
            return 0;
        } else {
            if (node->data->neptun == neptun) {
                return node->data;
            } else {
                if (node->data->neptun > neptun)
                    return search(neptun, node->left);
                else
                    return search(neptun, node->right);
            }
        }
        return 0;
    }

    void deleteItem(string neptun) {
        deleteItem(search(neptun, root));
    }

    bool deleteItem(Item* data) {
        if (root == NULL)
            return false;
        else {
            if (root->data == data) {
                Leaf nroot(0);
                nroot.left = root;
                Leaf* removedNode = root->remove(data, &nroot);
                root = nroot.left;
                if (removedNode != 0) {
                    delete removedNode;
                    return true;
                } else
                    return false;
            } else {
                Leaf* removedNode = root->remove(data, 0);
                if (removedNode != 0) {
                    delete removedNode;
                    return true;
                } else
                    return false;
            }
        }
    }
};

我不知道为什么删除的节点在这些之后仍然存在。我的 inorderprint 函数首先检查数据是否存在（如果（节点）），但仍会打印内存垃圾。提前致谢。

这是 Item 类和 inorderprint：

class Item {
    string neptun;
    string name;
    double rating;
    Item* prev;
    Item* next;
    friend class circList;
    friend class binaryTree;
    friend class Leaf;

    Item(string neptun, string name, double rating, Item* prev = 0, Item* next =
            0) :
            neptun(neptun), name(name), rating(rating), prev(prev), next(next) {
    }

    bool operator<(Item* other) {
        return ((this->neptun) < (other->neptun));
    }

    bool operator>(Item* other) {
        return ((this->neptun) > (other->neptun));
    }
};

void listForward() {
        cout << "Listing in abc order:" << endl;
        listForward(root);
        cout << endl;
    }

void listForward(Leaf* node) {
        if (node) {
            listForward(node->left);
            cout << node->data->neptun << endl;
            listForward(node->right);
        }
}