연결리스트 이진트리 출력 코드

2015.06.04 15:20

공영선 조회 수:921

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

typedef int element;
typedef struct TreeNode {
element key;
struct TreeNode *left;
struct TreeNode *right;
}TreeNode;

//printing tree in ascii

typedef struct asciinode_struct asciinode;

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

#define MAX_HEIGHT 1000
int lprofile[MAX_HEIGHT];
int rprofile[MAX_HEIGHT];
#define INFINITY (1<<20)
int print_next;
int gap = 3;
int MIN(int X, int Y)
{
return ((X) < (Y)) ? (X) : (Y);
}

int MAX(int X, int Y)
{
return ((X) > (Y)) ? (X) : (Y);
}

asciinode * build_ascii_tree_recursive(TreeNode * 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->key);
node->lablen = strlen(node->label);

return node;
}


//Copy the tree into the ascii node structre
asciinode * build_ascii_tree(TreeNode * 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);
}


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

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

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

//prints ascii tree for given Tree structure
void print_ascii_tree(TreeNode * t)
{
asciinode *proot;
int xmin, i;
if (t == NULL) return;
proot = build_ascii_tree(t);
compute_edge_lengths(proot);
for (i = 0; i<proot->height && i < MAX_HEIGHT; i++)
{
lprofile[i] = INFINITY;
}
compute_lprofile(proot, 0, 0);
xmin = 0;
for (i = 0; i < proot->height && i < MAX_HEIGHT; i++)
{
xmin = MIN(xmin, lprofile[i]);
}
for (i = 0; i < proot->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);
}


void main() {
TreeNode a, b, c, d;
a.key = 2;
a.left = &b;
a.right = NULL;

b.key = 1;
b.left = NULL;
b.right = &c;

c.key = 3;
c.left = NULL;
c.right = NULL;

//print Tree
print_ascii_tree(&a);



}

댓글 0

목록
번호 제목 글쓴이 날짜 조회 수
5 C언어 문제들 참고자료 DrNam 2018.05.04 250
4 데이터구조 기말고사 main 공영선 2015.06.12 805
» 연결리스트 이진트리 출력 코드 공영선 2015.06.04 921
2 배열 이진트리 출력 코드 공영선 2015.06.04 4911
1 트리 텍스트 그림 공영선 2015.05.29 233