二叉树的深层副本

我有这种树需要进行深层复制的不同类型的节点。层次结构看起来是这样的：二叉树的深层副本

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

有谁有如何做到这一点的一些想法？

来源

2014-09-02 Johan Hjalmarsson

希望这是真的'allnodes中* rChild，* lChild ;'。 *巨大差距。并且这样做根本不会* node * copy * *如果你正在做一个真正深的“复制”，你可以期望在这个过程中实际分配一些*节点*。 – WhozCraig 2014-09-02 09:20:00

如果您只是使用'value_ptr'来存储节点会怎么样？和“变种”来存储价值或孩子。 – 2014-09-02 09:20:03

你只是分配指针，当然这是一个浅拷贝...先分配内存，然后将数据复制到新内存中，然后分配指针 – 2014-09-02 09:20:11

创建一个虚拟方法并在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; 
    } 
};

（只是一个草案）

来源

2014-09-02 09:20:02 Messa

整洁！我会尝试一下。 – 2014-09-02 09:24:42

这是多态行为（创建一个深层副本，根据具体类型的对象）。因此，它应该在整个节点层次结构中以虚拟功能实现。

进行深拷贝的功能通常被称为克隆：

class AllNodes 
{ 
    //this is a purely virtual base class 
public: 
    virtual AllNodes* clone() = 0; 
}; 

class TreeNode : public AllNodes 
{ 
    AllNodes *rChild, *lChild; // you skipped declaring lChild as a pointer 
public: 
    virtual AllNodes* clone() override // recursive implementation for child nodes 
    { 
     return new TreeNode{ 
      rChild ? rChild->clone() : nullptr, 
      lChild ? lChild->clone() : nullptr }; // assume existence of this 
                // constructor 
    } 
}; 

class LeafNode : public AllNodes 
{ 
    int value; 
public: 
    virtual AllNodes* clone() override 
    { 
     return new LeafNode{ value }; // assume existence of this constructor 
    } 
};

客户端代码（整个树的深层副本）：

AllNodes *original; // filled in elsewhere 
AllNodes *deepCopy = original->clone();

来源

2014-09-02 09:31:39 utnapistim

二叉树的深层副本

回答

相关问题