二叉樹的深層副本

我有這種樹需要進行深層複製的不同類型的節點。層次結構看起來是這樣的：二叉樹的深層副本

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

二叉樹的深層副本

回答

相關問題