이진 검색 트리 - 트리 복사

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