バイナリツリーのディープコピーコンストラクタ

Question

C++でバイナリツリーデータ構造のディープコピーを作成しようとしています。問題は、私が使用しているコードは、私に浅いコピーを与えているように思えるだけです（私のデコンストラクタに問題を引き起こすようです）。

以下のコードは、私のバイナリツリーのコピーコンストラクタです：

BinaryTreeStorage::BinaryTreeStorage(const BinaryTreeStorage &copytree):root(NULL) 
{ 
    root = copytree.root; 
    copyTree(root); 
} 

BinaryTreeStorage::node* BinaryTreeStorage::copyTree(node* other) 
{ 
    //if node is empty (at bottom of binary tree) 
    /* 
     This creates a shallow copy which in turn causes a problem 
     with the deconstructor, could not work out how to create a 
     deep copy. 
    */ 
    if (other == NULL) 
    { 
     return NULL; 
    } 

    node* newNode = new node; 

    if (other ->nodeValue == "") 
    { 
     newNode ->nodeValue = ""; 
    } 

    newNode->left = copyTree(other->left); 
    newNode->right = copyTree(other->right); 

    return newNode; 
} 

任意の助けをいただければ幸いです。 おかげでここ

は、あなたのルートノードの深いコピーを実行していない

BinaryTreeStorage::~BinaryTreeStorage(void) 
{ 
    try 
    { 
     destroy_tree();//Call the destroy tree method 
     delete root;//delete final node 
    } 
    catch(int &error) 
    { 
     cout << "Error Message : " << error << endl; 
    } 
} 
void BinaryTreeStorage::destroy_tree() 
{ 
    destroy_tree(root); 
} 
void BinaryTreeStorage::destroy_tree(node *leaf) 
{ 
    if(leaf!=NULL) 
    { 
    //Recursively work way to bottom node 
    destroy_tree(leaf->left); 
    destroy_tree(leaf->right); 
    //delete node 
    delete leaf; 
} 
} 

Answer 1

（私はので、私は上記やる浅いコピーであると信じて）メモリ例外をスローデコンストラクタですその子供たち。

は、それはすべきではない：

root = copyTree(copytree.root); 

？

EDIT：さらにで、あなたが二回rootを破壊する：あなただけのこれらの修正プログラムのいずれかを実行した場合

destroy_tree();//Call the destroy tree method 

//once here 
//remove this line 
delete root;//delete final node 

と

if(leaf!=NULL) 
{ 
    //Recursively work way to bottom node 
    destroy_tree(leaf->left); 
    destroy_tree(leaf->right); 

    //one more time here 
    delete leaf; 
} 

を、問題は解決されません。

Answer 2

実際、コピーコンストラクタを使用して、ツリーを再帰的にディープコピーすることができます。次のようにクラスが定義されていると仮定します

class TreeNode { 
public: 
    TreeNode() : value(), count(0), left(nullptr), right(nullptr) {} 
    TreeNode(const TreeNode &); 

    ~TreeNode(); 

    TreeNode &operator=(const TreeNode &); 

    // Other members... 

private: 
    std::string value; 
    int count; 
    TreeNode *left; 
    TreeNode *right; 
    // Note that the valid state for the `left` and `right` pointer is either 
    // `nullptr` or a subtree node. So that we must check these pointers every 
    // time before dereferencing them. 
}; 

そして、コピーコンストラクタは、その両方の2人の子供がnullptrなので再帰は、リーフノードで停止されます

TreeNode::TreeNode(const TreeNode &n) 
    : value(n.value), count(n.count), left(nullptr), right(nullptr) { 
    if (n.left) 
    left = new TreeNode(*n.left); // recursively call copy constructor 
    if (n.right) 
    right = new TreeNode(*n.right); // recursively call copy constructor 
} 

です。

デストラクタも同様です。再帰が停止されるように

TreeNode::~TreeNode() { 
    delete left; // recursively call destructor on left subtree node 
    delete right; // recursively call destructor on right subtree node 
} 

leftまたはrightがnullptrで、deleteは、何もしません。

hereから完全なコードを見ることができます。