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..

Here is the printing routine..

//prints ascii tree for given Tree structure void print_ascii_tree(Tree * t) { asciinode *proot; int xmin, i; if (t == NULL) return; proot = build_ascii_tree(t); compute_edge_lengths(proot); for (i=0; iheight && i < MAX_HEIGHT; i++) { lprofile[i] = INFINITY; } compute_lprofile(proot, 0, 0); xmin = 0; for (i = 0; i height && i < MAX_HEIGHT; i++) { xmin = MIN(xmin, lprofile[i]); } for (i = 0; i height; i++) { print_next = 0; print_level(proot, -xmin, i); printf("\n"); } if (proot->height >= MAX_HEIGHT) { printf("(This tree is taller than %d, and may be drawn incorrectly.)\n", MAX_HEIGHT); } free_ascii_tree(proot); }

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; ilablen-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; iright != NULL) { for (i=0; ileft, 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; ileft->height && i left, 0, 0); hmin = node->left->height; } else { hmin = 0; } if (node->right != NULL) { for (i=0; iright->height && i right, 0, 0); hmin = MIN(node->right->height, hmin); } else { hmin = 0; } delta = 4; for (i=0; ileft != 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 edge_length && y+i 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 edge_length && y+i 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]; };

Please refer reference code for collection of posts in data structures

[note: I’d used msvc6 (which is a bit old one), so when you use new compilers you may get few compilations errors, fix them yourself or drop a msg over here..]

Advertisements

Thx 4ever

2 April 2009at11pmNice!

I linked to this from http://stackoverflow.com/questions/801740/c-how-to-draw-a-binary-tree-to-the-console/801794#801794

30 April 2009at5pmquick and dirty (but working) java version is here: http://pastebin.com/fd713b9f

18 May 2009at12amand i forgot to thank you, man:)

18 May 2009at12amHere you can find a Linux port of this program (compiled fine with GCC 4.3.3). I’ve also split binary tree routines and ascii drawing into separate .c files. Makefile included, just type ‘make’ 🙂

http://tfsoft.org.ua/downloads/ascii_bt_linux.tar.gz

5 June 2009at4amthanks a lot… it really helped… 🙂

12 June 2009at9amhow can i compile these without main function?

12 June 2009at12pmHi Thanks my friend….

Thank you very much…..

These programs are helping me very much…

25 June 2009at12am