c++复制二叉树

Question

如果我用它来复制一个二叉树

BTNode<ElemType>* BinaryTree<ElemType>::_Copy( BTNode<ElemType>* T){ 
    if (T == NULL){
        return NULL;
    }
    BTNode<ElemType> *p;
    p = new BTNode<ElemType>;
    p->data = T->data;
    p->lchild = _Copy(T->lchild);
    p->rchild = _Copy(T->rchild);
    return p; 
}

并像这样为 = 运算符设置重载函数:

BinaryTree& operator=(const BinaryTree &rhs){
    if (&rhs == this){
        return *this;
    }
    _Destroy (m_root);
    m_root = _Copy ( rhs.m_root);
    return *this;
}

那么如果我有两个树型元素 tree_1 和 tree_2。

当我这样做

tree_2 = tree_1;

我将所有元素从 tree_1 复制到 tree_2。 而此时，我向 tree_2 添加了一个新节点。 tree_1 也会发生变化。 如何设置一个新的递归复制函数，使 tree_1 保持不变，只改变 tree_2 的结构？

Answer 1

您仅覆盖节点元素 BTNode = operator

这就是根拷贝的工作方式 当你复制树时 [tree_2 = tree_1;]

你正在使用 c++ 提供的默认复制 ctor 使用按位复制(深复制) 你需要创建一个复制构造函数 对于使用 foreach 节点的树 “=”运算符你都可以实现

node  *Cpy( root ) { 

   if (root == NULL ) : return root;

   node *temp = new node();
   temp->data = root-> data;    

   temp->left = Cpy( root -> left);   

   temp->right = Cpy(root -> right);  

   return temp;
}