如何“绘制”一个二叉树到控制台

小开

我认为您不应该自己编写代码，但是看看树: : Visualize，它似乎是一个不错的 Perl 实现，具有不同的可能样式，并且使用/移植了其中的一个算法。

小开

一些提示: 相同深度的节点之间的间距(例如，示例中的2和4或3和8)是深度的函数。

每个打印行由具有相同深度的所有节点组成，从最左边的节点打印到最右边的节点。

因此，您需要一种方法，例如，根据行的深度，按照它们最左边的顺序，将节点排列成行数组。

从根节点开始，广度优先搜索将按深度和最左边的顺序访问节点。

节点之间的间距可以通过找到树的最大高度，对最深的节点使用一些恒定的宽度，并且对于每个较小的深度将宽度加倍，这样任何深度的宽度 = (1 + maxdeep-current deep) * deep pestwidth。

这个数字给出了在任何特定深度下每个节点的打印“水平宽度”。

左节点在其父节点宽度的左半部分为水平定位，右半部分为右节点。您将为任何没有父节点的节点插入虚拟间隔符; 一种更简单的方法是确保所有叶子与最深的节点处于同一深度，并以空白作为它们的值。显然，您还必须补偿值的宽度，也许可以使最大深度的宽度至少与最大值节点的打印(大概是十进制表示)一样宽。

小开

最佳答案

看看在 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

小开

查看 Linux 中 pstree 命令的输出。它不会以你想要的精确形式产生输出，但恕我直言，这种方式更具可读性。

小开

我同意 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。

小开

我有一个 Ruby 程序，可以计算二叉树中每个节点应该被画在这里的坐标: http://hectorcorrea.com/Blog/Drawing-a-Binary-Tree-in-Ruby

这段代码使用了一个非常基本的算法来计算坐标，它不是“面积有效”的，但它是一个很好的开始。如果你想看到代码“活”，你可以在这里测试它: http://binarytree.heroku.com/

小开

我在 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

小开

下面是在数组中实现树时的另一个场景:

#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

小开

密码:

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)

小开

一个非常简单的横向 C + + 解决方案打印树:

代码(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();
}