时间戳

首页 > 解决方案 > 如何在红黑树中重载 operator=？C++

c++ - 如何在红黑树中重载 operator=？C++

问题描述

我有一棵红黑树，需要用赋值运算符重载。我有点重载了其节点不知道其父节点的二叉树的 operator=。但是，对于节点与左、右和父节点有关系的树，我该怎么做呢？

template<typename KEY, typename VALUE> class map;
template <typename KEY, typename VALUE>
class Node
{
private:
    friend class map<KEY, VALUE>;
 
    KEY id;
    VALUE object;
    bool color;
 
    Node* parent;
    Node* left;
    Node* right;
 
    Node(): id(0), object(nullptr), color(RED), parent(nullptr), left(nullptr), right(nullptr) {}
    Node(const KEY& id, const VALUE& object) : id(id), object(object), color(RED), parent(nullptr), left(nullptr), right(nullptr) {}
};
 
template<typename KEY, typename VALUE>
class map
{
private:
    Node<KEY, VALUE>* root;
public:
        map() : root(nullptr) {}
    ~map() { destroy(root); }
 
    map(const map<KEY, VALUE>& other)
    {
        if (other.root == nullptr)
            root = nullptr;
        else
            copyTree(root, other.root);
    }
 
    const map<KEY, VALUE>& operator=(const map<KEY, VALUE>& other)
    {
        if (this != &other)
        {
            if (root != nullptr)
                destroy(root);
            if (other.root == nullptr)
                root = NULL;
            else
                copyTree(root, other.root);
        }
        return *this;
    }
 
    void copyTree (Node<KEY, VALUE>*& copiedTreeRoot, Node<KEY, VALUE>* otherTreeRoot)
    {
        if (otherTreeRoot == nullptr)
            copiedTreeRoot = nullptr;
        else {
            copiedTreeRoot = new Node<KEY, VALUE>;
            copiedTreeRoot->id = otherTreeRoot->id;
            copiedTreeRoot->object = otherTreeRoot->object;
            copiedTreeRoot->color = otherTreeRoot->color;
            copiedTreeRoot->parent = otherTreeRoot->parent;
            copyTree(copiedTreeRoot->left, otherTreeRoot->left);
            copyTree(copiedTreeRoot->right, otherTreeRoot->right);
            //copyTree(copiedTreeRoot->parent, otherTreeRoot->parent);
        }
    }
};

标签： c++assignment-operatorred-black-tree

解决方案

您可以将新父母传递给CopyTree：

const map<KEY, VALUE>& operator=(const map<KEY, VALUE>& other)
{
    if (this != &other)
    {
        if (root != nullptr)
            destroy(root);
        copyTree(root, nullptr, other.root);
    }
    return *this;
}

void copyTree (Node<KEY, VALUE>*& copiedTreeRoot,
               Node<KEY, VALUE>* newParent,
               Node<KEY, VALUE>* otherTreeRoot)
{
    if (otherTreeRoot == nullptr)
        copiedTreeRoot = nullptr;
    else {
        copiedTreeRoot = new Node<KEY, VALUE>;
        copiedTreeRoot->id = otherTreeRoot->id;
        copiedTreeRoot->object = otherTreeRoot->object;
        copiedTreeRoot->color = otherTreeRoot->color;
        copiedTreeRoot->parent = newParent;

        copyTree(copiedTreeRoot->left, copiedTreeRoot, otherTreeRoot->left);
        copyTree(copiedTreeRoot->right, copiedTreeRoot, otherTreeRoot->right);
    }
}

推荐阅读