Reputation: 25
How can I print a binary tree?
I am trying to print out a binary tree diagram from code like this for example:
4
/ \
2 6
/ \ / \
1 3 5 7
I tried researching how to print one all overall the internet but either the answers were confusing or not much help at all. I try making a print function by using recursion similar what U did for my insert function, but it only just printed all the numbers from each note in a straight vertical line. The order was root, left lef, left right, right left, right right. Plus, the loops stop inputting numbers for the tree when you type in the number 0.
#include <stdio.h>
#include <stdlib.h>
//typedef char* string;
typedef struct node{
int num;
struct node* left;
struct node* right;
}
node;
void print(node* pp){
printf("%i\n",pp->num);
if(pp->left !=NULL){
print(pp->left);
}
if(pp->right !=NULL){
print(pp->right);
}
}
void insert(int y, node* p){
if (p->num > y){
if (p->left == NULL){
node* a = malloc(sizeof(node));
p->left = a;
p->left->num = y;
}
else{
insert(y, p->left);
}
}
if (p->num < y){
if (p->right == NULL){
node* a = malloc(sizeof(node));
p->right = a;
p->right->num = y;
}
else{
insert(y, p->right);
}
}
}
int main(void) {
printf("Hello World\n");
node *n = malloc(sizeof(node));
printf("In put root number: ");
int x = 0;
scanf("%i", &x);
printf("\n");
n->num = x;
int y = 1;
while (y != 0){
printf("In put number: ");
scanf("%i", &y);
//printf("\n");
insert(y, n);
}
print(n);
return 0;
}
Upvotes: 1
Views: 2807
Answers (2)
Reputation: 12655
You cannot print a tree as you post in your sample, because the printing device goes from left to right, then from top to bottom, so you need to print your tree level by level, and not navigating the tree in preorder, inorder or postorder.
You can get some satisfactory results if you instead print it this way:
+-7
+-6
| +-5
+-4
| +-3
+-2
+-1
but it continues to be a challenge. The best way to proceed is to use a routine to print a right subtree, which is something like
+---------------+
+-| right subtree |
| +---------------+
another to print a node:
+-node
and another to print a left subtree:
| +--------------+
+-| left subtree |
+--------------+
and to call them as appropiate, to print the parts of the tree in this order.
One thing important is that the leftSubTree(), and rightSubTree() need a prefix to be passed as parameter to be able to paint the correct tree structure, that fails out of the drawn box above, so the links between nodes are painted correctly. so for example a left subtree needs to paint the same prefix as has been painted for the parent node, then a | before we reach the root node of the subtree, then a +- and the root node, and then a strting of two blanks to make space for the not shown part of the tree. A rightSubtree() will print first the empty part, then the root node and finally the | part.
For now, and appearing the problem an academic one, I'll leave you to exercise your mind and think on a solution yourself for this approach. The vertical tree has far more complexity to print from top to bottom and left to right order.
Chapter 2
Let's study the right subtree, as it appears above. there's a box that represents the contents of what the right subtree should print and there's a prefix with a part that is fixed for the whole treee and another part is variable for the level we are trying to print, I'll try to distinguish them below:
+----------fixed part
| +---variable part
v v v right subtree
+--------+----+--------------------------+
| | | |
| | +-Root Node of Right subtree |
| | | | |
| | | +--------------------------+
| --Root Node
| | | +--------------------------+
| | | | |
| | | | |
| | | | |
| | | | |
| | +-Root Node of Left Subtree |
| | | |
+--------+----+--------------------------+
As you see the middle prefix is painted different before and after the root node (the first part has blanks before the root node of the right subtree and filled with a line after that node, and the second part, after the root node is lined before the root node of the root node of the left subtree and blank after) We will make three routines, one to paint the nodes themselves, and a left subtree and right subtree to paint the complete subtrees on the left and the right sides.
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct node {
int key;
struct node *left;
struct node *right;
};
char buffer[1024];
/* prints a node, with its key and prefix. */
static void print_node(
struct node *n, /* node to print */
FILE *o) /* file to print to */
{
/* the first string is the fixed part that prefix the whole
* subtree, the second is the node's name. */
fprintf(o, "%s+-%d\n", buffer, n->key);
}
/* prints a subtree (the first one in the sequence)
* printing a left or right subtree is controlled by the
* prf_right and prf_left parameters passed to the call. */
static void print_subtree(
struct node *n, /* root node reference */
FILE *o, /* FILE descriptor to use as output. */
const char *prf_right, /* right prefix */
const char *prf_left, /* left prefix */
char *buf, int buf_sz) /* buffer management, to add prefixes to */
{
if (n->right) { /* right subtree */
/* add the prefix for the right subtree, this is prf_right for
* the right part (the first, before the root node) */
int res = snprintf(buf, buf_sz, "%s", prf_right);
print_subtree(n->right, o, " ", "| ", buf + res, buf_sz - res);
*buf = '\0';
}
print_node(n, o);
if (n->left) { /* left subtree */
/* add the prefix for the left subtree, this is prf_left
* for the left part (the second, after the root node) */
int res = snprintf(buf, buf_sz, "%s", prf_left);
print_subtree(n->left, o, "| ", " ", buf + res, buf_sz - res);
*buf = '\0';
}
}
int main()
{
struct node *root = NULL; /* empty tree */
/* while not EOF, read a line */
int key;
while (scanf("%d", &key) == 1) {
/* search for the pointer to be modified to add the node*/
struct node **parent = &root;
while (*parent != NULL) {
int res = key - (*parent)->key;
if (res == 0) {
printf("Node %d already in the tree, ignored\n",
key);
goto next_value;
} else if (res > 0) {
parent = &(*parent)->right;
} else {
parent = &(*parent)->left;
}
}
/* *parent == NULL */
*parent = malloc(sizeof **parent);
assert(*parent != NULL);
(*parent)->key = key;
(*parent)->left = (*parent)->right = NULL;
next_value: ;
}
/* now print a root tree (it has both prefixes equal to " ")
*/
print_subtree(root, stdout, " ", " ",
buffer, sizeof buffer);
}
The main routine reads a sequence of numbers and inserts them in the binary tree as keys, for the sample tree above, a valid sequence that produces it should be:
4 6 7 5 2 3 1
for another tree:
$ btree
1 5 3 4 7 2
+-7
+-5
| | +-4
| +-3
| +-2
+-1
$ _
Upvotes: 5
Reputation: 69
Try this :
struct Tree
{
Tree * left, * right;
int element;
};
//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];
};
Upvotes: 1
Related Questions
- How can I get a non-empty binary tree and print it?
- Print Simple Binary Search Tree in C
- Creating and printing binary tree from array
- C program: Binary tree
- Printing Binary Search Tree with numbered nodes
- How would you print a binary tree by it's rows?
- Create and print a tree in C
- Unable to print Binary Search Tree
- Unable to print all the elements in the binary tree
- How to print level order tree (not binary) in C?