이진 검색 트리의 배열 구현

Question

1D 배열을 사용하여 이진 검색 트리를 만듭니다. 내 문제는 삽입 기능입니다.

트리를 출력 할 때 5, 8, 3, 1, 4 및 9를 삽입하면 올바른 색인이 생성됩니다. 그러나 트리에 9 이후에 숫자를 추가하려고하면 인덱스가 잘못됩니다. 예를 들어 앞에서 언급 한 숫자의 경우 9의 지수는 7입니다. 15의 지수 대신 9의 오른쪽 자식 인 17을 삽입하면 색인은 11입니다.

어떻게 내가 증분 내가하지만 나는 그것을 고쳐야할지 모르겠다. 어떤 도움을 주셔서 감사합니다. 감사! 노드에 대한 포인터 temp에서 유지되고 노드의 인덱스가 i에 보관 :

void insert(int x)    
    { 
    int i = 1; //Counter 

    if (ptr->arr[1] == -1) //If bst is empty. 
    { 
     ptr->arr[1] = x; 
    } 
    else      
    { 
     int *temp = &ptr->arr[1]; //Temp starts at root 
     int *parent = NULL; 
     while (*temp != -1 && *temp != x) 
     { 
      if (x < *temp) 
      { 
       parent = temp; 
       temp = &ptr->arr[i*2]; 
       i++; 
      } 

      else 
      { 
       parent = temp; 
       temp = &ptr->arr[i*2+1]; 
       i+=2; 
      } 

     } 

     *temp = x; 

    } 

Answer 1

당신은 두 개의 서로 다른 변수의 현재의 노드를 유지하고 있습니다. 이것 자체로 - 아마도 최적은 아니지만 - 문제가 아닙니다. 그러나 두 변수의 일관성을 유지하지는 않습니다 (포인터를 색인과 다르게 갱신합니다). 간단한 수정이 일관성을 유지하는 것입니다 :

제 생각에는

temp = &ptr->arr[i*2]; //the pointer update is correct 
i = i * 2; //same update as above 
//... 
temp = &ptr->arr[i*2+1]; 
i = i * 2 + 1; //same update as above 

, 또한 완전히 포인터 temp을 삭제하고 항상 인덱스 배열에 액세스하는 것이 좋습니다. 이것은 두 변수 사이의 동기화를 필요로하지 않습니다.