Как визуализировать двоичное дерево в C ++

Question

Когда я реализовал двоичные деревья, одна из первых написанных утилит - это функция визуализации, которая по заданному дереву выводит его на экран.

Использование функции cout для печати ее каждый раз, как стопка, - проблема для меня, я не могу представить ценность своей работы.

Правильная печать деревьев в ASCII довольно сложна для понимания. Между тем, оно не может представлять ваше дерево и ваши операции в ясном виде.

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

Я ищу какой-то код, алгоритм или метод для отображения моего дерева. Я думаю использовать некоторые библиотеки, такие как GTK, QT, STL или WPF, потому что я работаю с Visual Studio C ++.

Можно ли их использовать? Какой лучше всего подходит?

Answer 1

Дерево также является графом; Вы можете использовать Graphviz просто отлично. И формат DOT очень просто для вывода. См. Примеры Graphviz , включая деревья .

Answer 2

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

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

Answer 3

Во-первых, для визуализации деревьев Graphviz не так уж сложно реализовать, если вы знаете, как заполнить скрипт точечного файла в пустом файле с помощью C / C ++.

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

Так что, если вам неудобно с DOT, Graphviz также предоставляет другие инструментыкак neato, fdp, sfdp, twopi, circo.Выберите тот, который лучше всего соответствует вашим целям.Узнайте больше о Graphviz здесь .Посмотрите на это image , как происходит ориентация данных в разных макетах.

Другой способ - просто кодировать дерево в командной строке, что довольно случайно.

Answer 4

Проверьте этот алгоритм здесь .
Печатает визуализацию ASCII для любого двоичного дерева.

                     0X0                     
                     / \                     
                    /   \                    
                   /     \                   
                  /       \                  
                 /         \                 
                /           \                
               /             \               
              /               \              
             /                 \             
            /                   \            
           /                     \           
         0X0                     0X0         
         / \                     / \         
        /   \                   /   \        
       /     \                 /     \       
      /       \               /       \      
     /         \             /         \     
   0X0         0X0         0X0         0X0   
   / \         / \         / \         / \   
  /   \       /   \       /   \       /   \  
0X0   0X0   0X0   0X0   0X0   0X0   0X0   0X0

Answer 5

Для простоты формата я использую комбинацию YEd Graph Editor и Trivial Graph Format .

Answer 6

Вы также можете сгенерировать латексный код и скомпилировать текстовый файл для получения pdf / eps. Проверьте это: http://hstuart.dk/2007/02/21/drawing-trees-in-latex/