2014-09-02 7 views
1

У меня есть это дерево с различными типами узлов, на которых мне нужно сделать глубокую копию. Иерархия выглядит примерно так:Глубокая копия двоичного дерева

class AllNodes 
{ 
    //this is a purely virtual base class 
}; 
class TreeNode : public AllNodes 
{ 
    AllNodes *rChild, *lChild; 
}; 
class LeefNode : public AllNodes 
{ 
    int value; 
}; 

Проблема заключается в том, что, когда я хочу сделать полную копию всего дерева, я не знаю, какие узлы будут иметь ребенок и какие узлы будут иметь значение. Я попытался это, но это не будет работать (по понятным причинам):

void AllNodes::deepCopy(AllNodes* &copied, AllNodes* o) 
{ 
    if(o->rChild == nullptr) 
     copied->rChild = nullptr; 
    else 
    { 
     copied->rChild = o->rChild; 
     deepCopy(copied->rchild, o->rChild); 
    } 

    if(o->lChild == nullptr) 
     copied->lChild = nullptr; 
    else 
    { 
     copied->lChild = o->lChild; 
     deepCopy(copied->lChild, o->lChild); 
    } 
} 

Кто-нибудь есть некоторые идеи о том, как это сделать?

+2

Надеюсь, что это на самом деле 'AllNodes * rChild * lChild ; '. *Большая разница. И это не делает * node * copy * вообще * Если вы делаете истинную глубокую «копию», вы можете рассчитывать фактически выделить некоторые * узлы * в этом процессе. – WhozCraig

+0

Что делать, если вы просто использовали 'value_ptr' для хранения узлов? И 'variant', чтобы сохранить либо значение, либо детей. –

+0

Вы просто назначаете указатели, так что это мелкая копия ... сначала выделите память, а затем скопируйте данные в эту новую память, а затем назначьте указатели –

ответ

5

Создайте виртуальный метод и реализуйте его в TreeNode и LeafNode.

class AllNodes 
{ 
    //this is a purely virtual base class 
    virtual AllNodes* copy() const = 0; 
}; 
class TreeNode : public AllNodes 
{ 
    AllNodes* rChild, lChild; 
    virtual AllNodes* copy() const { 
     TreeNode *n = new TreeNode; 
     n->rChild = rChild->copy(); 
     n->lChild = lChild->copy(); 
     return n; 
    } 
}; 
class LeafNode : public AllNodes 
{ 
    int value; 
    virtual AllNodes* copy() const { 
     LeafNode *n = new LeafNode; 
     n->value = value; 
     return n; 
    } 
}; 

(Только проект)

+0

Уход! Я попробую. –

2

Это полиморфное поведение (создание глубокой копии, на основе конкретного типа объекта). Таким образом, он должен быть реализован в виртуальной функции по всей иерархии узлов.

Функция для выполнения глубокого копирования, как правило, называют клоном:

class AllNodes 
{ 
    //this is a purely virtual base class 
public: 
    virtual AllNodes* clone() = 0; 
}; 

class TreeNode : public AllNodes 
{ 
    AllNodes *rChild, *lChild; // you skipped declaring lChild as a pointer 
public: 
    virtual AllNodes* clone() override // recursive implementation for child nodes 
    { 
     return new TreeNode{ 
      rChild ? rChild->clone() : nullptr, 
      lChild ? lChild->clone() : nullptr }; // assume existence of this 
                // constructor 
    } 
}; 

class LeafNode : public AllNodes 
{ 
    int value; 
public: 
    virtual AllNodes* clone() override 
    { 
     return new LeafNode{ value }; // assume existence of this constructor 
    } 
}; 

код клиента (глубокая копия всего дерева):

AllNodes *original; // filled in elsewhere 
AllNodes *deepCopy = original->clone(); 
Смежные вопросы