C Как «нарисовать» двоичное дерево на консоли [закрыто]
https://stackoverflow.com/questions/801740
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Какие алгоритмы можно использовать для рисования двоичного дерева в консоли?Дерево реализовано в C.Например, BST с цифрами:2 3 4 5 8 будет отображаться в консоли как:
Решение
Проверить Печать двоичных деревьев в Ascii
Из @AnyOneElse Pastbin ниже:
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!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];
};
выход:
2
/ \
/ \
/ \
1 3
/ \ / \
0 7 9 1
/ / \ / \
2 1 0 8 8
/
7
Другие советы
Код:
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 в вашем примере) является функцией глубины.
Каждая напечатанная строка состоит из всех узлов одинаковой глубины, напечатанных от крайнего левого узла до крайнего правого узла.
Итак, вам нужен способ, например, расположить узлы в массивах строк в соответствии с их глубиной и в порядке их левого расположения.
Начиная с корневого узла, поиск в ширину будет посещать узлы в порядке глубины и левого угла.
Расстояние между узлами можно найти, найдя максимальную высоту дерева, используя некоторую постоянную ширину для самых глубоких узлов и удваивая эту ширину для каждой меньшей глубины, чтобы ширина для любой глубины = ( 1 + максимальная глубина - текущая глубина ) * глубокая ширина. .
Это число дает вам напечатанную «горизонтальную ширину» каждого узла на любой конкретной глубине.
Левый узел расположен горизонтально расположен в левой половине ширины родительского узла, правый узел в правой половине.Вы вставите фиктивные прокладки для любого узла, у которого нет родителей;более простой способ сделать это — убедиться, что все листья находятся на той же глубине, что и самый глубокий узел, с пустой как их ценность.Очевидно, вам также придется компенсировать ширину значений, возможно, сделав ширину наибольшей глубины по крайней мере такой же ширины, как напечатанное (предположительно десятичное представление) узла с наибольшим значением.
Вот еще один вариант реализации дерева в массиве:
#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.Он не выдает результат в той форме, которую вы хотите, но, ИМХО, так он более читаем.
Я рекомендую вторую литб.Недавно мне пришлось сделать это, чтобы распечатать дерево VAD процесса Windows, и я использовал язык DOT (просто распечатайте узлы из вашей функции обхода двоичного дерева):
http://en.wikipedia.org/wiki/DOT_language
Например, ваш файл DOT будет содержать:
digraph graphname {
5 -> 3;
5 -> 8;
3 -> 4;
3 -> 2;
}
Вы создаете график с помощью dotty.exe или конвертируете его в PNG с помощью dot.exe.
Очень простое решение для печати на 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();
}
Я думаю, вам не следует кодировать это самостоятельно, но посмотрите Дерево::Визуализация который кажется хорошей реализацией Perl с различными возможными стилями и использованием/переносом туда одного из алгоритмов.
У меня есть программа на Ruby, которая вычисляет координаты, в которых должен быть нарисован каждый узел двоичного дерева: http://hectorcorrea.com/Blog/Drawing-a-Binary-Tree-in-Ruby
Этот код использует очень простой алгоритм для вычисления координат, и он не является «эффективным по площади», но это хорошее начало.Если вы хотите увидеть код «вживую», вы можете протестировать его здесь: http://binarytree.heroku.com/
