Конструктор копирования для двоичного дерева C ++

Question

У меня есть класс Tree со следующим определением:

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

TreeNode представляет узел и имеет данные, leftPtr и rightPtr.

Как мне создать копию объекта дерева, используя конструктор копирования? Я хочу сделать что-то вроде:

Tree obj1;
//insert nodes

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

Любая помощь приветствуется!

Answer 1

Псевдо-код:

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

Answer 2

Зависит от того, хотите ли вы мелкую или глубокую копию. Предполагая глубокое копирование, вы должны иметь возможность копировать все, что находится на «листьях», свисающих с объекта 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 заботится об этом уровне функциональности (как о другом классе), то, очевидно, у вас будет точный эквивалент, но с клонированием узла в качестве явного аргумента.

Answer 3

Два основных варианта:

Если у вас есть итератор, вы можете просто перебрать элементы в дереве и вставить каждый из них вручную, как описал Р. Пейт. Если ваш класс дерева не принимает явных мер для уравновешивания дерева (например, AVL или красно-черные повороты), таким образом вы получите эффективный связанный список узлов (то есть все левые дочерние указатели будут нулевыми ). Если вы балансируете свое дерево, вы фактически дважды выполняете работу по балансировке (поскольку вам уже приходилось выяснять это в исходном дереве, из которого вы копируете).

Более быстрое, но более сложное и подверженное ошибкам решение состояло бы в том, чтобы создать копию сверху вниз, выполнив обход исходной древовидной структуры в ширину или глубину. Вам не понадобятся какие-либо балансировочные вращения, и вы получите идентичную топологию узла.

Answer 4

Вот еще один пример, который я использовал с двоичным деревом. В этом примере узел и дерево определены в отдельных классах, а рекурсивная функция copyHelper помогает функции copyTree. Код не полный, я попытался указать только то, что было необходимо, чтобы понять, как реализованы функции.

copyHelper

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

Надеюсь, это кому-нибудь поможет.

Answer 5

Вы можете попробовать что-то вроде (не проверено)

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

Answer 6

Когда у вашего класса есть указатель, указывающий на динамически выделяемую память, в конструкторе копирования этого класса вам нужно выделить память для вновь созданного объекта. Затем вам нужно инициализировать вновь выделенную память тем, на что указывает другой указатель. Вот пример того, как вам нужно работать с классом, имеющим динамически распределенную память:

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