我有一个具有以下定义的树类:
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;
}
关于c++ - 二叉树C++的复制构造函数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/1753486/