wake-up-neo.com

C So "zeichnen" Sie einen Binärbaum in die Konsole

Mit welchen Algorithmen kann ein Binärbaum in der Konsole gezeichnet werden? Der Baum ist in C implementiert. Ein BST mit den Nummern: 2 3 4 5 8 würde in der Konsole angezeigt als:

alt text

67
Marek Szanyi

Check out 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("/");
          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(t);
      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];  
    };

ausgabe:

        2
       / \
      /   \
     /     \
    1       3
   / \     / \
  0   7   9   1
 /   / \     / \
2   1   0   8   8
       /
      7
40
Jonas Elfström

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)                                                       
43
user1571409

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 Zeile besteht aus allen Knoten mit derselben Tiefe, die vom linken bis zum rechten Knoten gedruckt werden.

Sie müssen also die Möglichkeit haben, Ihre Knoten beispielsweise in Reihen anzuordnen, und zwar entsprechend ihrer Tiefe in der Reihenfolge ihrer äußersten Linken.

Ausgehend vom Wurzelknoten werden mit Breitensuche die Knoten in der Reihenfolge der Tiefe und der äußersten Linken gesucht.

Der Abstand zwischen den Knoten kann ermittelt werden, indem die maximale Höhe des Baums unter Verwendung einer konstanten Breite für die tiefsten Knoten ermittelt und diese Breite für jede geringere Tiefe verdoppelt wird, sodass die Breite für jede Tiefe = (1 + maxdepth - currentdepth) * deepestwidth .

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 übergeordneten Knotens, ein rechter Knoten in der rechten Hälfte. Sie fügen Platzhalter für jeden Knoten ein, der keine übergeordneten Knoten hat. Eine einfachere Möglichkeit besteht darin, sicherzustellen, dass sich alle Blätter in der gleichen Tiefe wie der tiefste Knoten befinden, mit leer als Wert. Offensichtlich müssen Sie auch die Breite der Werte ausgleichen, indem Sie die Breite der größten Tiefe möglicherweise mindestens so breit machen, wie die gedruckte (vermutlich dezimale) Darstellung des Knotens mit dem größten Wert.

19
tpdi

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

#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
11
Bula

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

Für meine Lösung ist eine zusätzliche Datenstruktur erforderlich, um die Tiefe des aktuellen Knotens im Baum zu speichern. (Wenn Sie mit einem unvollständigen Baum arbeiten, stimmt die Tiefe eines bestimmten Unterbaums möglicherweise nicht mit der Tiefe im gesamten Baum überein.)

#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 wird folgendes ausgedruckt:

        0                                                                                                
    1       2                                                                                            
  3   4   5   6                                                                                          
8
Steve Lorimer

Schauen Sie sich die Ausgabe des Befehls pstree unter Linux an. Die Ausgabe wird nicht in der gewünschten Form erstellt, aber auf diese Weise ist sie besser lesbar.

3
Anonymous

Ich empfehle litb. Ich musste dies in letzter Zeit tun, um den VAD-Baum eines Windows-Prozesses zu drucken, und ich verwendete die DOT-Sprache (drucke einfach Knoten aus deiner Binärbaum-Walking-Funktion aus):

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

Zum Beispiel würde Ihre DOT-Datei enthalten:

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

Sie generieren den Graphen mit dotty.exe oder konvertieren ihn mit dot.exe nach PNG.

3
Martin

Ein sehr einfacher C++ - Lösungsdruckbaum in horizontaler Richtung:

5
  1
    5
  9
    7
    14

Code (Node::print() function ist das was zählt):

#include<iostream>

using namespace std;

class Tree;

class Node{
public:
    Node(int val): _val(val){}
    int val(){ return _val; }
    void add(Node *temp)
    {
        if (temp->val() > _val)
        {
            if (_rchild)
                _rchild->add(temp);
            else
            {
                _rchild = temp;
            }
        }
        else
        {
            if (_lchild)
                _lchild->add(temp);
            else
            {
                _lchild = temp;
            }
        }
    }
    void print()
    {
        for (int ix = 0; ix < _level; ++ix) cout << ' ';
        cout << _val << endl;
        ++_level;
        if (_lchild)
        {
            _lchild->print();
            --_level;
        }
        if (_rchild)
        {
            _rchild->print();
            --_level;
        }
    }
private:
    int _val;
    Node *_lchild;      
    Node *_rchild;
    static int _level;      
};

int Node::_level = 0;       

class Tree{
public:
    Tree(): _root(0){}  
    void add(int val)
    {
        Node *temp = new Node(val);
        if (!_root)
            _root = temp;
        else
            _root->add(temp);       
    }
    void print()
    {
        if (!_root)
            return;
        _root->print();             
    }
private:
    Node *_root;    
};

int main()
{
    Tree tree;
    tree.add(5);
    tree.add(9);
    tree.add(1);
    tree.add(7);
    tree.add(5);
    tree.add(14);
    tree.print();
}
2
cpp

Ich habe ein Ruby Programm, das die Koordinaten berechnet, wo jeder Knoten in einem Binärbaum hier gezeichnet werden soll: http://hectorcorrea.com/Blog/Drawing-a- Binary-Tree-in-Ruby

Dieser Code verwendet einen sehr einfachen Algorithmus zur Berechnung der Koordinaten und ist nicht "flächeneffizient", aber ein guter Anfang. Wenn Sie den Code "live" sehen möchten, können Sie ihn hier testen: http://binarytree.heroku.com/

1
Hector Correa

Ich denke, Sie sollten das nicht selbst programmieren, sondern einen Blick auf Tree :: Visualize werfen, das eine nette Perl-Implementierung mit verschiedenen möglichen Stilen zu sein scheint und einen der dortigen Algorithmen verwendet/portiert.

1
schnaader