C如何“绘制”二进制树到控制台

什么algorithm可以用来在控制台中绘制二叉树？ 树在C中实现。例如，控制台中将显示一个数字为2 3 4 5 8的BST，如下所示：

Answer 1

检查打印二叉树在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], xi); } } 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 

Answer 2

码：

 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) 

Answer 3

一些提示：相同深度的节点之间的间距（例如，2和4或3和8在您的示例中）是深度的函数。

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

所以你需要一种方法，例如，按照它们的深度，按照它们最左边的顺序排列你的节点。

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

节点之间的间距可以通过find树的最大高度来find，对于最深的节点使用一些恒定的宽度，并且对于每个较小的深度加倍该宽度，使得任何深度的宽度=（1 + maxdepth-currentdepth）*最大宽度。

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

左节点水平地位于其父宽度的左半部分，右节点处于右节点。 您将为任何没有父母的节点插入虚拟分隔符; 一个更简单的方法是确保所有的叶子与最深的节点处于同一深度，其值为空白 。 显然，你也必须补偿值的宽度，或许通过使最大深度的宽度至less与最大值节点的打印（十进制表示，可能是）一样宽。

Answer 4

当一个树在数组中被实现时，这里还有一个：

 #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 

Answer 5

我有这个在c + +的小解决scheme – 它可以很容易地转换为c。

我的解决scheme确实需要一个补充数据结构来存储树中的当前节点的深度（这是因为如果您使用的是不完整的树，给定的子树的深度可能与完整树的深度不一致）。

 #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 

Answer 6

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

Answer 7

我第二个litb的build议。 我最近不得不这样做打印一个Windows进程的VAD树，我使用DOT语言（只是从你的二叉树行走function打印节点）：

http://en.wikipedia.org/wiki/DOT_language

例如，您的DOT文件将包含：

  digraph graphname {
      5  - > 3;
      5  - > 8;
      3  - > 4;
      3  - > 2;
 }

您使用dotty.exe生成graphics或使用dot.exe将其转换为PNG。

Answer 8

我认为你不应该自己编写代码，而是看一看Tree :: Visualize ，它似乎是一个不同的可能样式的不错的Perl实现，并使用/移植那里的一个algorithm。

Answer 9

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

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

Answer 10

一个非常简单的C ++解决scheme在水平方向上打印树：

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