C Wie man einen Binärbaum auf die Konsole “zeichnet”. [closed]

Lesezeit: 13 Minuten

Benutzeravatar von Marek Szanyi
Marek Szanyi

Welche Algorithmen können verwendet werden, um einen Binärbaum in der Konsole zu zeichnen? Der Baum ist in C implementiert. Beispielsweise würde ein BST mit den Zahlen: 2 3 4 5 8 in der Konsole wie folgt angezeigt:

Alt-Text

  • Erstellen Sie eine .dot-Datei mit Ihren Knoten und Kanten und rendern Sie sie mit graphviz. Sieht ordentlich aus

    – Johannes Schaub – litb

    29. April 2009 um 10:41 Uhr

  • @litb: schön. Ich habe tatsächlich eine Renderliste und einen Framebuffer implementiert und meine eigenen BMPs generiert!

    Benutzer82238

    21. Mai 2009 um 22:13 Uhr

  • Bitte Bild aktualisieren 🙂

    – Andreas Storvik Straumann

    18. Mai 2015 um 16:05 Uhr

Benutzeravatar von Jonas Elfström
Jonas Elfström

Kasse Drucken von Binärbäumen in ASCII

Von @AnyOneElse Pastbin unten:

!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!Code originally from /http://www.openasthra.com/c-tidbits/printing-binary-trees-in-ascii/
!!! Just saved it, cause the website is down.
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
Printing Binary Trees in Ascii

Here we are not going to discuss what binary trees are (please refer this, if you are looking for binary search trees), or their operations but printing them in ascii.

The below routine prints tree in ascii for a given Tree representation which contains list of nodes, and node structure is this

    struct Tree 
    {
      Tree * left, * right;
      int element;
    };

This pic illustrates what the below routine does on canvas..
ascii tree

Here is the printing routine..

    b5855d39a6b8a2735ddcaa04a404c125001 

Auxiliary routines..

    //This function prints the given level of the given tree, assuming
    //that the node has the given x cordinate.
    void print_level(asciinode *node, int x, int level) 
    {
      int i, isleft;
      if (node == NULL) return;
      isleft = (node->parent_dir == -1);
      if (level == 0) 
      {
        for (i=0; i<(x-print_next-((node->lablen-isleft)/2)); i++) 
        {
          printf(" ");
        }
        print_next += i;
        printf("%s", node->label);
        print_next += node->lablen;
      } 
      else if (node->edge_length >= level) 
      {
        if (node->left != NULL) 
        {
          for (i=0; i<(x-print_next-(level)); i++) 
          {
            printf(" ");
          }
          print_next += i;
          printf("https://stackoverflow.com/");
          print_next++;
        }
        if (node->right != NULL) 
        {
          for (i=0; i<(x-print_next+(level)); i++) 
          {
            printf(" ");
          }
          print_next += i;
          printf("\\");
          print_next++;
        }
      } 
      else 
      {
        print_level(node->left, 
                    x-node->edge_length-1, 
                    level-node->edge_length-1);
        print_level(node->right, 
                    x+node->edge_length+1, 
                    level-node->edge_length-1);
      }
    }


    //This function fills in the edge_length and 
    //height fields of the specified tree
    void compute_edge_lengths(asciinode *node) 
    {
      int h, hmin, i, delta;
      if (node == NULL) return;
      compute_edge_lengths(node->left);
      compute_edge_lengths(node->right);

      /* first fill in the edge_length of node */
      if (node->right == NULL && node->left == NULL) 
      {
        node->edge_length = 0;
      } 
      else 
      {
        if (node->left != NULL) 
        {
          for (i=0; i<node->left->height && i < MAX_HEIGHT; i++) 
          {
            rprofile[i] = -INFINITY;
          }
          compute_rprofile(node->left, 0, 0);
          hmin = node->left->height;
        } 
        else 
        {
          hmin = 0;
        }
        if (node->right != NULL) 
        {
          for (i=0; i<node->right->height && i < MAX_HEIGHT; i++) 
          {
            lprofile[i] = INFINITY;
          }
          compute_lprofile(node->right, 0, 0);
          hmin = MIN(node->right->height, hmin);
        } 
        else 
        {
          hmin = 0;
        }
        delta = 4;
        for (i=0; i<hmin; i++) 
        {
          delta = MAX(delta, gap + 1 + rprofile[i] - lprofile[i]);
        }

        //If the node has two children of height 1, then we allow the
        //two leaves to be within 1, instead of 2 
        if (((node->left != NULL && node->left->height == 1) ||
              (node->right != NULL && node->right->height == 1))&&delta>4) 
        {
          delta--;
        }

        node->edge_length = ((delta+1)/2) - 1;
      }

      //now fill in the height of node
      h = 1;
      if (node->left != NULL) 
      {
        h = MAX(node->left->height + node->edge_length + 1, h);
      }
      if (node->right != NULL) 
      {
        h = MAX(node->right->height + node->edge_length + 1, h);
      }
      node->height = h;
    }

    asciinode * build_ascii_tree_recursive(Tree * t) 
    {
      asciinode * node;

      if (t == NULL) return NULL;

      node = malloc(sizeof(asciinode));
      node->left = build_ascii_tree_recursive(t->left);
      node->right = build_ascii_tree_recursive(t->right);

      if (node->left != NULL) 
      {
        node->left->parent_dir = -1;
      }

      if (node->right != NULL) 
      {
        node->right->parent_dir = 1;
      }

      sprintf(node->label, "%d", t->element);
      node->lablen = strlen(node->label);

      return node;
    }


    //Copy the tree into the ascii node structre
    asciinode * build_ascii_tree(Tree * t) 
    {
      asciinode *node;
      if (t == NULL) return NULL;
      node = build_ascii_tree_recursive
      node->parent_dir = 0;
      return node;
    }

    //Free all the nodes of the given tree
    void free_ascii_tree(asciinode *node) 
    {
      if (node == NULL) return;
      free_ascii_tree(node->left);
      free_ascii_tree(node->right);
      free(node);
    }

    //The following function fills in the lprofile array for the given tree.
    //It assumes that the center of the label of the root of this tree
    //is located at a position (x,y).  It assumes that the edge_length
    //fields have been computed for this tree.
    void compute_lprofile(asciinode *node, int x, int y) 
    {
      int i, isleft;
      if (node == NULL) return;
      isleft = (node->parent_dir == -1);
      lprofile[y] = MIN(lprofile[y], x-((node->lablen-isleft)/2));
      if (node->left != NULL) 
      {
        for (i=1; i <= node->edge_length && y+i < MAX_HEIGHT; i++) 
        {
          lprofile[y+i] = MIN(lprofile[y+i], x-i);
        }
      }
      compute_lprofile(node->left, x-node->edge_length-1, y+node->edge_length+1);
      compute_lprofile(node->right, x+node->edge_length+1, y+node->edge_length+1);
    }

    void compute_rprofile(asciinode *node, int x, int y) 
    {
      int i, notleft;
      if (node == NULL) return;
      notleft = (node->parent_dir != -1);
      rprofile[y] = MAX(rprofile[y], x+((node->lablen-notleft)/2));
      if (node->right != NULL) 
      {
        for (i=1; i <= node->edge_length && y+i < MAX_HEIGHT; i++) 
        {
          rprofile[y+i] = MAX(rprofile[y+i], x+i);
        }
      }
      compute_rprofile(node->left, x-node->edge_length-1, y+node->edge_length+1);
      compute_rprofile(node->right, x+node->edge_length+1, y+node->edge_length+1);
    }

Here is the asciii tree structure…

    struct asciinode_struct
    {
      asciinode * left, * right;

      //length of the edge from this node to its children
      int edge_length; 

      int height;      

      int lablen;

      //-1=I am left, 0=I am root, 1=right   
      int parent_dir;   

      //max supported unit32 in dec, 10 digits max
      char label[11];  
    };

Ausgang:

        2
       / \
      /   \
     /     \
    1       3
   / \     / \
  0   7   9   1
 /   / \     / \
2   1   0   8   8
       /
      7

  • Genau was ich gesucht habe, vielen Dank!

    – Marek Szányi

    29. April 2009 um 10:54 Uhr

  • Leider scheint es so. Konnte es nicht im Google Cache oder auf dem Wayback-Computer des Internetarchivs finden. Das könnte es sein, ich habe es noch nicht versucht: datastructuresblog.wordpress.com/2007/12/21/…

    – Jonas Elfström

    9. Juli 2010 um 6:40 Uhr


  • Der Text scheint beschädigt zu sein, und der Codelink ist defekt. Wenn jemand den Code finden kann, bitte helfen! Ein Link zu Pastebin ist möglicherweise nicht falsch …

    – Norman Ramsey

    11. April 2011 um 3:32 Uhr

  • Gefunden, gespeichert! pastebin.com/d3AtFKAK und web.archive.org/web/20071224095835/http://www.openasthra.com/…

    – Irgendjemand anderes

    24. September 2013 um 9:04 Uhr

  • Ich habe dies vor ein paar Jahren auf JS portiert github.com/gaastonsr/treevis

    – Gaston Sánchez

    13. Juli 2020 um 21:34 Uhr

Benutzeravatar von user1571409
Benutzer1571409

Code:

int _print_t(tnode *tree, int is_left, int offset, int depth, char s[20][255])
{
    char b[20];
    int width = 5;

    if (!tree) return 0;

    sprintf(b, "(%03d)", tree->val);

    int left  = _print_t(tree->left,  1, offset,                depth + 1, s);
    int right = _print_t(tree->right, 0, offset + left + width, depth + 1, s);

#ifdef COMPACT
    for (int i = 0; i < width; i++)
        s[depth][offset + left + i] = b[i];

    if (depth && is_left) {

        for (int i = 0; i < width + right; i++)
            s[depth - 1][offset + left + width/2 + i] = '-';

        s[depth - 1][offset + left + width/2] = '.';

    } else if (depth && !is_left) {

        for (int i = 0; i < left + width; i++)
            s[depth - 1][offset - width/2 + i] = '-';

        s[depth - 1][offset + left + width/2] = '.';
    }
#else
    for (int i = 0; i < width; i++)
        s[2 * depth][offset + left + i] = b[i];

    if (depth && is_left) {

        for (int i = 0; i < width + right; i++)
            s[2 * depth - 1][offset + left + width/2 + i] = '-';

        s[2 * depth - 1][offset + left + width/2] = '+';
        s[2 * depth - 1][offset + left + width + right + width/2] = '+';

    } else if (depth && !is_left) {

        for (int i = 0; i < left + width; i++)
            s[2 * depth - 1][offset - width/2 + i] = '-';

        s[2 * depth - 1][offset + left + width/2] = '+';
        s[2 * depth - 1][offset - width/2 - 1] = '+';
    }
#endif

    return left + width + right;
}

void print_t(tnode *tree)
{
    char s[20][255];
    for (int i = 0; i < 20; i++)
        sprintf(s[i], "%80s", " ");

    _print_t(tree, 0, 0, 0, s);

    for (int i = 0; i < 20; i++)
        printf("%s\n", s[i]);
}

Ausgabe:

                           .----------------------(006)-------.                 
                      .--(001)-------.                   .--(008)--.            
                 .--(-02)       .--(003)-------.       (007)     (009)          
       .-------(-06)          (002)       .--(005)                              
  .--(-08)--.                           (004)                                   
(-09)     (-07)                     

oder

                                                  (006)                         
                           +------------------------+---------+                 
                         (001)                              (008)               
                      +----+---------+                   +----+----+            
                    (-02)          (003)               (007)     (009)          
                 +----+         +----+---------+                                
               (-06)          (002)          (005)                              
       +---------+                        +----+                                
     (-08)                              (004)                                   
  +----+----+                                                                   
(-09)     (-07)                                                       

  • +1 für die SCHÖNHEIT der rekursiven Implementierung und der Ausgabe.

    – AufDerEinfachstenWeg

    23. September 2014 um 2:56 Uhr

  • Ich habe versucht, dies mit einem Baum mit Zeichenfolgenwerten zu verwenden. Hat nicht wirklich gut funktioniert, selbst wenn die Breitenvariable erhöht wurde. Auch die feste Anzahl an Zeilen ist unglücklich.

    – Ray Hulha

    4. Oktober 2016 um 20:40 Uhr

Benutzeravatar von tpdi
tpdi

Einige Hinweise: Der Abstand zwischen Knoten gleicher Tiefe (z. B. 2 und 4 oder 3 und 8 in Ihrem Beispiel) ist eine Funktion der Tiefe.

Jede gedruckte Reihe besteht aus allen Knoten mit der gleichen Tiefe, gedruckt vom Knoten ganz links bis zum Knoten ganz rechts.

Sie brauchen also zum Beispiel eine Möglichkeit, Ihre Knoten in Zeilenarrays entsprechend ihrer Tiefe und in der Reihenfolge ihrer äußersten linken Position anzuordnen.

Ausgehend vom Wurzelknoten a Breitensuche besucht die Knoten in der Reihenfolge der Tiefe und ganz links.

Der Abstand zwischen Knoten kann ermittelt werden, indem die maximale Höhe des Baums ermittelt wird, wobei eine konstante Breite für die tiefsten Knoten verwendet wird und diese Breite für jede geringere Tiefe verdoppelt wird, sodass die Breite für jede Tiefe = ( 1 + maxdepth – currentdepth ) * deepestwidth ist .

Diese Zahl gibt Ihnen die gedruckte “horizontale Breite” jedes Knotens in einer bestimmten Tiefe.

Ein linker Knoten ist horizontal positioniert in der linken Hälfte der Breite des Elternteils, ein rechter Knoten in der rechten Hälfte. Sie fügen Dummy-Abstandshalter für jeden Knoten ein, der keine Eltern hat; Ein einfacherer Weg, dies zu tun, wäre sicherzustellen, dass alle Blätter in der gleichen Tiefe wie der tiefste Knoten sind, mit leer als ihren Wert. Natürlich müssen Sie auch die Breite der Werte kompensieren, vielleicht indem Sie die Breite der größten Tiefe mindestens so breit machen wie die gedruckte (dezimale Darstellung, vermutlich) des Knotens mit dem größten Wert.

Bula's Benutzer-Avatar
Bula

Hier ist eine weitere Einstellung, wenn ein Baum in einem Array implementiert wird:

#include <stdio.h>
#include <math.h>


#define PARENT(i) ((i-1) / 2)
#define NUM_NODES 15
#define LINE_WIDTH 70

int main() {
    int tree[NUM_NODES]={0,1,2,3,4,5,6,7,8,9,1,2,3,4,5};
    int print_pos[NUM_NODES];
    int i, j, k, pos, x=1, level=0;

    print_pos[0] = 0;
    for(i=0,j=1; i<NUM_NODES; i++,j++) {
        pos = print_pos[PARENT(i)] + (i%2?-1:1)*(LINE_WIDTH/(pow(2,level+1))+1);

        for (k=0; k<pos-x; k++) printf("%c",i==0||i%2?' ':'-');
        printf("%d",tree[i]);

        print_pos[i] = x = pos+1;
        if (j==pow(2,level)) {
            printf("\n");
            level++;
            x = 1;
            j = 0;
        }
    }
    return 0;
}

Ausgabe:

                                   0
                  1-----------------------------------2
          3-----------------4                 5-----------------6
      7---------8       9---------1       2---------3       4---------5

Benutzeravatar von Steve Lorimer
Steve Lorimer

Ich habe diese kleine Lösung in c++ – sie könnte leicht in c konvertiert werden.

Meine Lösung erfordert eine zusätzliche Datenstruktur, um die Tiefe des aktuellen Knotens innerhalb des Baums zu speichern (dies liegt daran, dass die Tiefe eines bestimmten Unterbaums möglicherweise nicht mit seiner Tiefe im vollständigen Baum übereinstimmt, wenn Sie mit einem unvollständigen Baum arbeiten.)

#include <iostream>
#include <utility>
#include <algorithm>
#include <list>

namespace tree {

template<typename T>
struct node
{
  T data;
  node* l;
  node* r;
  node(T&& data_ = T()) : data(std::move(data_)), l(0), r(0) {}
};

template<typename T>
int max_depth(node<T>* n)
{
  if (!n) return 0;
  return 1 + std::max(max_depth(n->l), max_depth(n->r));
}

template<typename T>
void prt(node<T>* n)
{
  struct node_depth
  {
    node<T>* n;
    int lvl;
    node_depth(node<T>* n_, int lvl_) : n(n_), lvl(lvl_) {}
  };

  int depth = max_depth(n);

  char buf[1024];
  int last_lvl = 0;
  int offset = (1 << depth) - 1;

  // using a queue means we perform a breadth first iteration through the tree
  std::list<node_depth> q;

  q.push_back(node_depth(n, last_lvl));
  while (q.size())
  {
    const node_depth& nd = *q.begin();

    // moving to a new level in the tree, output a new line and calculate new offset
    if (last_lvl != nd.lvl)
    {
      std::cout << "\n";

      last_lvl = nd.lvl;
      offset = (1 << (depth - nd.lvl)) - 1;
    }

    // output <offset><data><offset>
    if (nd.n)
      sprintf(buf, " %*s%d%*s", offset, " ", nd.n->data, offset, " ");
    else
      sprintf(buf, " %*s", offset << 1, " ");
    std::cout << buf;

    if (nd.n)
    {
      q.push_back(node_depth(nd.n->l, last_lvl + 1));
      q.push_back(node_depth(nd.n->r, last_lvl + 1));
    }

    q.pop_front();
  }
  std::cout << "\n";
}

}

int main()
{
  typedef tree::node<int> node;
  node* head = new node();
  head->l    = new node(1);
  head->r    = new node(2);
  head->l->l = new node(3);
  head->l->r = new node(4);
  head->r->l = new node(5);
  head->r->r = new node(6);

  tree::prt(head);

  return 0;
}

Es druckt Folgendes aus:

        0                                                                                                
    1       2                                                                                            
  3   4   5   6                                                                                          

  • Vielen Dank. Ich verwende Ihre Lösung, aber es gibt einen kleinen Fehler. Das zweite q.push_back(node_depth(nd.n->l, last_lvl + 1)) sollte q.push_back(node_depth(nd.n->r, last_lvl + 1)) sein.

    – versank

    18. Dezember 2012 um 2:55 Uhr


  • @sank – ich bin mir nicht sicher, wovon du sprichst – es tut berechne das node_depth des rechten Teilbaums bereits. Vielleicht hast du dich beim Kopieren vertippt? Arbeitscode hier: ideone.com/wrY8Vo

    – Steve Lorimer

    18. Dezember 2012 um 3:53 Uhr

Benutzeravatar von Anonymous
Anonym

Sehen Sie sich die Ausgabe des Befehls pstree unter Linux an. Es erzeugt die Ausgabe nicht genau in der gewünschten Form, aber meiner Meinung nach ist es auf diese Weise besser lesbar.

  • Vielen Dank. Ich verwende Ihre Lösung, aber es gibt einen kleinen Fehler. Das zweite q.push_back(node_depth(nd.n->l, last_lvl + 1)) sollte q.push_back(node_depth(nd.n->r, last_lvl + 1)) sein.

    – versank

    18. Dezember 2012 um 2:55 Uhr


  • @sank – ich bin mir nicht sicher, wovon du sprichst – es tut berechne das node_depth des rechten Teilbaums bereits. Vielleicht hast du dich beim Kopieren vertippt? Arbeitscode hier: ideone.com/wrY8Vo

    – Steve Lorimer

    18. Dezember 2012 um 3:53 Uhr

Benutzeravatar von Martin
Martin

Ich schließe mich der Empfehlung von litb an. Ich musste dies kürzlich tun, um den VAD-Baum eines Windows-Prozesses zu drucken, und ich habe die DOT-Sprache verwendet (drucken Sie einfach Knoten aus Ihrer Binärbaum-Walking-Funktion aus):

http://en.wikipedia.org/wiki/DOT_language

Ihre DOT-Datei würde beispielsweise Folgendes enthalten:

digraph graphname {
     5 -> 3;
     5 -> 8;
     3 -> 4;
     3 -> 2;
}

Den Graphen erzeugen Sie mit dotty.exe oder wandeln ihn mit dot.exe in PNG um.

  • Punkt ist fabelhaft, aber das Problem hier ist ASCII

    – Norman Ramsey

    11. April 2011 um 3:31 Uhr

  • Irgendwelche Hinweise zur Integration von DOT in C?

    – yuw444

    22. Juni um 17:00 Uhr

1417910cookie-checkC Wie man einen Binärbaum auf die Konsole “zeichnet”. [closed]

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy