5

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

2 に答える 2

5

ルートノードのディープコピーを実行しているのではなく、その子のみを実行しています。

すべきではありません：

root = copyTree(copytree.root);

？

編集：さらに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;
}

これらの修正の1つだけを実行すると、問題は解決されません。

于 2012-05-07T12:22:21.177 に答える
1

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

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

次に、コピーコンストラクタは

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
}

2つの子が両方ともであるため、再帰はリーフノードで停止しますnullptr。

そして、デストラクタもそうです。

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

またはがの場合left、rightは何も実行しないため、再帰は停止しますnullptr。delete

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

于 2016-02-05T10:56:40.890 に答える