Оператор двоичного дерева глубокая копия - PullRequest
Новая
       5

Оператор двоичного дерева глубокая копия

0 голосов
/ 13 января 2020

Я пытаюсь сделать глубокую копию, используя оператор "=", но, похоже, это мелкая копия в том виде, в котором я ее написал, и я не понимаю, почему это так. 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?

Ответы [ 3 ]

1 голос
/ 13 января 2020

Вам нужно создавать новые узлы, а не (просто) удалять старые. Если дерево состоит из пяти узлов, и вы никогда не создаете какие-либо новые узлы, невозможно иметь два дерева из пяти узлов после.

Ваш оператор присваивания копии должен представлять конструкцию нового дерева в целом. В этом случае вы можете использовать конструктор копирования (который в любом случае должен иметь правило три): 

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

Вот сравнение, показывающее ваш неправильный вызов, который просто назначает указатели по сравнению с реальным объектом назначение. Я предполагаю, что ваш конструктор правильно сформирован, и делайте приватные члены доступными c, так как вы не включили весь необходимый код, чтобы я мог быстро это проверить. 

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;
}
0 голосов
/ 13 января 2020

Подумайте рекурсивно, когда вы пишете алгоритмы для рекурсивных структур данных.

Сначала определите ваши понятия:

Клон узла A :

  • Пусто, если A пусто или

  • Новый узел, данные которого являются копией A * 1019 Данные *, слева клон левого узла А , а справа клон правого узла А в противном случае.

Это можно перевести на вспомогательный метод: 

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

Теперь вы можете express ваш 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;
}
0 голосов
/ 13 января 2020

почему это мелкая копия

Потому что, если вы назначите элемент указателя this, чтобы он указывал на тот же объект, на который указывает другой экземпляр, значит, вы сделали мелкое copy.

Чтобы получить глубокую копию дерева, вы должны создать узлы для этой копии. Если дубликатов узлов нет, то дубликат (глубокая) копия дерева не существует. Нигде в вашем операторе присваивания вы не создаете никаких узлов.

...