BST

Question

에 노드를 삽입이 문제는 if 문 처음에 자리 잡고 내 삽입 기능

void BinTree::insert(Node * temp, NodeData * insData) 
{ 
    if (temp == NULL) 
    { 

     temp = new Node; 
     temp->pData = insData; 
     temp->left = NULL; 
     temp->right = NULL; 
     return; 
    } 
     //recursively go left or right 
     //....rest of the function 
} 

의 첫 번째 부분입니다. 여러 개의 노드를 추가하고 있습니다.
다음은 insert 함수를 호출하는 함수입니다.

void BinTree::insertMiddle(NodeData* arr[], int bottom, int top) 
{ 


    if (bottom <= top) 
    { 
     int middle = (bottom + top)/2; 

     if (arr[middle] == NULL) 
     { 
      return; 
     } 
     else 
     { 
      insert(root, arr[middle]); 
      arr[middle] = NULL; 

      insertMiddle(arr, bottom, middle - 1); 
      insertMiddle(arr, middle + 1, top); 
     } 
    } 
    else 
    { 
     return; 
    } 
} 

모든 노드를 삽입 한 후에도 루트는 여전히 NULL입니다. 사실 insert 함수의 첫 번째 if 문은 매번 true로 바뀝니다.
첫 번째 삽입 후 null이 아니어야합니다.
아무 것도 삭제하지 않거나 루트를 NULL로 설정할 필요가 없다고 생각합니다.

코드에 무슨 문제가 있습니까?

Answer 1

코드의 정확성을 확인할 수는 없지만 지금 당면하고있는 문제가 있다고 생각합니다. insert은 노드에 temp 포인터를 가져오고 할당 된 노드 중 하나 인 new 노드로 변경합니다. 그러나 포인터 temp는 값에 의해 전달되는, 그래서 전달 된 매개 변수의 사본 변경되기 때문에 기능 insert

temp = new Node; 

내부의 할당은, 발신자에 표시되지 않습니다. 당신은 함수 내에서

insert(root, arr[middle]); 

(값에 의해 전달) 매개 변수 temp의 변화를 호출 할 때 insert 호출자에 root의 값을 변경하지 않습니다.

void BinTree::insert(Node*& temp, NodeData * insData) 
         ^^^ 

이런 식으로, 임시 형 pointer-to-Node의 매개 변수가하고있다 : 당신이 호출자에 의해 전달 된 매개 변수를 변경하는 기능 insert를 원하는 경우

, 참조에 의해 매개 변수 를 전달하는 프로토 타입을 변경 참조로 전달. 포인터에 대한 변경 사항은 호출자 코드에 표시됩니다.