複製二叉樹爲了

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指向根（2）。複印時，我們必須做到以下幾點：

1. 在copyTree創建一個節點，而副本中的值2到它
2. 如果​​，叫copyInOrder(orgTree->left, copyTree->left);
3. 如果orgTree->right != NULL，通話copyInOrder(orgTree->right, copyTree->right);

順便說一下，這種遍歷類型被稱爲pre-order traversa l，按順序遍歷是不同的。

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