c++ - 二叉树的深拷贝

Question

我有一个包含不同类型节点的树，我需要对其进行深度复制。层次结构看起来像这样:

class AllNodes
{
    //this is a purely virtual base class
};
class TreeNode : public AllNodes
{
    AllNodes *rChild, *lChild;
};
class LeefNode : public AllNodes
{
    int value;
};

问题是，当我想对整棵树进行深拷贝时，我不知道哪些节点会有子节点，哪些节点会有值。我试过这个，但它行不通(原因很明显):

void AllNodes::deepCopy(AllNodes* &copied, AllNodes* o)
{
    if(o->rChild == nullptr)
        copied->rChild = nullptr;
    else
    {
        copied->rChild = o->rChild;   
        deepCopy(copied->rchild, o->rChild);
    }

    if(o->lChild == nullptr)
        copied->lChild = nullptr;
    else
    {
        copied->lChild = o->lChild;
        deepCopy(copied->lChild, o->lChild);
    }
}

有没有人知道如何实现这一点？

Answer 1

创建虚方法并在TreeNode和LeafNode中实现。

class AllNodes
{
    //this is a purely virtual base class
    virtual AllNodes* copy() const = 0;
};
class TreeNode : public AllNodes
{
    AllNodes* rChild, lChild;
    virtual AllNodes* copy() const {
         TreeNode *n = new TreeNode;
         n->rChild = rChild->copy();
         n->lChild = lChild->copy();
         return n;
    }
};
class LeafNode : public AllNodes
{
    int value;
    virtual AllNodes* copy() const {
         LeafNode *n = new LeafNode;
         n->value = value;
         return n;
    }
};

(只是草稿)