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)은 깊이의 함수입니다.
각 인쇄 행은 깊이가 동일한 모든 노드로 구성되며 가장 왼쪽 노드에서 가장 오른쪽 노드까지 인쇄됩니다.
예를 들어, 깊이에 따라 노드를 왼쪽의 순서로 순서대로 배열로 배열하는 방법이 필요합니다.
루트 노드에서 시작하여 a 폭 넓은 첫 번째 검색 깊이와 왼쪽에서 가장 큰 순서로 노드를 방문합니다.
트리의 최대 높이를 찾고 가장 깊은 노드의 일정한 너비를 사용하고 모든 깊이에 대한 폭을 두 배로 늘려서 노드 사이의 간격을 찾을 수 있습니다. .
이 숫자는 특정 깊이에서 각 노드의 인쇄 된 "수평 너비"를 제공합니다.
왼쪽 노드는 가로입니다 위치 부모 폭의 왼쪽 절반에서 오른쪽 절반의 높은 노드. 부모가없는 노드에 대해 더미 스페이서를 삽입합니다. 더 쉬운 방법은 모든 잎이 가장 깊은 노드와 같은 깊이를 유지하는 것입니다. 공백 그들의 가치로. 분명히, 당신은 또한 아마도 가장 큰 가치의 노드의 인쇄 된 (소수점 표현, 아마도)만큼 가장 큰 깊이 너비를 만들어 값의 너비를 보상해야합니다.
트리가 배열에서 구현 될 때 다음은 다음과 같습니다.
#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
Linux에서 PSTREE 명령의 출력을보십시오. 원하는 정확한 형태로 출력을 생성하지는 않지만 IMHO는 그렇게 읽을 수 있습니다.
두 번째 Litb의 추천. 최근에 Windows 프로세스의 VAD 트리를 인쇄하기 위해이 작업을 수행해야했으며 DOT 언어를 사용했습니다 (이진 트리 워킹 기능에서 노드를 인쇄합니다).
http://en.wikipedia.org/wiki/dot_language
예를 들어, DOT 파일은 다음과 같습니다.
digraph graphname {
5 -> 3;
5 -> 8;
3 -> 4;
3 -> 2;
}
dotty.exe로 그래프를 생성하거나 dot.exe를 사용하여 png로 변환합니다.
수평 방향으로 매우 간단한 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 구현으로 보이며 알고리즘 중 하나를 사용/포트합니다.
바이너리 트리의 각 노드를 여기에서 그려야하는 좌표를 계산하는 루비 프로그램이 있습니다. http://hectorcorrea.com/blog/drawing-a-binary-tree-in-ruby
이 코드는 매우 기본적인 알고리즘을 사용하여 좌표를 계산하며 "면적 효율적인"것은 아니지만 좋은 시작입니다. 코드를 보려면 "라이브"를 참조하려면 여기에서 테스트 할 수 있습니다. http://binarytree.heroku.com/
제휴하지 않습니다 StackOverflow
