So drucken Sie ein BST in C ++ aus

Question

Mein C ++ - Programm erstellt einen binären Suchbaum. Ich weiß, wie man die Werte vorbestellt, nach der Bestellung und in Ordnung ausdruckt.

Ich möchte jedoch etwas Schwierigeres tun. Ich möchte die Werte so ausdrucken, wie er aussehen würde, wenn jemand den Baum auf Papier zeichnet. Es würde die Wurzel in der Mitte oben haben, es ist ein linkes Kind rechts unter und links von es und es ist rechts unter und rechts von rechts. Der Rest der Knoten würde entsprechend gezeichnet.

Wie kann ich das machen?

Answer 1

Dieser Artikel Enthält Code für das, was Sie brauchen, scheint:

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

Bearbeiten: Diese Seite ging offline

Hier ist noch einer einige andere Optionen erkunden.

Answer 2

Hier finden Sie einen ungefähren Pseudo-Code, um dies zu tun. Die Grundidee ist, die Baumschicht für Schicht zu laufen und den gesamten Knoten in jeder Ebene auf einer Zeile zu drucken. Jeder Knoten wird durch doppelt so viel Platz wie die Knoten darunter getrennt. Da der Baum nicht die gesamte einheitliche Tiefe ist, ist er mit virtuellen Knoten künstlich gepolstert, um die leeren Räume aufzunehmen, in denen Knoten nicht existieren.

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
}

Jeder gedruckte Raum ist die Breite eines numerischen Feldes. Angenommen, der Baum hat Tiefe d = 4. Dann lautet der Druck wie folgt:

// 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

Eine Möglichkeit besteht darin, GraphViz zu verwenden. Verwenden Sie insbesondere das "DOT" -Programm, aber die Ausgabe ist möglicherweise nicht möglich.

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

Nun, in einem Terminal ist es schwer ... da es möglicherweise nicht passt. Es gibt jedoch Bibliotheken für Grafikzeichnungen, die schöne Bilder für Sie machen können. Es gibt Graphvis, das eines der beliebtesten ist.

Bearbeiten: Wenn Sie wirklich nur einen Text drucken möchten, verfügt Graphvis über eine Markup -Sprache, die ein Benutzer an Graphvis übergeben kann, das wiederum die schönen Bilder macht.