2

我有一个具有以下定义的 Tree 类：

class Tree {
  Tree();
private:
  TreeNode *rootPtr;
}

TreeNode 表示一个节点，有数据，leftPtr 和 rightPtr。

如何使用复制构造函数创建树对象的副本？我想做类似的事情：

Tree obj1;
//insert nodes

Tree obj2(obj1); //without modifying obj1.

任何帮助表示赞赏！

4

6 回答 6

9

伪代码：

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;
}
于 2009-11-18T03:43:49.730 回答
5

这取决于您想要浅拷贝还是深拷贝。假设一个深拷贝，您需要能够复制挂在TreeNode对象上的“叶子”上的任何内容；所以理想情况下，功能应该在TreeNode（除非你设计Tree的一个朋友类TreeNode非常熟悉它的实现，当然这通常是这种情况;-)。假设类似...：

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正在处理此级别的功能（作为朋友类），那么显然您将拥有完全相同的功能，但节点被克隆为显式 arg。

于 2009-11-18T03:55:57.587 回答
2

两个基本选项：

如果您有可用的迭代器，您可以简单地迭代树中的元素并手动插入每个元素，如 R. Pate 所述。如果您的树类没有采取明确的措施来平衡树（例如 AVL 或红黑旋转），那么您将以这种方式有效地得到一个节点链表（也就是说，所有左子指针都将为空）。如果您正在平衡您的树，您将有效地进行两次平衡工作（因为您已经必须在您要复制的源树上找出它）。

一个更快但更混乱且更容易出错的解决方案是通过对源树结构进行广度优先或深度优先遍历来自顶向下构建副本。您不需要任何平衡旋转，并且最终会得到相同的节点拓扑。

于 2009-11-18T03:56:52.810 回答
1

这是我使用二叉树的另一个示例。在这个例子中，节点和树被定义在不同的类中，一个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

复制：返回一个指向新树的指针

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);

我希望这可以帮助别人。

于 2011-11-06T17:55:29.760 回答
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;}
};
于 2009-11-18T04:01:13.770 回答
0

您可以尝试类似（未经测试）


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 ;
}
于 2009-11-18T04:13:15.253 回答