이진 트리의 전체 복사본

이 트리에는 딥 복사를 수행해야하는 여러 유형의 노드가 있습니다. 계층 구조는 다음과 같은 :이진 트리의 전체 복사본

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

사람이 작업을 수행하는 방법에 대한 몇 가지 아이디어를 가지고 있습니까?

출처

2014-09-02 Johan Hjalmarsson

희망 :

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

클라이언트 코드 (전체 트리의 깊은 복사) :

깊은 복사를 수행 할 수있는 기능

은 일반적으로 복제라고합니다 ;'. *큰 차이. 그리고 이것은 * node * copy *를 전혀 만들지 않습니다. * 진실한 깊은 "복사"를하고 있다면 실제로 프로세스에 * 노드 *를 할당 할 것으로 기대할 수 있습니다. – WhozCraig

단순히'value_ptr'을 사용하여 노드를 저장하면 어떨까요? 값이나 자식을 저장하는 'variant'. –

그냥 포인터를 할당하는 것입니다. 이것은 얕은 복사본입니다. 먼저 메모리를 할당 한 다음 데이터를 새 메모리에 복사 한 다음 포인터를 할당하십시오. –

가상 메소드를 만들고이를 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; 
    } 
};

(그냥 초안)

출처

2014-09-02 09:20:02 Messa

Neat! 나는 그것을 밖으로 시도 할 것이다. –

이 (객체의 구체적인 유형에 따라 전체 복사본을 생성) 다형성 (polymorphic)이다. 따라서 전체 노드 계층에 걸쳐 가상 함수로 구현되어야합니다. `하여 allnodes * rChild, * lChild은 정말

AllNodes *original; // filled in elsewhere 
AllNodes *deepCopy = original->clone();

출처

2014-09-02 09:31:39 utnapistim

이진 트리의 전체 복사본

답변

관련 문제