时间戳

首页 > 解决方案 > 尝试在 C++ 中删除 BST 时出现问题

c++ - 尝试在 C++ 中删除 BST 时出现问题

问题描述

我想删除二叉搜索树中的所有节点。这是在树中插入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 类的一部分：

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;
}

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

标签： c++memorybinary-search-tree

解决方案

问题似乎在这里：

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

如果一个具有值的节点已经存在，那么由于没有插入该节点value，因此分配它会浪费内存。nn

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

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

推荐阅读