2017-12-28 106 views
0

議題は、ostream演算子を使用してAVLツリーの内容を出力することです。内容は特定の形式で印刷する必要があります。AVLツリーのOstream演算子C++

ツリーはテンプレートを使用して実装されています。 シンプルな主な実装です。

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); 
     } 
    } 

私は印刷のための2つのヘルパー関数を持っています。

は「」あなたは木の最後の要素を検出する方法を、印刷されることになっていない私が手出力が要求出力が

{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 << " "; 
} 

はあなたの内部ロジックと条件を交換してください:

+0

左と右の印刷の間にコンマが表示されるようです。おそらく最後には何も印刷されませんか? –

+1

また、やや異なったアプローチを取って、コンマ*ファースト*を出力に印刷して最後に印刷しないでください。そうすれば、末尾にカンマが現れることはありません。ノードが最初に印刷されるかどうかを検出するIMOは、それが印刷される最後のノードであるかどうかを検出しようとするよりも把握が容易です。 – PaulMcKenzie

答えて

0

は、単純なif statement条件を導入します。

+0

私は質問を更新しました。私は実際に条件を必要とし、条件のロジックはツリーの終わりを検出することになっています。 –

+0

私は質問を再構成しなければなりませんでした。目的は正しい書式を得ることでした。つまり、 "、"は印刷しないでください。しかし、私は同じことを確認するための条件が必要でした。私は "条件"が必要であることを理解していますが、私の質問は "some_condition_of_yours"に焦点を当てています。どのように私はそれに着きますか? –

0

私はこれを達成するために見ることができる2つの方法:

1.

はその後に}を追加し、その後、(間隔に応じて)最後の2つのまたは3文字を落とし、変数内の文字列、店舗を生成します形式を閉じてostreamに出力してください。最初の印刷機能を入力する場合、0にカウンタを設定

、及び毎回増分ノードを処理します。これにより、印刷されたアイテムの総数が表示されます。これをAVLツリーのアイテムの総数と比較することができます。どこかでアイテムの総数を追跡する必要があります。

私はオプション1を使用します。これは今実装が簡単なためです。また、AVLツリーは、その中にいくつのアイテムがあるかを知っているべきではありません。また、ツリーのサイズが大きいほど、より多くのifステートメントとcountのインクリメントが存在するため、印刷が遅くなります。これらの2つの操作は最小限に抑えられますが、数千または数百万のアイテムが得られれば、それは合計されます。

0

右に何かがあるかどうかを知るために、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); 
     } 
    } 
0

この問題を考えるための別の方法は、最後に、コンマ最初を印刷することはないです(注意テストしていません)。この方法では、最初の項目が印刷されるので、後にコンマを入力することはありません。ヘルパー関数で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トラック。この場合、カンマは印刷されません。そうでない場合はカンマが印刷されます。

+0

ちょっと試しました.. 無効な出力{1:1.1,2:2.23:3.3,4:4.4,5:5.5,6:6.6,7:7.7,8:8.8} は{1:1.1,2 :2.2,3:3.3,4:4.4,5:5.5,6:6.7,7.7,7,8:8.8}。 違いは非常に微妙ですが、なんらかの理由で「スペースなし」が表示されます。 –

+0

私が与えた答えにコードがあると、その出力は非常に起こりそうにないようです。 'operator <<'は2つのパラメータ 'print'を呼び出し、' firstTime'変数は何かが最初に出力されるときに即座に 'false'に設定されます。オリジナルの投稿で何をすべきかは、上記のコードで 'print'関数をどのように呼び出すかを示す[mcve]です。明らかに、実際のコードは単に 'print(param1、param2)'を呼び出す以外の何かをしています。あなたのコードをデバッグして、ブール値の 'false'への明白な設定が固執しない理由を調べることもできます。 – PaulMcKenzie

+0

さらに、このコードでは、 'operator <<'に 'AVLTree'が与えられたツリーを表示しようとしていることを前提としています。その1つのパラメータ 'print'は元のポストで機能します。それはどんな使い方も表示せず、' operator << 'によっても使われません。では、単一のパラメータ 'print'関数の目的は何ですか? – PaulMcKenzie

0

しばらくして問題の原因を突き止め、簡単な解決策を考え出すことができたので、忘れる前に答えを投稿することにしました。

ツリーの左辺と右辺の両方に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; 
    } 

もスタックにそれらをプッシュすると最後の文字をpopingし、完全にスタックを印刷する別のオプションがありました、これは私が必要なものに非常に近かったが、木が近くに15,000ノードを持っていたとして、非常に効率が悪いですその上に。