时间戳

首页 > 解决方案 > 为什么我的二叉搜索树重载移动赋值运算符没有根据我的代码正确删除？

c++ - 为什么我的二叉搜索树重载移动赋值运算符没有根据我的代码正确删除？

问题描述

BST.cpp 的重载移动赋值运算符：

BST& BST::operator=(BST&& otherBST) {
    if (this != &otherBST) {
        if (root) {
            stack <Node*> nodeStack;
            nodeStack.push(root);

            Node *currentNode = nullptr;
            while (!nodeStack.empty()) {
                currentNode = nodeStack.top();
                nodeStack.pop();

                if (currentNode->rlink) {
                    nodeStack.push(currentNode->rlink);
                }
                if (currentNode->llink) {
                    nodeStack.push(currentNode->llink);
                }

                delete currentNode;
                currentNode = nullptr;
            }
            cout << root << endl; // This is where it seems like root is not being deleted correctly/nullptr'd.
        }

        root = move(otherBST.root);
        otherBST.root = nullptr;
    }
    else {
        cerr << "ERROR: Cannot assign to self." << endl;
    }

    return *this;
}

看看我评论的 cout << root << endl 部分。当那段代码运行时，它会打印出一个不是 00000000 的地址。看起来它们没有被正确删除。

这是一个代码，其中调用对象的 BST 被删除（所有分支），然后它窃取了其他 BST 的树。移动赋值运算符。但是为什么它不打印 nullptr 而是打印另一个地址呢？它似乎没有被正确删除。

以下供参考：

这是正在运行的测试驱动程序的屏幕截图：单击此处查看。

主文件

#include <iostream>
#include "Test.h"
using namespace std;

int main()
{
    runTest();

    cout << endl << endl;
    system("Pause");
    return 0;
}

测试.h

#include "BST.h"

void runTest() {
    cout << "--------------------------------------------------------------------" << endl;
    cout << "Binary Search Tree Test Driver" << endl;
    cout << "--------------------------------------------------------------------" << endl;
    // Initialization:
    BST bst1;
    // Traversal when there are no elements in the tree:
    cout << "BST traversal when there are no elements within the tree (bst1): " << endl;
    bst1.preorderTraversal();
    cout << endl;
    cout << "BST, inserting one element into the tree recursively and non-recursively (bst1): " << endl;
    bst1.insert(21);
    bst1.preorderTraversal();
    cout << endl;
    bst1.insert(69);
    bst1.preorderTraversal();
    cout << endl;
    cout << "BST, inserting duplicate elements into the tree recursively (bst1): " << endl;
    bst1.insert(32);
    bst1.insert(32);
    bst1.preorderTraversal();
    cout << endl;
    cout << "BST using the function destroyTree (bst1): " << endl;
    bst1.destroyTree();
    bst1.preorderTraversal();
    cout << endl;
    cout << "BST copy constructor by copy constructing bst1 (bst2): " << endl;
    bst1.insert(21);
    bst1.insert(69);
    BST bst2(bst1);
    bst2.preorderTraversal();
    cout << endl;
    cout << "BST move constructor by move constructing bst1 (bst3): " << endl;
    BST bst3 = move(bst1);
    bst3.preorderTraversal();
    cout << endl;
    cout << "BST move assignment operator by move assigning bst2 (bst1) when bst1 has no elements in its tree: " << endl;
    bst1.destroyTree();
    bst1 = move(bst2);
    bst1.preorderTraversal();
    cout << endl;
    bst1.destroyTree();
    bst2.destroyTree();
    cout << "BST move assignment operator by move assigning bst2 (bst1) when bst1 already has some elements in its tree: " << endl;
    bst1.insert(21);
    bst1.insert(105);
    bst1.insert(18);
    bst1.insert(16);
    bst1.insert(7);
    bst1.insert(19);
    bst1.insert(109);
    bst1.insert(125);
    bst1.insert(101);
    bst2.insert(691);
    bst1 = move(bst2);
    bst1.preorderTraversal();
    cout << endl;
}

BST.h

#ifndef BST_H
#define BST_H

#include <string>       
#include <iostream>
#include <stack>

using namespace std;

class Node
{
    friend class BST;
public:
    Node() : data(0), rlink(nullptr), llink(nullptr) {}
    ~Node() {}
private:
    int data;
    Node *rlink, *llink;
};

class BST
{
public:
    BST();

    BST(const BST& otherBST); 

    BST(BST&& otherBST); 

    void insert(int item);

    void insertNonRecursive(int item);

    void preorderTraversal() const;

    // BST& operator=(const BST& otherBST); 

    BST& operator=(BST&& otherBST); 

    void destroyTree();

    ~BST();

private:
    Node * root; // Pointer to the root.

    void copyConstructor(const Node *p);

    void insert(Node* &p, Node *newNode);

    void preorderTraversal(const Node *p) const;

    void destroyTree(Node *&p);
};

#endif

BST.cpp

#include "BST.h"

BST::BST() : root(nullptr) {}

BST::BST(const BST& otherBST) {
    copyConstructor(otherBST.root);
}

BST::BST(BST&& otherBST) {
    root = move(otherBST.root);

    otherBST.root = nullptr;
}

void BST::copyConstructor(const Node *p) {
    if (p != nullptr) {
        insert(p->data);
        copyConstructor(p->llink);
        copyConstructor(p->rlink);
    }
}


void BST::insert(int insertItem)
{
    Node  *newNode = new Node;
    newNode->data = insertItem;
    insert(root, newNode);
}

void BST::insert(Node* &p, Node *newNode)
{
    if (p == nullptr)
        p = newNode;
    else if (p->data > newNode->data)
        insert(p->llink, newNode);
    else
        insert(p->rlink, newNode);
}

void BST::insertNonRecursive(int item) {
    if (root == nullptr) {
        root = new Node();
        root->data = item;
    }
    else {
        Node *current = root;
        bool searching = true;

        while (searching) {
            if (item > current->data && current->rlink != nullptr) {
                current = current->rlink;
            }
            else if (item < current->data && current->llink != nullptr) {
                current = current->llink;
            }
            else if (item == current->data) {
                cerr << "The item to insert is already in the list, duplicates are not allowed." << endl;
                searching = false;
            }
            else {
                if (item > current->data) {
                    current->rlink = new Node();
                    current->rlink->data = item;
                }
                else {
                    current->llink = new Node();
                    current->llink->data = item;
                }

                searching = false;
            }
        }
    }
}

void BST::preorderTraversal() const {
    if (root == nullptr)
        cerr << "There is no tree.";
    else
    {
        preorderTraversal(root);
    }
}

void BST::preorderTraversal(const Node *p) const {
    if (p != nullptr) {
        cout << p->data << " ";
        preorderTraversal(p->llink);
        preorderTraversal(p->rlink);
    }
}

BST& BST::operator=(BST&& otherBST) {
    if (this != &otherBST) {
        if (root) {
            stack <Node*> nodeStack;
            nodeStack.push(root);

            Node *currentNode = nullptr;
            while (!nodeStack.empty()) {
                currentNode = nodeStack.top();
                nodeStack.pop();

                if (currentNode->rlink) {
                    nodeStack.push(currentNode->rlink);
                }
                if (currentNode->llink) {
                    nodeStack.push(currentNode->llink);
                }

                delete currentNode;
                currentNode = nullptr;
            }
            cout << root << endl; // This is where it seems like root is not being deleted correctly/nullptr'd.
        }

        root = move(otherBST.root);
        otherBST.root = nullptr;
    }
    else {
        cerr << "ERROR: Cannot assign to self." << endl;
    }

    return *this;
}

void BST::destroyTree(Node* &p)
{
    if (p != nullptr)
    {
        destroyTree(p->llink);
        destroyTree(p->rlink);
        delete p;
        p = nullptr;
    }
}

void  BST::destroyTree()
{
    destroyTree(root);
}

BST::~BST()
{
    destroyTree(root);
}

标签： c++treebinaryvariable-assignmentmove

解决方案

我认为你提到的那条线很好，没有泄漏任何东西。只是指针没有分配给NULL。在下面的示例中，您可能期望 pA 为 NULL

int *pA = new int;
int *pB = pA;
delete pB;
pB=NULL;

printf("pA=0x%p, pB=0x%p", pA,pAB);

请注意，即使 pA 指向的东西现在是一个悬空指针，也没有泄漏。

要获得所需的行为，您可以在完成压入堆栈后将根设置为 NULL。

推荐阅读