Скопируйте двоичное дерево в порядке

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

Предположим, orgTree указывает на корень (2). Для копирования мы должны сделать следующее:

1. создайте узел в copyTree и скопируйте в него значение 2
2. если orgTree->left != NULL, звоните copyInOrder( orgTree->left, copyTree->left );
3. если orgTree->right != NULL, звоните copyInOrder( orgTree->right, copyTree->right );

Кстати, этот тип обхода известен как обход по предварительному заказу l, обход по порядку отличается.

Answer 2

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 3

Я думаю, что это было бы что-то вроде этого.

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