نسخ مُنشئ لشجرة ثنائية 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

يعتمد ذلك على ما إذا كنت تريد أ بارز أو عميق ينسخ. بافتراض نسخة عميقة ، يجب أن تكون قادرًا على نسخ كل ما هو في "الأوراق" معلقة 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

خياران أساسيان:

إذا كان لديك جهاز تكرار متاح ، فيمكنك ببساطة التكرار عبر العناصر الموجودة في الشجرة وإدراج كل منها يدويًا ، كما وصف R. Pate. إذا لم تتخذ فئة الشجرة الخاصة بك تدابير واضحة لتحقيق التوازن بين الشجرة (مثل 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

ينسخ: يعيد مؤشر إلى الشجرة الجديدة

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 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 6

يمكنك تجربة شيء مثل (لم يخبر)

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