有哪些算法可以在控制台中绘制二叉树？该树是用C实现的。例如，具有数字2 3 4 5 8的BST将在控制台中显示为：
如何在控制台中“绘制”二叉树？（C语言）
79
- Marek Szanyi
4
2创建一个包含节点和边的 .dot 文件，并使用 Graphviz 渲染它。看起来很整洁。 - Johannes Schaub - litb
@litb：不错。我实际上实现了一个渲染列表和帧缓冲，并生成了自己的BMP文件！ - user82238
请更新图片 :) - Andreas Storvik Strauman
1这里有一个开源库可以实现您想要的功能：https://github.com/YoussefRaafatNasry/bst-ascii-visualization - baziorek
10个回答
55
代码：
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)
- user1571409
2
8对于递归实现和输出的美感，给予加一赞。 - OnTheEasiestWay
我尝试将其与具有字符串值的树结构一起使用。即使增加了宽度变量，效果也不是很好。而且固定行数也很不幸。 - Ray Hulha
55
请查看在Ascii中打印二叉树。
来自@AnyOneElse Pastbin的内容如下：
来自@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
- Jonas Elfström
7
2很不幸，似乎是这样。在Google缓存或互联网档案馆Wayback机器中找不到它。这可能就是它，但我还没有尝试运行它：http://datastructuresblog.wordpress.com/2007/12/21/printing-binary-trees-in-ascii/ - Jonas Elfström
10找到了，保存了！http://pastebin.com/d3AtFKAK 和 http://web.archive.org/web/20071224095835/http://www.openasthra.com/wp-content/uploads/2007/12/binary_trees1.c。 - AnyOneElse
是的，这个不错，但如果我想打印更复杂的内容怎么办？有人为B树想出了类似的东西吗？ - Mahesha999
请注意，此答案中粘贴的代码并不包含所有原始代码。请前往存档链接获取完整的代码。 - rasen58
3我几年前将其移植到JS https://github.com/gaastonsr/treevis - Gaston Sanchez
显示剩余2条评论
20
一些提示：同一深度下节点之间的间距（例如，您示例中的2和4或3和8）是深度函数的函数。
每一行打印出所有深度相同的节点，从最左边的节点到最右边的节点。
因此，您需要一种方法，例如，将节点按照它们的深度排列在行的数组中，按其最左侧性排序。
从根节点开始，广度优先搜索将按深度和最左侧性的顺序访问节点。
通过查找树的最大高度，使用某些常数宽度作为最深节点的宽度，并将该宽度加倍用于每个较小深度，以使任何深度的宽度=（1 + maxdepth- currentdepth）* deepestwidth，可以找到节点之间的间距。
那个数字给出了任何特定深度上每个节点的打印“水平宽度”。
左节点在其父节点的宽度左半部分中水平“定位”，右节点在右半部分中。对于没有父节点的任何节点，您将插入虚拟间隔符; 更简单的方法是确保所有叶子与最深节点具有相同的深度，其中其值为空白。显然，您还必须对值的宽度进行补偿，可能是通过使最大深度的宽度至少与最大值节点的打印（十进制表示，可能）一样宽。
每一行打印出所有深度相同的节点，从最左边的节点到最右边的节点。
因此，您需要一种方法，例如，将节点按照它们的深度排列在行的数组中，按其最左侧性排序。
从根节点开始，广度优先搜索将按深度和最左侧性的顺序访问节点。
通过查找树的最大高度，使用某些常数宽度作为最深节点的宽度，并将该宽度加倍用于每个较小深度，以使任何深度的宽度=（1 + maxdepth- currentdepth）* deepestwidth，可以找到节点之间的间距。
那个数字给出了任何特定深度上每个节点的打印“水平宽度”。
左节点在其父节点的宽度左半部分中水平“定位”，右节点在右半部分中。对于没有父节点的任何节点，您将插入虚拟间隔符; 更简单的方法是确保所有叶子与最深节点具有相同的深度，其中其值为空白。显然，您还必须对值的宽度进行补偿，可能是通过使最大深度的宽度至少与最大值节点的打印（十进制表示，可能）一样宽。
- tpdi
13
这是一种将树实现在数组中的方法：
#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
- Bula
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
- Steve Lorimer
2
谢谢。我正在使用您的解决方案，但是有一个小错误。第二个q.push_back(node_depth(nd.n->l, last_lvl + 1))应该是q.push_back(node_depth(nd.n->r, last_lvl + 1))。 - bisarch
@sank - 不确定你在说什么 - 它已经计算了右子树的
node_depth。也许你复制时打错了？这里是可工作的代码：http://ideone.com/wrY8Vo - Steve Lorimer3
在Linux中查看pstree命令的输出。它不能以你想要的确切形式生成输出，但我认为这样更易读。
- Anonymous
3
我赞同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。
- Martin
2
点很棒，但问题在于ASCII。 - Norman Ramsey
有关如何将DOT与C集成的任何提示？ - yuw444
2
一个非常简单的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();
}
- cpp
1
我有一个Ruby程序，可以计算二叉树中每个节点应该绘制的坐标，代码如下：http://hectorcorrea.com/Blog/Drawing-a-Binary-Tree-in-Ruby
这段代码使用了一种非常基本的算法来计算坐标，虽然不是“面积高效”的，但是它是一个很好的起点。如果你想要在“实时”环境下查看代码，可以在这里测试：http://binarytree.heroku.com/
- Hector Correa
2
ASCII！问题要求 ASCII。 - Norman Ramsey
@Norman - 的确如此，但他也正在寻找一个算法，他可以在我列出的帖子中找到。 - Hector Correa
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接