二叉树运算符深拷贝

Question

我正在尝试使用“=”运算符进行深拷贝，但按照我的写法，它似乎是浅拷贝，但我不明白为什么会这样。 bs2 还添加了 "q" 所以我可以理解它做了浅拷贝为什么是浅拷贝，我以为是深拷贝。如何将其更改为深拷贝？

here is what I tried:
BSNode& BSNode::operator=(const BSNode& other) 
{
    if (this == &other) // tries to copy the object to itself
    {
        return *this;
    }
    delete _left;
    _left = other._left;
    delete _right;
    _right = other._right;

    return *this;
}

class BSNode
{
public:
    BSNode(std::string data);
    BSNode(const BSNode& other);
    ~BSNode();

    BSNode& operator=(const BSNode& other);

    //some more functions...
private:
    std::string _data;
    BSNode* _left;
    BSNode* _right;
    int _count; count the times an element appears in the tree
};

    BSNode* bs1 = new BSNode("d");
    bs1->insert("d");
    bs1->insert("b");

    BSNode* bs2 = new BSNode("1");

    bs2 = bs1;
    bs1->insert("q");
    bs2->printNodes(bs2);//bs2 also added "q"
    ```
bs2 also added "q" so I can understand it did shallow copy
why is it shallow copy, I expected it to be deep-copying.
how can I change it to deep copy?

Answer 1

why is it shallow copy

因为如果您将 this 的指针成员指定为指向与另一个实例所指向的对象相同的对象，那么您就进行了浅拷贝。

为了拥有树的深层副本，您必须为副本创建节点。如果没有重复的节点集，则不存在树的重复（深）副本。您的赋值运算符中没有任何地方创建任何节点。

Answer 2

您需要实际构建新节点，而不是（只是）删除旧节点。如果一棵树由五个节点组成，而你从不构造任何新节点，那么之后就不可能有两棵五个节点的树。

你的复制赋值运算符应该完全代表一棵新树的构造。在这种情况下，您可以利用复制构造函数（无论如何您都应该通过三规则获得）：

BSNode::BSNode(const BSNode& other) {
if(other._left){
      _left = new BSNode(*other._left);
    }
    if(other._right) {
      _right = new BSNode(*other._right);
    }
}

BSNode& BSNode::operator=(const BSNode& other) 
{
    if (this == &other) // tries to copy the object to itself
    {
        return *this;
    }
    delete _left;
    if(other._left){
      _left = new BSNode(*other._left);
    }
    delete _right;
    if(other._right) {
      _right = new BSNode(*other._right);
    }
    return *this;
}

这是一个比较，显示了与实际的对象分配相比，您的错误调用只是分配指针。我假设您的构造函数格式正确，并使成员成为私有成员 public，因为您没有包含我快速测试它所需的所有代码。

int main(){
    // bad
    BSNode* ap = new BSNode("a");
    ap->_left = new BSNode("al");
    BSNode* bp = ap;
    bp->_left = new BSNode("bl");

    std::cout << ap->_left->_data << std::endl;

    // good
    BSNode a("a");
    a._left = new BSNode("al");
    BSNode b(a);
    b._left = new BSNode("bl");
    std::cout << a._left->_data << std::endl;
}

Answer 3

在为递归数据结构编写算法时考虑递归。

首先定义你的概念：

Clone of a node A is:

Empty if A is empty, or

A new node whose data is the copy of A's data, left is Clone of A's left node, and right is Clone of A's right node otherwise.

这可以翻译成辅助方法：

BSNode* clone_node(const BSNode* src) {
    if (src == nullptr) return nullptr;
    BSNode* clonedNode = new BSNode(src.data);
    clonedNode.left = clone_node(src.left);
    clonedNode.right = clone_node(src.right);
    return clonedNode;
}

现在您可以这样表达您的operator=：

BSNode& BSNode::operator=(const BSNode& other) 
{
    if (this == &other) // tries to copy the object to itself
    {
        return *this;
    }
    this->data = other.data;
    delete this->left;
    delete this->right;
    this->left = clone_node(other.left);
    this->right = clone_node(other.right);
    return *this;
}

但是，如果您的左（或右）节点不是 nullptr，您可以重用它们（而不是分配新节点）。编写另一个辅助方法：

void clone_to(BSNode*& dest, const BSNode* src) {
    if (dest != nullptr && src != nullptr) {
        *dest = *src;
    }
    else {
        delete dest;
        dest = clone_node(src);
    }
}

现在你可以写你的最终版本了 operator=:

BSNode& BSNode::operator=(const BSNode& other) 
{
    if (this == &other) // tries to copy the object to itself
    {
        return *this;
    }
    this->data = other.data;
    clone_to(this->left, other.left);
    clone_to(this->right, other.right);
    return *this;
}

二叉树运算符深拷贝

Binary tree operator deep copy

c++

binary-tree

deep-copy