コンソールでバイナリ ツリーを描画するために使用できるアルゴリズムは何ですか? ツリーは C で実装されています。たとえば、数字が 2 3 4 5 8 の BST は、コンソールに次のように表示されます。
103921 次
10 に答える
53
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
于 2009-04-29T10:42:05.703 に答える
51
Code:
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]);
}
Output:
.----------------------(006)-------.
.--(001)-------. .--(008)--.
.--(-02) .--(003)-------. (007) (009)
.-------(-06) (002) .--(005)
.--(-08)--. (004)
(-09) (-07)
or
(006)
+------------------------+---------+
(001) (008)
+----+---------+ +----+----+
(-02) (003) (007) (009)
+----+ +----+---------+
(-06) (002) (005)
+---------+ +----+
(-08) (004)
+----+----+
(-09) (-07)
于 2012-12-07T02:11:58.913 に答える
20
いくつかのヒント: 同じ深さのノード間の間隔 (たとえば、例では 2 と 4 または 3 と 8) は、深さの関数です。
印刷された各行は、同じ深さのすべてのノードで構成され、左端のノードから右端のノードまで印刷されます。
したがって、たとえば、ノードを行の配列に配置する方法が必要です。ノードの深さに応じて、左端の順に並べます。
ルート ノードから開始して、幅優先検索は、深さと左端の順にノードを訪問します。
ノード間の間隔は、ツリーの最大の高さを見つけ、最も深いノードには一定の幅を使用し、深さが浅い場合はその幅を 2 倍にして、深さの幅 = ( 1 + maxdepth - currentdepth ) * deepestwidth にすることで見つけることができます。 .
その数値は、特定の深さでの各ノードの印刷された「水平幅」を示します。
左ノードは親の幅の左半分に水平に配置され、右ノードは右半分に配置されます。親を持たないノードにはダミーのスペーサーを挿入します。これを行う簡単な方法は、すべての葉が最も深いノードと同じ深さにあり、値が空白であることを確認することです。明らかに、おそらく最大の深さの幅を、最大値のノードの出力 (おそらく 10 進表現) と少なくとも同じ幅にすることによって、値の幅を補正する必要もあります。
于 2009-04-29T10:41:22.537 に答える
12
ツリーが配列に実装されている場合のもう 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
于 2012-12-07T01:55:35.783 に答える
8
私は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
于 2011-12-18T10:08:23.513 に答える
3
Linuxでのpstreeコマンドの出力を見てください。希望どおりの形式で出力を生成するわけではありませんが、私見ではその方が読みやすくなっています。
于 2009-04-29T10:59:42.493 に答える
3
私は2番目のlitbの推奨事項です。最近、Windows プロセスの VAD ツリーを出力するためにこれを行う必要があり、DOT 言語を使用しました (バイナリ ツリー ウォーキング関数からノードを出力するだけです)。
http://en.wikipedia.org/wiki/DOT_language
たとえば、DOT ファイルには次のものが含まれます。
digraph グラフ名 {
5 -> 3;
5 -> 8;
3 -> 4;
3 -> 2;
}
グラフは dotty.exe で生成するか、dot.exe を使用して PNG に変換します。
于 2009-04-29T14:29:40.117 に答える
1
バイナリ ツリーの各ノードをここに描画する座標を計算する Ruby プログラムがあります: http://hectorcorrea.com/Blog/Drawing-a-Binary-Tree-in-Ruby
このコードは非常に基本的なアルゴリズムを使用して座標を計算します。これは「面積効率的」ではありませんが、良いスタートです。コードを「ライブ」で見たい場合は、ここでテストできます: http://binarytree.heroku.com/
于 2011-04-11T00:41:37.127 に答える