AVL 트리 Ostream 연산자 C++

Question

일정은 ostream 연산자를 사용하여 AVL 트리의 내용을 인쇄하는 것입니다. 내용을 특정 형식으로 인쇄해야합니다.

트리는 템플릿을 사용하여 구현됩니다. 간단한 주요 구현.

AVLTree<int, float> tree; 
for(int i = 0; i < 10; i++) 
    tree.insert(i, i+0.1); 
cout << tree; 

ostream에 운영자

friend ostream& operator<<(ostream& out, const AVLTree& v) 
{ 
    out << "{"; 
    v.print(out, v.root); 
    out << "}"; 
    return out; 
} 


void print(AVLnode<KEY,INFO>* curr)const 
    { 
     if(curr) 
     { 
      print(curr->left); 
      print(curr->right); 
     } 
    } 

void print(ostream& out, AVLnode<KEY, INFO>* curr)const 
    { 
     if(curr) 
     { 
      print(out, curr->left); 
      out << curr->Key_ << ": " << curr->Info_<<", "; 
      print(out, curr->right); 
     } 
    } 

내가 인쇄이 개 도우미 기능을 가지고 있습니다.

은 ","당신이 나무의 마지막 요소를 감지하는 방법, 인쇄 안되어 내가 얻을 출력이 필요한 출력

{1:1.1, 2:2.1. 3:3.1, 4:4.1, 5:5.1, 6:6.1, 7:7.1, 8:8.1, 9:9.1} 

입니다

{1:1.1, 2:2.1. 3:3.1, 4:4.1, 5:5.1, 6:6.1, 7:7.1, 8:8.1, 9:9.1, } 

입니까? 나는 그 상태를 이해하지 못한다. 그것은 간단하지만 나는 그것을 보지 못한다.

out << curr->Key_ << ": " << curr->Info_; 
if (some_condition_of_yours) { 
    out << ", "; 
} 
else { 
    out << " "; 
} 

은 내부 로직과 조건 교체 :

Answer 1

간단한 if statement 조건을 소개합니다. 내가 볼 수

Answer 2

두 가지 방법으로이 작업을 수행합니다 :

1.

다음 (간격)에 따라 지난 2 개 또는 3 문자를 드롭, 문자열, 변수에 저장소를 생성 한 후 }로를 추가 형식을 닫은 다음 ostream으로 출력하십시오. 첫 번째 인쇄 기능을 입력 할 때

2.

0으로 카운터를 설정하고, 매 시간 처리 노드 증가. 그러면 인쇄 된 총 항목 수가 표시됩니다. 그런 다음 AVL 트리의 총 항목 수와 비교할 수 있습니다. 당신은 어딘가에 총 항목 수를 추적해야 할 것입니다.

지금 구현하기가 쉽기 때문에 옵션 1을 사용합니다. 또한 AVL 트리는 항목이 얼마나 많은지를 아는 일을해서는 안됩니다. 또한 if 문이 더 많고 count 단위가 증가하므로 트리가 커질수록 인쇄 속도가 느려집니다. 이 두 가지 작업은 최소한이지만 항목이 수천 또는 수백만 가지면 더할 수 있습니다.

Answer 3

오른쪽에 뭔가가 있는지 알기 위해 print()에 추가 매개 변수가 필요하다고 가정합니다. 예를함으로써

:

friend ostream& operator<<(ostream& out, const AVLTree& v) 
{ 
    out << "{"; 
    v.print(out, v.root, false); 
    out << "}"; 
    return out; 
} 


void print (ostream & out, AVLnode<KEY, INFO> * curr, bool proComma) const 
    { 
     if (curr) 
     { 
      bool proC2 = proComma || (NULL != curr->right); 

      print(out, curr->left, proC2); 

      out << curr->Key_ << ": " << curr->Info_; 

      if (proC2) 
       out << ", "; 

      print(out, proComma); 
     } 
    } 

Answer 4

이 문제에 대해 생각하는 또 다른 방법은 마지막 쉼표 첫을하지 인쇄하는 것입니다 (주의 테스트하지). 이렇게하면 첫 번째 항목이 인쇄되므로 쉼표를 사용하지 않습니다.(하지 시험) 헬퍼 기능에 bool 기준 변수를 도입함으로써 달성 될 수

:

friend ostream& operator<<(ostream& out, const AVLTree& v) 
{ 
    bool firstTime = true; 
    out << "{"; 
    v.print(out, v.root, firstTime); 
    out << "}"; 
    return out; 
} 


void print(ostream& out, AVLnode<KEY, INFO>* curr, bool& firstTime) const 
{ 
    if (curr) 
    { 
     print(out, curr->left, firstTime); 
     out << (firstTime?"":", ") << curr->Key_ << ": " << curr->Info_; 
     firstTime = false; 
     print(out, curr->right, firstTime); 
    } 
} 

가 인쇄되고 처음 여부 firstTime 트랙. 이 경우 쉼표가 인쇄되지 않으며, 그렇지 않으면 쉼표가 인쇄됩니다.

Answer 5

잠시 후 나는 문제가 무엇인지 알아 내고 간단한 해결책을 제시 할 수 있었고, 그렇게하기를 잊기 전에 대답을 게시하기로 결정했습니다.

나무의 왼쪽과 오른쪽 모두에 NULL이 있기 때문에 트리에서 마지막 노드를 감지하기가 정말로 어렵습니다. 따라서 전체 트리를 인쇄하고 여분의 문자를 삭제하면 트릭이 아주 잘되었습니다.

template<typename KEY, typename INFO> 
void AVLTree<KEY, INFO>:: print(ostream& out, AVLnode<KEY,INFO>* curr) const{ 
     //sstream operator to calc the output and delete (n-1) of the output.   
     out << "{"; 
     std::stringstream ss; 
     printHelp(ss, curr); 
     std::string output = ss.str(); 
     if (output.length() > 1) 
      output.erase(output.end()-2, output.end()); 

     out << output; 
     out << "}"; 
} 

template<typename KEY, typename INFO> 
void AVLTree<KEY, INFO>::printHelp(std::stringstream& ss, AVLnode<KEY, INFO>* curr) const{ 
    if(curr){ 
      printHelp(ss, curr->left); 
      ss << curr->Key_<< ": " << curr->Info_ << ", "; 
      printHelp(ss, curr->right); 
     } 
} 

그런 다음 ostream 연산자는 루트 노드를 매개 변수로 사용하는 인쇄 기능과 ostream 개체를 사용합니다.

friend ostream& operator<<(ostream& out, const AVLTree& v){ 
     v.print(out, v.root); 
     return out; 
    } 

또한 스택으로 그들을 밀어 마지막 문자를 저런 애하고 전체 스택을 인쇄의 또 다른 옵션이 있었다, 이것은 내가 필요한 것과 매우 가까이하지만 나무 가까이에 15,000 노드를했다으로 매우 비효율적이다 그 위에.