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

Question

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

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

Это зависит от того, хотите ли вы получить копию shallow or deep. Предполагая глубокую копию, вы должны иметь возможность копировать все, что угодно, на «листья», зависающие от объекта 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.

Answer 3

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

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

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

Answer 4

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

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

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

Вот еще один пример, который я использовал с двоичным деревом. В этом примере узел и дерево определены в отдельных классах, а рекурсивная функция 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 

копия: возвращает указатель на новое дерево

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

Я надеюсь, что это поможет кому-то.