배열 기반 바이너리 검색 트리 C++로 나를 도울 수 있습니까?

Question

이것은 내가 지금까지 가지고있는 것이다.

void BST::insert(const data& aData) 
{ 
    if (items[root_index].empty) 
    { 
     items[root_index].theData = aData;// Get the data. 
     items[root_index].empty = false; 
     oldRoot.theData = aData; 
    } 
    else 
    { 
     if (aData < items[root_index].theData) 
     { 
      leftChild = root_index * 2; 
      if (items[leftChild].empty) 
      { 
       items[leftChild].theData = aData; 
       items[leftChild].empty = false; 
      } 
      else 
      { 
       root_index++; 
       items[root_index].theData = items[leftChild].theData;       
            items[root_index].empty = false; 
       this->insert(aData); 
      } 
     } 
     else if (items[root_index].theData < aData) 
     { 
      rightChild = root_index * 2 + 1; 
      if (items[rightChild].empty) 
      { 
       items[rightChild].theData = aData; 
       items[rightChild].empty = false; 
      } 
      else 
      {//this where the problem is for "Z" insertion 
       root_index++; 
       items[root_index].theData = items[rightChild].theData; 
       items[root_index].empty = false; 
       this->insert(aData); 
      } 
     } 
     else return; 
    } 
    items[1].theData = oldRoot.theData; 
} 

생성자 : 그것은 작품을 나던

BST::BST(int capacity) : items(new item[capacity]), size(0), 
leftChild(0), rightChild(0), root_index(1) 
{ 
    items->empty = true; 
    maxSize = capacity-1; 
} 

. 나는 이유를 모른다. 나는 균형을 이루도록 코드를 작성하는 것 같다. 내가 "Z"를 삽입 할 때

 R 
    /
    A 
     \ 
     F 

, "R", "A"및 "F"를 삽입, 그래서 F의 권리 자식이 : 내가 지금까지 가지고하는 것은 유사한 나무입니다.

 R 
    /\ 
    A Z 
     \ 
     F 

누군가가 나에게 그런 식으로 활용할 수 있도록 수 :하지만 정말 루트의 권리 자녀해야 하는가?

Answer 1

나는 뭔가를 놓칠 수 있지만 코드는 모든 종류의 엉망으로 보입니다. root_index++, 데이터를 트리에 추가 한 후 에 대한 재귀 호출 ...이 드로잉 보드로 돌아가고 싶을 수 있습니다.

배열을 사용하는 주된 이유 인 완전한 이진 검색 트리를 사용할 경우 배열에 새 요소를 추가하고 트리 순서 불변량을 파기하는 요소를 이동할 수 있습니다 (왼쪽 자손 < 및 노드 < 오른쪽 자손)를 나무 위로 올리십시오.