print binary tree
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
char input[256]; int i;
struct node_t {
char x;
struct node_t *left, *right;
};
struct node_t *node(char x, struct node_t *left, struct node_t *right) {
struct node_t *p = (struct node_t *)malloc(sizeof(struct node_t));
*p = (struct node_t){ x, left, right };
return p;
}
// root ['(' [left] ',' [right] ')']
struct node_t *parse_tree() {
char x = input[i]; i++;
struct node_t *left = NULL, *right = NULL;
if (input[i] == '(') {
i++; if (input[i] != ',') left = parse_tree();
i++; if (input[i] != ')') right = parse_tree();
i++;
}
return node(x, left, right);
}
void delete_tree(struct node_t *tree) {
if (tree) {
delete_tree(tree->left);
delete_tree(tree->right);
free(tree);
}
}
struct node_t *read_tree() {
i = 0; scanf("%s", input);
return parse_tree();
}
int calc_height(struct node_t *tree) {
if (!tree) return 0;
int left = calc_height(tree->left);
int right = calc_height(tree->right);
return (left > right ? left : right) + 1;
}
void transform_tree(struct node_t *tree, char target[], int i) {
if (tree) {
target[i] = tree->x;
transform_tree(tree->left, target, i * 2 + 1);
transform_tree(tree->right, target, i * 2 + 2);
}
}
void pad(int n) {
for (int i = 0; i < n; ++i) printf(" ");
}
void print_tree(struct node_t *tree) {
char target[64] = "";
transform_tree(tree, target, 0);
int height = calc_height(tree), k = 0;
for (int i = 0; i < height; ++i) {
int padding = 1 << (height - i);
pad(padding);
for (int j = 0, n = 1 << i; j < n; ++j) {
char x = target[k++];
if (x) {
printf("%c", x);
} else {
printf("_");
}
pad(padding * 2);
}
printf("\n");
}
}
int main() {
struct node_t *tree = read_tree();
print_tree(tree);
delete_tree(tree);
}
C
INFO