C How to draw a binary tree on the console

Question

What algorithms can I use to draw a binary tree in the console? The tree is implemented in C. For example, BST with numbers: 2 3 4 5 8 will be displayed on the console as:

Answer 1

Check out the printing of binary trees in Ascii

From @AnyOneElse Pastbin below:

!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! !!!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]; }; 

exit:

  2 / \ / \ / \ 1 3 / \ / \ 0 7 9 1 / / \ / \ 2 1 0 8 8 / 7 

Answer 2

the 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) 

Answer 3

Some hints: the distance between nodes at the same depth (e.g. 2 and 4 or 3 and 8 in your example) is a function of depth.

Each printed line consists of all nodes with the same depth printed from the leftmost node to the rightmost node.

Thus, you need a way, for example, to arrange your nodes in arrays of strings, according to their depth, in the order of their very left.

Starting at the root of the node, a breadth-first search will visit the nodes in order of depth and leftmost.

The spacing between nodes can be found by finding the maximum height of the tree using some constant width for the deepest nodes and doubling this width for each lesser depth, so that the width for any depth = (1 + maxdepth - currentdepth) * the deepest width.

This number gives you the printed "horizontal width" of each node at any particular depth.

The left node is located horizontally in the left half of its parent width, righ node in the right half. You will introduce dummy pads for any node that does not have parents; the easiest way to do this is to have all the leaves at the same depth as the deepest node, with an empty value. Obviously, you will also have to compensate for the width of the values, perhaps by making the maximum width of the depth at least as wide as the printed (decimal representation, presumably) of its largest node value.

Answer 4

Here is another example when the tree is implemented in an array:

 #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; } 

Output:

  0 1-----------------------------------2 3-----------------4 5-----------------6 7---------8 9---------1 2---------3 4---------5 

Answer 5

I have this small solution in C ++ - it can be easily converted to c.

My solution needs an additional data structure to store the current depth of the node in the tree (this is because if you are working with an incomplete tree, this depth of the subtree may not correspond to its depth in the full volume of the tree.)

 #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; } 

Prints the following:

  0 1 2 3 4 5 6 

Answer 6

Look at the output of the pstree command on Linux. It does not produce output in the form you want, but IMHO it is more readable in this way.

Answer 7

I second letter recommendation. I had to do this recently to print the VAD tree of the Windows process, and I used the DOT language (just print the nodes from the binary tree function):

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

For example, your DOT file will contain:

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

You create a graph using dotty.exe or convert it to PNG using dot.exe.

Answer 8

I think you should not code this yourself, but look at Tree :: Visualize , which seems to be a good implementation in Perl with various possible styles and using / port is one of the algorithms there.

Answer 9

I have a Ruby program that calculates the coordinates where each node in a binary tree should be drawn here: http://hectorcorrea.com/Blog/Drawing-a-Binary-Tree-in-Ruby

This code uses a very simple algorithm to calculate coordinates, and it is not "area efficient", but it is a good start. If you want to see the "live" code, you can check it here: http://binarytree.heroku.com/

Answer 10

A very simple C ++ solution prints a tree in the horizontal direction:

 5 1 5 9 7 14 

Code function ( Node::print() is important):

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