嗯，没错我还报了蓝桥杯。

这是题目

问题描述

二叉树可以用于排序。其原理很简单：对于一个排序二叉树添加新节点时，先与根节点比较，若小则交给左子树继续处理，否则交给右子树。

当遇到空子树时，则把该节点放入那个位置。

比如，10 8 5 7 12 4 的输入顺序，应该建成二叉树如下图所示，其中.表示空白。

...|-12

10-|

...|-8-|

.......|...|-7

.......|-5-|

...........|-4

本题目要求：根据已知的数字，建立排序二叉树，并在标准输出中横向打印该二叉树。

输入格式

输入数据为一行空格分开的N个整数。 N<100，每个数字不超过10000。

输入数据中没有重复的数字。

输出格式

输出该排序二叉树的横向表示。为了便于评卷程序比对空格的数目，请把空格用句点代替：

样例输入1

10 5 20

样例输出1

...|-20

10-|

...|-5

样例输入2

5 10 20 8 4 7

样例输出2

.......|-20

..|-10-|

..|....|-8-|

..|........|-7

5-|

..|-4

这是分析

横向打印，使用中序遍历可以获得每个节点应该在的层数
‘|’这个符号的打印是大难点

这是我的思路

使用一个二维字符数组来保存所有应该打印出来的东西
使用中序遍历获得顺序
同样使用中序遍历来打印每个数字
对于每一个非叶节点，单独打印这个节点跟它的子节点的连线

这是代码

#include<stdio.h>

#include<stdlib.h>

#define COLS 10002

#define ROWS 102

char graph[ROWS][COLS];

struct Node

{

	int lines;//这个节点应该在第几行被打印

	int layer;//这个节点在第几层

	int value;

	struct Node *left,*right;

};

struct Node *tree;

int i_index = 0;

int j_index = 0;

int index=0;

void insert(int value)

{

	int layer = 1;

	int flag = 0;

	struct Node *temp,*p;

	if(tree==NULL){

	    //putchar('a');

		tree = (struct Node*)malloc(sizeof(struct Node));

		tree->layer = layer;

		tree->value = value;

        tree->right = NULL;

		tree->left = NULL;

	}else{

	    //putchar('b');

		temp = tree;

		while(temp!=NULL){

			if(value>temp->value){

				if(temp->right!=NULL)

					temp = temp->right;

				else{

					layer++;

					flag = 1;

					break;

				}

			}else{

				if(temp->left!=NULL)

					temp = temp->left;

				else{

					layer++;

					flag = 2;

					break;

				}

			}

			layer++;

		}

		p = (struct Node*)malloc(sizeof(struct Node));

		p->left = NULL;

		p->right = NULL;

		p->layer = layer;

		p->value = value;

		if(flag==1)

			temp->right = p;

		else

			temp->left = p;

		//putchar('d');

	}

	//putchar('c');

}

int getLen(int n)

{

	int result = 0;

	while(n>0)

	{

		n/=10;

		result++;

	}

	return result;

}

void inOrder(struct Node *p)

{

	if(p==NULL)

		return;

	inOrder(p->right);

	p->lines = index++;

//	printf("%d:%d:%d\n",p->value,p->lines,p->layer);

	inOrder(p->left);

}

void DrawFinal(struct Node *p,int j)

{

	int up;int down;

	int i;

	if(p->right==NULL&&p->left==NULL)

		return;

	if(p->right==NULL)

		up=p->lines;

	else

		up=p->right->lines;

	if(p->left==NULL)

		down = p->lines;

	else

		down=p->left->lines;

	for(i = up;i<=down;i++)

		graph[i][j] = '|';

}

void inOrderDraw(struct Node *p)

{

	int i;

	int temp = j_index;

	if(p==NULL)

		return ;

	if(p->right!=NULL)

	{

		if(p->layer>1)

			j_index+=3;

		j_index+=getLen(p->value);

		inOrderDraw(p->right);

	}

	j_index = temp;

	/*for(i=0;i<j_index;i++)

		graph[i_index][i] = '.';

*/

	i = j_index;

	if(p->layer!=1)

	{

		graph[i_index][i++] = '.';

		graph[i_index][i++] = '|';

		graph[i_index][i++] = '-';

	}

	i+= sprintf(graph[i_index]+i,"%d",p->value);

	if(p->left!=NULL||p->right!=NULL)

	{

		graph[i_index][i++] = '-';

		graph[i_index][i++] = '|';

		DrawFinal(p,i-1);

	}

	graph[i_index][i++] = '\n';

	graph[i_index][i] = '\0';

	i_index++;

	if(p->left!=NULL)

	{

		if(p->layer>1)

			j_index+=3;

		j_index+=getLen(p->value);

		inOrderDraw(p->left);

	}

}

int main()

{

	int i,j;

	int num;

	char c;

	int n=0;

	for(i = 0;i<ROWS;i++)

		for(j=0;j<COLS;j++)

			graph[i][j] = '.';

	tree = NULL;

	while(1)

	{

		scanf("%d",&num);

		c = getchar();

		n++;

		insert(num);

		if(c=='\n')

			break;

	}

    inOrder(tree);

	inOrderDraw(tree);

	for(i=0;i<n;i++)

		for(j=0;graph[i][j]!='\0';j++)

			putchar(graph[i][j]);

    return 0;

}

感觉代码还是没有其他人的好。

但是其他人的我也没看懂。。。(:3 | ∠)

但是做出来了还是很开心的。。

巴特西

蓝桥杯PREV-11：横向打印二叉树

这是题目

这是分析

这是我的思路

这是代码

最新文章

热门文章