arbre binaire pour

Question

Le code que j'ai écrit à ce jour est:

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

Je ne sais pas comment créer un lien vers le parent aux nœuds que son afinde.

Answer 1

Je pense que ce serait quelque chose comme ça.

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 des points à la racine Supposons que (2). Pour la copie, nous devons faire ce qui suit:

1. créer un noeud à copyTree, et la copie la valeur 2 en elle
2. si orgTree->left != NULL, appelez copyInOrder(orgTree->left, copyTree->left);
3. si orgTree->right != NULL, appel copyInOrder(orgTree->right, copyTree->right);

BTW, ce type de traversée est connu comme pre-order traversa l, La traversée dans l'ordre est différente.

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