이진 검색 트리 C++ (학부모)

Question

내 BST에 조금만 더 도움이 필요합니다. 이것은 내 BST를 삽입 할 때 모습입니다 :

R은, L은, J,

     R --Root at Index 0 
        /\ 
    L @ Index1  L NULL 
       /\ 
    J @ Index3 J NULL 
       /\ 
    G @ Index7 G NULL 

G

이 여기 일이 만드는 코드입니다.

void BST::insert(const data &aData) 
{ 
    if (items[Parent].empty) 
    { 
     items[Parent].theData = aData; // insert at leaf. 
     items[Parent].empty = false; 
     size++; 

     return; 
    }   
    for (int i = 0; i <= size; i++) 
    { 
     if (aData < items[Parent].theData) 
     { 
      if (items[2*i+1].empty) 
      { 
      items[2*i+1].theData = aData; 
      items[2*i+1].empty = false; 
      } 
      else 
          { 
      // we must already have a left child to some root. 
           Parent++; So make the previous data the root??? 
      if (items[Parent].empty) 
      { 
       items[Parent].theData = items[2*i+1].theData; 
       items[Parent].empty = false; 
       Parent = (i-1)/2; 
      } 
          } 
     } 
     else 
     { ...// do the same for data greater than but with items[2*i+2] } 

내 질문은 언제 새로운 루트를 만들어야합니까? 언제 새 루트를 만들어야합니까? 재평가를 위해?

이 방법이 맞습니까? 둘 다 내 게시물을 보는 사람들에게 감사드립니다 :)

// 생성자 BST 클래스 및 해당 개인 섹션. (내가 말을해야 오히려 퍼지)

BST::BST(int capacity) : items(new item[capacity]), size(0), Parent(0), 
leftChild(0), rightChild(0) 
{ 
    items->empty = true; 
    maxSize = capacity; 
} 
private: 
    int size; // size of the ever growing/expanding tree :) 
    int Parent; 
    int maxSize;  
    int leftChild; 
    int rightChild; 
    struct item 
    { 
     bool empty; 
     data theData; 
    }; 
    item *items; // The tree array 

Answer 1

당신의 논리는 잘못된 것으로 보인다 "경우"순서가가의 어떤 종류입니까?

if (items[2*i+1].empty) 
{ 
} 
else if (!items[2*i+1].empty) 
{ 
    if (items[2*i+1].empty) 
    { 
     // any code here is unreachable 
    } 
} 

Answer 2

재귀 적으로 다시 구현하는 것이 좋습니다. 이런 식으로 뭔가가 :

void BST::insert(const data& aData, int pos) { 
    if (items[pos].empty) { 
     // insert it here 
    } 
    else (aData < items[pos].theData) { 
     // go to left child 
     insert(aData, 2*pos + 1); 
    } 
    else { 
     // go to right child 
     insert(aData, 2*pos + 2); 
    } 
} 

그것은 leftChild 및 rightChild이 수업 시간에 무엇을하는지 부모 정말 분명하지 않다, 그러나 그것은 별개의 문제입니다.