C Как "нарисовать" двоичное дерево на консоли [закрыто]

код:

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

выход:

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

или

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

некоторые подсказки: расстояние между узлами на той же глубине, (например, 2 и 4 или 3 и 8 в вашем примере), является функцией глубины.

каждая напечатанная строка состоит из всех узлов с одинаковой глубиной, напечатанных от самого левого узла до самого правого узла.

поэтому вам нужен способ, например, расположить ваши узлы в массивах строк, в соответствии с их глубиной, в порядке их наибольшей левой части.

начиная с корневого узла, a в ширину поиск будет посещать узлы в порядке глубины и наибольшей левой части.

расстояние между узлами можно найти, найдя максимальную высоту дерева, используя некоторую постоянную ширину для самых глубоких узлов и удваивая эту ширину для каждой меньшей глубины, так что ширина для любой глубины = ( 1 + maxdepth - currentdepth ) * deepestwidth.

Это число дает вам напечатанную "горизонтальную ширину" каждого узла на любой конкретной глубине.

левый узел горизонтально расположенный в левой половине ширины своего родителя, узел righ в правой половине. Вы будете вставлять фиктивные распорки для любого узла, у которого нет родителей; более простой способ сделать это-убедиться, что все листья находятся на той же глубине, что и самый глубокий узел, с пробел как их стоимость. Очевидно, вам также придется компенсировать ширину значений, возможно, сделав ширину наибольшей глубины по крайней мере такой же широкой, как печатное (десятичное представление, предположительно)самого большого ценного узла.

вот еще один дубль, когда дерево реализовано в массиве:

#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;
}

выход:

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

у меня есть это маленькое решение в c++ - оно может быть легко преобразовано в c.

мое решение требует дополнительной структуры данных для хранения глубины текущего узла в дереве (это потому, что если вы работаете с неполным деревом, глубина данного поддерева может не соответствовать его глубине в полном дереве.)

#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;
}

Он выводит следующее:

        0                                                                                                
    1       2                                                                                            
  3   4   5   6                                                                                          

посмотрите на вывод команды pstree в Linux. Он не производит вывод в точной форме, которую вы хотите, но IMHO это более читабельно таким образом.

Я поддерживаю рекомендацию litb. Мне пришлось сделать это в последнее время, чтобы напечатать дерево VAD процесса Windows, и я использовал язык точек (просто распечатайте узлы из своей двоичной функции ходьбы по дереву):

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

например, ваш точечный файл будет содержать:

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

вы создаете график с dotty.exe или конвертировать его в PNG с помощью dot.исполняемый.

очень простое решение c++ печать дерева в горизонтальном направлении:

5
  1
    5
  9
    7
    14

код (Node::print() функция-это то, что имеет значение):

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

Я думаю, что вы не должны кодировать это сами, но посмотрите на Tree:: Visualize что кажется хорошей реализацией Perl с различными возможными стилями и использованием/портом одного из алгоритмов там.

У меня есть программа Ruby, которая вычисляет координаты, где каждый узел в двоичном дереве должен быть нарисован здесь:http://hectorcorrea.com/Blog/Drawing-a-Binary-Tree-in-Ruby

этот код использует очень простой алгоритм для вычисления координат и это не "эффективным", но это хорошее начало. Если вы хотите увидеть код "live", вы можете проверить его здесь:http://binarytree.heroku.com/