次の定義を持つ Tree クラスがあります。
class Tree {
Tree();
private:
TreeNode *rootPtr;
}
TreeNode はノードを表し、データ leftPtr および rightPtr を持ちます。
コピー コンストラクターを使用してツリー オブジェクトのコピーを作成するにはどうすればよいですか? 私は次のようなことをしたい:
Tree obj1;
//insert nodes
Tree obj2(obj1); //without modifying obj1.
どんな助けでも大歓迎です！
擬似コード:
struct Tree {
Tree(Tree const& other) {
for (each in other) {
insert(each);
}
}
void insert(T item);
};
具体例 (ツリーの歩き方を変更することは重要ですが、コピー ctor がどのように機能するかを示すことを妨げており、ここで誰かの宿題をやりすぎている可能性があります):
#include <algorithm>
#include <iostream>
#include <vector>
template<class Type>
struct TreeNode {
Type data;
TreeNode* left;
TreeNode* right;
explicit
TreeNode(Type const& value=Type()) : data(value), left(0), right(0) {}
};
template<class Type>
struct Tree {
typedef TreeNode<Type> Node;
Tree() : root(0) {}
Tree(Tree const& other) : root(0) {
std::vector<Node const*> remaining;
Node const* cur = other.root;
while (cur) {
insert(cur->data);
if (cur->right) {
remaining.push_back(cur->right);
}
if (cur->left) {
cur = cur->left;
}
else if (remaining.empty()) {
break;
}
else {
cur = remaining.back();
remaining.pop_back();
}
}
}
~Tree() {
std::vector<Node*> remaining;
Node* cur = root;
while (cur) {
Node* left = cur->left;
if (cur->right) {
remaining.push_back(cur->right);
}
delete cur;
if (left) {
cur = left;
}
else if (remaining.empty()) {
break;
}
else {
cur = remaining.back();
remaining.pop_back();
}
}
}
void insert(Type const& value) {
// sub-optimal insert
Node* new_root = new Node(value);
new_root->left = root;
root = new_root;
}
// easier to include simple op= than either disallow it
// or be wrong by using the compiler-supplied one
void swap(Tree& other) { std::swap(root, other.root); }
Tree& operator=(Tree copy) { swap(copy); return *this; }
friend
ostream& operator<<(ostream& s, Tree const& t) {
std::vector<Node const*> remaining;
Node const* cur = t.root;
while (cur) {
s << cur->data << ' ';
if (cur->right) {
remaining.push_back(cur->right);
}
if (cur->left) {
cur = cur->left;
}
else if (remaining.empty()) {
break;
}
else {
cur = remaining.back();
remaining.pop_back();
}
}
return s;
}
private:
Node* root;
};
int main() {
using namespace std;
Tree<int> a;
a.insert(5);
a.insert(28);
a.insert(3);
a.insert(42);
cout << a << '\n';
Tree<int> b (a);
cout << b << '\n';
return 0;
}
浅いコピーと深いコピーのどちらが必要かによって異なります。TreeNodeディープコピーを想定すると、オブジェクトからぶら下がっている「葉」にあるものは何でもコピーできる必要があります。理想的には、機能が含まれている必要があります（もちろん、多くの場合、その実装に精通するように設計したフレンドクラスでTreeNodeない限り;-）。次のようなものを想定しています...：TreeTreeNode
template <class Leaf>
class TreeNode {
private:
bool isLeaf;
Leaf* leafValue;
TreeNode *leftPtr, *rightPtr;
TreeNode(const&Leaf leafValue);
TreeNode(const TreeNode *left, const TreeNode *right);
...
次に、それに追加できます
public:
TreeNode<Leaf>* clone() const {
if (isLeaf) return new TreeNode<Leaf>(*leafValue);
return new TreeNode<Leaf>(
leftPtr? leftPtr->clone() : NULL,
rightPtr? rightPtr->clone() : NULL,
);
}
がこのレベルの機能を (フレンド クラスとして) 処理している場合Tree、明らかにまったく同等のものになりますが、ノードは明示的な引数として複製されます。
2 つの基本的なオプション:
利用可能なイテレータがある場合は、R. Pate が説明したように、ツリー内の要素を単純に繰り返し処理し、それぞれを手動で挿入できます。ツリー クラスがツリーのバランスをとるための明示的な手段 (AVL や赤黒の回転など) をとらない場合、この方法で効果的にノードのリンク リストが作成されます (つまり、左側の子ポインターはすべて null になります)。 ）。ツリーのバランスをとっている場合は、効果的にバランス作業を 2 回行うことになります (コピー元のソース ツリーで既に計算しておく必要があるため)。
ソース ツリー構造の幅優先または深さ優先のトラバーサルを実行して、コピーをトップダウンで構築することは、より迅速ですが、より厄介でエラーが発生しやすいソリューションです。ローテーションのバランスをとる必要はなく、最終的には同一のノード トポロジになります。
二分木で使用した別の例を次に示します。この例では、ノードとツリーが別々のクラスで定義されており、copyHelper再帰関数が関数を支援していcopyTreeます。コードは完全ではありません。機能がどのように実装されているかを理解するために必要なものだけを入れようとしました。
コピーヘルパー:
void copyHelper( BinTreeNode<T>* copy, BinTreeNode<T>* originalNode ) {
if (originalTree == NULL)
copy = NULL;
else {
// set value of copy to that of originalTree
copy->setValue( originalTree->getValue() );
if ( originalTree->hasLeft() ) {
// call the copyHelper function on a newly created left child and set the pointers
// accordingly, I did this using an 'addLeftChild( node, value )' function, which creates
// a new node in memory, sets the left, right child, and returns that node. Notice
// I call the addLeftChild function within the recursive call to copyHelper.
copyHelper(addLeftChild( copy, originalTree->getValue()), originalTree->getLeftChild());
}
if ( originalTree->hasRight() ) { // same with left child
copyHelper(addRightChild(copy, originalTree->getValue()), originalTree->getRightChild());
}
} // end else
} // end copyHelper
copy : 新しいツリーへのポインタを返します
Tree* copy( Tree* old ) {
Tree* tree = new Tree();
copyHelper( tree->root, oldTree->getRoot() );
// we just created a newly allocated tree copy of oldTree!
return tree;
} // end copy
使用法：
Tree obj2 = obj2->copy(obj1);
これが誰かに役立つことを願っています。
あなたは（未テスト）のようなものを試すことができます
class Tree {
TreeNode *rootPtr;
TreeNode* makeTree(Treenode*);
TreeNode* newNode(TreeNode* p)
{
TreeNode* node = new Treenode ;
node->data = p->data ;
node->left = 0 ;
node->right = 0 ;
}
public:
Tree(){}
Tree(const Tree& other)
{
rootPtr = makeTree(other.rootPtr) ;
}
~Tree(){//delete nodes}
};
TreeNode* Tree::makeTree(Treenode *p)
{
if( !p )
{
TreeNode* pBase = newNode(p); //create a new node with same data as p
pBase->left = makeTree(p->left->data);
pBase->right = makeTree(p->right->data);
return pBase ;
}
return 0 ;
}
クラスに動的に割り当てられたメモリを指すポインターがある場合、そのクラスのコピー コンストラクターで、新しく作成されたオブジェクトにメモリを割り当てる必要があります。次に、新しく割り当てられたメモリを、他のポインタが指すもので初期化する必要があります。動的に割り当てられたメモリを持つクラスをどのように処理する必要があるかの例を次に示します。
class A
{
int *a;
public:
A(): a(new int) {*a = 0;}
A(const A& obj): a(new int)
{
*a = *(obj.a);
}
~A() {delete a;}
int get() const {return *a;}
void set(int x) {*a = x;}
};