尝试在 C++ 中删除 BST 的问题

Question

我想删除二叉搜索树中的所有节点。这是在树中插入 nodesAmount 个节点的代码：

    void testFindInsert(int nodesAmount) {
    int value; 
    BSTNode* n = NULL;
    BSTNode* root = NULL;

    for (int i = 0; i < nodesAmount; i++) {
        value = rand() % INT_MAX + 1;
        n = new BSTNode(value, "");
        if (!findNode(root, value))
            root = (BSTNode*)insertNode(root, n, BST);
    }

    root->destroy();
    root = NULL;
}

这是 BSTNode 的一部分 class:

BSTNode::BSTNode(int value, string str) {
    this->value = value;
    this->str = str;
}
...
void BSTNode::destroy(){
    if (this == NULL) return;
    this->left->destroy();
    this->right->destroy();
    delete this;
}

这里是插入方法：

BSTNode* insertNode(BSTNode* root, BSTNode* node, TreeType bstType = BST) {
    bool inserted = false;
    BSTNode* treeIterator = root;
        
    if (root == NULL) {
        root = node;
        inserted = true;
    } 

    while (!inserted) {
        if (node->getValue() < treeIterator->getValue()) {
            if (treeIterator->getLeft() != NULL) {
                treeIterator = treeIterator->getLeft();
            }
            else {
                treeIterator->setLeft(node);
                node->setFather(treeIterator);
                inserted = true;
            }
        }
        else if (node->getValue() > treeIterator->getValue()) {
            if (treeIterator->getRight() != NULL) {
                treeIterator = treeIterator->getRight();
            }
            else {
                treeIterator->setRight(node);
                node->setFather(treeIterator);
                inserted = true;
            }
        }
    }
    return root;
}

一切正常，但在调用 testFindInsert 后，内存未释放。即使以这种不同的方式尝试使用堆栈也不能解决问题：

void testFindInsert(int nodesAmount) {
    int value; 
    BSTNode* n = NULL;
    BSTNode* root = NULL;

    for (int i = 0; i < nodesAmount; i++) {
        value = rand() % INT_MAX + 1;
        n = new BSTNode(value, "");
        if (!findNode(root, value))
            root = (BSTNode*)insertNode(root, n, BST);
    }

    stack<BSTNode*> stackNodes;
    BSTNode* node;
    stackNodes.push(root);

    while (!stackNodes.empty()) {
        node = stackNodes.top();
        stackNodes.pop();
        if (node != NULL) {
            stackNodes.push(node->getRight());
            stackNodes.push(node->getLeft());
            delete node;
        }
    }
    root = NULL;
}

有谁知道问题出在哪里？提前致谢！

Answer 1

问题似乎出在这里：

n = new BSTNode(value, "");
if (!findNode(root, value))
    root = (BSTNode*)insertNode(root, n, BST);

如果值为 value 的节点已经存在，则将其分配给 n 会浪费内存，因为未插入该节点 n。

所以一旦确定value的节点在BST中不存在，就为节点分配内存。像这样：

if (!findNode(root, value)) {
    n = new BSTNode(value, "");
    root = (BSTNode*)insertNode(root, n, BST);
}

尝试在 C++ 中删除 BST 的问题

Problems trying to delete a BST in C++

c++

memory

binary-search-tree