반응형
C 콘솔에 바이너리 트리를 "그리는"방법
콘솔에서 이진 트리를 그리는 데 사용할 수있는 알고리즘은 무엇입니까? 트리는 C로 구현됩니다. 예를 들어, 숫자가 2 3 4 5 8 인 BST는 콘솔에 다음과 같이 표시됩니다.
아래 @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 + maxdepth-currentdepth) * deepestwidth가되도록 더 작은 깊이에 대해 해당 너비를 두 배로 늘림으로써 찾을 수 있습니다. .
이 숫자는 특정 깊이에서 각 노드의 인쇄 된 "수평 너비"를 제공합니다.
왼쪽 노드는 부모 너비의 왼쪽 절반에 수평으로 배치 되고 오른쪽 절반에는 오른쪽 노드에 배치됩니다. 부모가없는 노드에 대해 더미 스페이서를 삽입합니다. 이를 수행하는 더 쉬운 방법은 모든 잎이 가장 깊은 노드와 동일한 깊이에 있고 값 이 비어 있는지 확인하는 것 입니다. 분명히, 아마도 가장 큰 깊이의 너비를 적어도 가장 큰 값을 갖는 노드의 인쇄 된 (아마도 10 진수 표현) 너비만큼 넓게 만들어 값의 너비를 보상해야 할 것입니다.
다음은 트리가 배열로 구현 될 때 한 가지 더 있습니다.
#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();
}
나는 당신이 직접 코딩해서는 안된다고 생각하지만 Tree :: Visualize 를 살펴보면 다른 가능한 스타일을 가진 멋진 Perl 구현 인 것 같고 거기에서 알고리즘 중 하나를 사용 / 포트합니다.
바이너리 트리의 각 노드가 여기에 그려 져야하는 좌표를 계산하는 Ruby 프로그램이 있습니다. http://hectorcorrea.com/Blog/Drawing-a-Binary-Tree-in-Ruby
이 코드는 좌표를 계산하기 위해 매우 기본적인 알고리즘을 사용하며 "면적 효율적"은 아니지만 좋은 시작입니다. "라이브"코드를보고 싶다면 http://binarytree.heroku.com/에서 테스트 할 수 있습니다.
참고 URL : https://stackoverflow.com/questions/801740/c-how-to-draw-a-binary-tree-to-the-console
반응형
'Programing' 카테고리의 다른 글
| tmux에서 창 이름을 바꾸는 방법은 무엇입니까? (0) | 2020.11.11 |
|---|---|
| Gradle-오류 인수에 대한 method implementation ()을 찾을 수 없음 [com.android.support:appcompat-v7:26.0.0] (0) | 2020.11.11 |
| 키워드가 지원되지 않는 데이터 소스 (0) | 2020.11.11 |
| HashSet 사용 방법 (0) | 2020.11.11 |
| 자바 스크립트에서 바이트 배열을 문자열로 변환 (0) | 2020.11.11 |