按顺序复制二叉树

Question

我到目前为止写的代码是：

void copyInOrder(TNode *orgTree, Tnode *& copyTree){
    if(orgTree !=NULL){
        copyInOrder(orgTree->left_link);
        //create leftmost node of tree but how to link to parent
        copyInOrder(orgTree->right_link);
    }
}

我不知道如何链接到节点的父节点作为其顺序。

Answer 1

我想会是这样的。

void copyInOrder(TNode *orgTree, Tnode *& copyTree){
    if(orgTree !=NULL){
        //left side
        TNode newLeftNode = cloneNode(orgTree->left_link);
        copyTree->left_link = newLeftNode;
        copyInOrder(orgTree->left_link, copyTree->left_link);

        //right side
        TNode newRightNode = cloneNode(orgTree->right_link);
        copyTree->right_link = newRightNode;
        copyInOrder(orgTree->right_link, copyTree->right_link);
    }
}

Answer 2

假设orgTree指向root（2）。对于复制，我们必须执行以下操作：

1. 在copyTree创建一个节点，并将值2复制到其中
2. 如果orgTree->left != NULL，请致电copyInOrder( orgTree->left, copyTree->left );
3. 如果orgTree->right != NULL，请致电copyInOrder( orgTree->right, copyTree->right );

顺便说一句，这种类型的遍历被称为pre-order traversal，有序遍历是不同的。

Answer 3

tnode *copy(tnode *root) {
     tnode *new_root;
     if(root!=NULL){
         new_root=new tnode;
         new_root->data=root->data;
         new_root->lchild=copy(root->lchild);
         new_root->rchild=copy(root->rchild);
     } else return NULL;
     return new_root;
 }

Answer 4

这是一种有效且简单的递归方法

Tnode* CopyInOrder(Tnode* root){
    if(root == NULL){return NULL;}
    else{
        Tnode* temp = new Tnode;
        temp -> data = root -> data;
        temp -> left = copyInOrder(root -> left);
        temp -> right = copyInOrder(root -> right);
        return temp;
        }
}