C ++でBSTを印刷する方法

Question

私のC ++プログラムは、バイナリ検索ツリーを作成します。予約注文、郵便局、および注文で値を印刷する方法を知っています。

しかし、私はもう少し難しいことをしたいです。誰かが紙の上で木を描いた場合、彼らが見る方法で価値を印刷したいです。それは上部の中央に根があり、それは左の子供がその左下と左側にあり、それは右の子供がその右下と右側にあります。残りのノードはそれに応じて描画されます。

どうやってやるの？

Answer 1

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

Alt Text http://www.cpp-promginming.net/wp-content/uploads/2007/12/ascii_tree.jpg

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

これがそうです もう1つ 他のいくつかのオプションを探索します。

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

1つの方法は、graphvizを使用することです。具体的には、その「DOT」プログラムを使用しますが、説明と同じように出力を正確に見ることができない場合があります。

Answer 4

    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 5

well, in a terminal it's hard...since it may not fit. But there are graph drawing libraries out there that can make nice pictures for you. There is graphvis that is one of the most popular.

edit: if you really just wan to print text, graphvis has a markup language that a user can pass to graphvis that in turn makes the nice pictures.