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

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)                                                       

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.

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

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                                                                                          

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.

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.

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();
}

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/

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.