Двоичное дерево поиска - Копирование дерева

Question

Я возился с сортировкой структур данных на C++, поэтому я пишу кучу функций, чтобы создать двоичный класс дерева поиска. Я немного потерял при попытке создать конструктор/функцию копирования для копирования дерева.

void BST<T>::copyBST(Node* treeOriginal, Node* treeNew){ 

     if (treeOriginal == NULL) //base case to end recursion when at tree end 
      treeNew == NULL; 
     else{ 
      Node* treeNew = new Node; //create the node and set the new key to original 
      treeNew->key = treeOriginal->key; 

      Node* leftChild = new Node; //create a left node to be child of new node 
      treeNew->left = leftChild; 
      leftChild->parent = treeNew; 

      Node* rightChild = new Node; //create a right node 
      treeNew->right = rightChild; 
      rightChild->parent = treeNew; 

      copyBST(treeOriginal->left, leftChild); //call copy function on subtree of left child 
      copyBST(treeOriginal->right, rightChild); //call copy function on subtree of right child 
     } 
} 

Теперь несколько вещей случаются, когда я пытаюсь запустить это. Во-первых, он не копирует все узлы и каждый раз копирует разные значения. Это странно для меня, так как я вызываю рекурсию на каждом узле, так как я начинаю с корня, а затем вызываю его слева и справа. Я попытался написать процесс на бумаге, визуально планируя, как он копирует исходное дерево, но для меня это похоже на логический процесс и не может найти, где он может потеряться.

Я также добавил инструкции cout в функцию, чтобы распечатать ключ, адрес, родительский элемент и дочерний элемент исходного узла, а также ключ, адрес, родительский элемент и дочерние элементы узла копии. Единственная проблема, которую я обнаружил в этом тесте, заключалась в том, что родительский адрес узла копии всегда был 00000000 или NULL. Таким образом, очевидно, что код кода

leftChild->parent = treeNew; and rightChild->parent = treeNew; 

фактически не устанавливает родительский указатель узла родительскому объекту.

Это были единственные ясные проблемы, которые я мог найти, пытаясь исправить это. Я не уверен, как еще искать проблему. Если вы не видите никаких проблем в логике кода, есть ли у кого-нибудь другие идеи о том, как найти, где проблема?

Спасибо!

Answer 1

Ваше объявление treeNew создает параметр по каждому значению. Это означает, что изменения этой переменной никогда не видны вызывающей стороне. Вы должны сделать это ссылочным параметром, чтобы указатель вызывающего абонента мог быть изменен. Затем рекурсивно копирует поддеревьев очень прост:

void BST<T>::copyBST(Node* treeOriginal, Node *parent, Node*& treeNew){ 

    if (treeOriginal == NULL) //base case to end recursion when at tree end 
     treeNew == NULL; 
    else{ 
     Node* treeNew = new Node; //create the node and set the new key to original 
     treeNew->key = treeOriginal->key; 
     treeNew->parent = parent; 

     // Just call recursively to copy the subtrees: 
     copyBST(treeOriginal->left, treeNew, treeNew->left); 
     copyBST(treeOriginal->right, treeNew, treeNew->right); 
    } 
} 

Обратите внимание на & добавлен ко второму типу параметра. Более распространенная идиома заключается в использовании возвращаемого значения функции:

Node* BST<T>::copyOf(Node* treeOriginal, Node *parent){ 

    if (treeOriginal == NULL) //base case to end recursion when at tree end 
     return NULL; 

    //create the node and set the new key to original 
    Node* treeNew = new Node; 
    treeNew->key = treeOriginal->key; 
    treeNew->parent = parent; 

    // Just call recursively to copy the subtrees: 
    treeNew->left = copyOf(treeOriginal->left, treeNew); 
    treeNew->right = copyOf(treeOriginal->right, treeNew); 

    return treeNew; 
}