c++ - C++ で BST を出力する方法

Question

私の C++ プログラムは二分探索木を作成します。プレオーダー、ポストオーダー、インオーダーで値を出力する方法を知っています。

でも、もう少し難しいことをやりたい。誰かが木を紙に描いた場合と同じように、値を印刷したいと思います。上部の中央にルートがあり、その真下の左に左の子があり、その真下の右に右の子があります。残りのノードはそれに応じて描画されます。

どうやってやるの？

Answer 1

この記事には、必要なもののコードが含まれています。

代替テキスト http://www.cpp-programming.net/wp-content/uploads/2007/12/ascii_tree.jpg

編集：そのサイトはオフラインになりました

これは、他のいくつかのオプションを調査する別のものです。

Answer 2

これを行うためのおおよその擬似コードを次に示します。基本的な考え方は、ツリーをレイヤーごとにたどって、各レイヤーのすべてのノードを 1 行に出力することです。各ノードは、その下のノードの 2 倍のスペースで区切られています。ツリーはすべてが均一な深さではないため、仮想ノードで人為的にパディングされ、ノードが存在しない空白スペースを占有します。

measure the depth of the tree, call that D
have two queues, called Q1 and Q2
enque the top node of the tree in Q1
for (i = D; --i>=0; ){
  foreach node in Q1 {

    on first iteration of this inner loop, print 2^i - 1 spaces,
    else print 2^(i+1) - 1 spaces.

    if node == null print blank
    else print node.value

    if node.left exists enque node.left in Q2
    else enque null in Q2

    if node.right exists enque node.right in Q2
    else enque null in Q2
  }
  copy Q2 to Q1
  clear Q2
  print end-of-line
}

印刷される各スペースは、1 つの数値フィールドの幅です。ツリーの深さが D = 4 であるとします。この場合、出力は次のようになります。

// it looks like this, and the space sequences are
i = 3: -------n 7
i = 2: ---n-------n 3 7
i = 1: -n---n---n---n 1 3 3 3
i = 0: n-n-n-n-n-n-n-n 0 1 1 1 1 1 1 1

Answer 3

    void print(node *p,int start)
    {
        start++;
        if (p->right != NULL)
        {
            print(p->right,start);
        }
        for (int i = 0; i <= start; i++)
        {
            cout<<"    ";
        } 
        cout << p->value<<endl;
        if (p->left != NULL)
        {
            print(p->left, start);
        }
    }

Answer 4

1 つの方法は、graphviz を使用することです。具体的には、その「ドット」プログラムを使用しますが、記述どおりに出力を正確に表示することはできない場合があります。

Answer 5

まあ、端末では難しいです...収まらないかもしれないので。しかし、素敵な画像を作成できるグラフ描画ライブラリが世の中にあります。最も人気のあるグラフビズがあります。

編集：本当にテキストを印刷したいだけなら、graphvisには、ユーザーがgraphvisに渡すことができるマークアップ言語があり、それが素敵な画像を作成します。