Constructor de copia para un árbol binario de C ++

Question

Tengo una clase de árbol con la siguiente definición:

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

TreeNode representa un nodo y tiene datos, leftPtr y rightPtr.

¿Cómo se crea una copia de un objeto árbol usando un constructor de copia? Quiero hacer algo como:

Tree obj1;
//insert nodes

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

Cualquier ayuda se agradece!

Answer 1

Pseudo-código:

struct Tree {
  Tree(Tree const& other) {
    for (each in other) {
      insert(each);
    }
  }

  void insert(T item);
};

Ejemplo concreto (cambiando la forma en que camina el árbol es importante saber, pero resta valor a mostrar cómo funciona la copia ctor, y podría estar haciendo demasiado de la tarea de alguien aquí):

#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

Depende de si quieres un poco profunda o profunda copia. Suponiendo una copia profunda, tiene que ser capaz de copiar todo lo que está en las "hojas" colgando de un objeto TreeNode; por lo que idealmente la funcionalidad debe estar en TreeNode (a menos Tree es una clase de amigo TreeNode que ha diseñado para estar profundamente familiarizado con su aplicación, que es a menudo el caso, por supuesto ;-). Suponiendo algo así como ...:

template <class Leaf>
class TreeNode {
  private:
    bool isLeaf;
    Leaf* leafValue;
    TreeNode *leftPtr, *rightPtr;
    TreeNode(const&Leaf leafValue);
    TreeNode(const TreeNode *left, const TreeNode *right);
  ...

Entonces se puede inscribir a un

  public:
    TreeNode<Leaf>* clone() const {
      if (isLeaf) return new TreeNode<Leaf>(*leafValue);
      return new TreeNode<Leaf>(
        leftPtr? leftPtr->clone() : NULL,
        rightPtr? rightPtr->clone() : NULL,
      );
    }

Si Tree se hace cargo de este nivel de funcionalidad (como una clase friend), entonces es obvio que tendrá el equivalente exacto pero con el nodo que se está clonado como un arg explícita.

Answer 3

Hay dos opciones básicas:

Si usted tiene un iterador disponible, puede simplemente iterar sobre los elementos en el árbol e insertar cada uno de forma manual, como R. Pate descrito. Si el árbol de la clase no toma medidas explícitas para equilibrar el árbol (por ejemplo, AVL o rotaciones de color rojo-negro), que va a terminar efectivamente con una lista enlazada de nodos de esta manera (es decir, todos los punteros hijo izquierdo será nula ). Si usted está equilibrando su árbol, que va a hacer el trabajo de manera efectiva el equilibrio de dos veces (ya que ya había que entenderlo en el árbol fuente de la que va a copiar).

A, pero más rápido y desordenado solución más propenso a errores serían para construir la parte superior copia hacia abajo haciendo un primero en amplitud o profundidad primer recorrido de la estructura de árbol de las fuentes. Usted no necesita ninguna rotación de equilibrio y que terminarías con una topología de nodos idénticos.

Answer 4

He aquí otro ejemplo he usado con un árbol binario. En este ejemplo, el nodo y el árbol se definen en clases separadas y una función recursiva copyHelper ayuda a la función copyTree. El código no es completa, traté de poner sólo lo necesario para entender cómo se implementan las funciones.

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

Copiar : devuelve un puntero al nuevo árbol

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

Uso:

Tree obj2 = obj2->copy(obj1);

Espero que esto ayude a alguien.

Answer 5

Cuando su clase tiene un puntero que apunta a asignado dinámicamente la memoria, en el constructor de copia de esa clase que necesita para asignar memoria para el nuevo objeto creado. Luego hay que inicializar la memoria recién asignada con cualquier otro puntero que apunta a. Aquí hay un ejemplo de cómo se tiene que hacer frente a una clase que tiene memoria asignada dinámicamente:

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

Puede intentar algo así como (no probado)

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