c++ - コンソールに二分探索木を正しく表示するには?

Question

コンソールに BST を表示しようとしています。それが私のコードです (これは、次のコードの修正版です: Printing Level Order Binary Search Tree Formatting ):

string printLevel(node *root, int level, string gap) {
  if (!root) {
    return gap + "-" + gap;
  }
  if (level==1) {
    stringstream out;
    out<<root->value;
    return gap + out.str() + gap;
  } else if (level>1) {
    string leftStr = printLevel(root->left, level-1, gap);
    string rightStr = printLevel(root->right, level-1, gap);
    return leftStr + " " + rightStr;
  } else return "";
}

void printLevelOrder (node* root, int depth) {
  for (int i=1; i<=depth; i++) {
    string gap="";
    for (int j=0; j<pow(2,depth-i)-1; j++) {
      gap+=" ";
    }
    string levelNodes = printLevel(root, i, gap);
    cout<<levelNodes<<endl;
  }
}

たとえば、結果は次のようになります。

       4
   1       6
 -   2   5   - 
- - - 3 - - - -

しかし、代わりに次のようになります。

       4       
   1       6
 -   2   5   -
- - 3 - - -

私が正しく理解していれば、プログラムが空のリーフに到達すると再帰が停止するため、結果の下位レベルに「 - 」がありません。しかし、下位レベルでどれだけ描画する必要があるかをどのように知ることができますか? これを機能させる方法は？

score 2 · Accepted Answer

どこで問題が発生したかを確認するためにコードをインストルメント化しました (ブラウザーでデバッガーを実行しているため...)。ここでライブを見ることができます。再現された関数は次のとおりです。

string printLevel(node *root, int level, string gap) {
  if (root == 0) {
    cout << ".. printLevel - " << root << ": " << gap << "-" << gap << "\n";
    return gap + "-" + gap;
  }
  if (level==1) {
    stringstream out;
    out<<root->value;
    cout << ".. printLevel - " << root << ": " << gap << root->value << gap << "\n";
    return gap + out.str() + gap;
  } else if (level>1) {
    string leftStr = printLevel(root->left, level-1, gap);
    string rightStr = printLevel(root->right, level-1, gap);

    cout << ".. printLevel - " << root << ": '" << leftStr << "', '" << rightStr << "'\n";
    return leftStr + " " + rightStr;
  } else return "";
}

そして、ここに興味深い出力があります。

.. printLevel - <none>: -
.. printLevel - <none>: -
.. printLevel - { 3, <none>, <none> }: 3
.. printLevel - { 2, <none>, { 3, <none>, <none> } }: '-', '3'
.. printLevel - { 1, <none>, { 2, <none>, { 3, <none>, <none> } } }: '-', '- 3'

したがって、問題は、が 0 のときはいつでも短絡することですroot。これは実際には問題です。がでない限り、は-正しい出力ではありません。level1

root0 であることと 0 でないことの唯一の違いはroot、値を読み取ることができないことです (したがって、で置き換えることができます-)。ただし、実際にその値を読み取るのはその値だけlevelです(注意してください1。読み取ろうとする可能性があります)。したがって、ブランチにいない限り、テストする理由はありません。leftrightroot == 0level == 1

少し並べ替えてみましょう。

string printLevel(node *root, int level, string gap) {
  if (level==1) {
//    if (root == 0) {
//      cout << ".. printLevel - " << root << ": " << gap << "-" << gap << "\n";
//      return gap + "-" + gap;
//    }
    stringstream out;
    out<<root->value;
    cout << ".. printLevel - " << root << ": " << gap << root->value << gap << "\n";
    return gap + out.str() + gap;
  } else if (level>1) {
//    string leftStr = printLevel(root ? root->left : 0, level-1, gap);
//    string rightStr = printLevel(root ? root->right : 0, level-1, gap);

    cout << ".. printLevel - " << root << ": '" << leftStr << "', '" << rightStr << "'\n";
    return leftStr + " " + rightStr;
  } else return "";
}

注: 変更された行を「コメント」で「強調表示」しました。

これで、ツリーが正しく印刷されます。

score 2 · Accepted Answer

void BinaryTree::Display(TreeNode *current, int indent)
{
    if (current != nullptr)
    {
        Display(current->left, indent + 4);
        if (indent > 0)
            cout << setw(indent) << " ";
        cout << current->value << endl;
        Display(current->right, indent + 4);
    }
}

ツリーを上からではなく左から右に出力します。

c++ - コンソールに二分探索木を正しく表示するには?

3 に答える 3

Related

Reference