蓝桥杯2013年第四届真题-横向打印二叉树 （C++代码）

解题思路:

注意事项:

参考代码:

/*
...|-12 
10-| 
...|-8-| 
.......|...|-7 
.......|-5-| 
...........|-4 
*/
#include<stdio.h>
#define maxn 110
char str[110][1000];
int cnt=1;
struct Node{
	int data;
	int lson,rson;
	int num;
	int p;
	int v;//垂直方向上的位置 
	Node()
	{
		data=-1;
		lson=-1;
		rson=-1;
		num=-1;
		p=-1;
		v=-1; 
	}
	Node(int _data,int _lson,int _rson,int _num,int _p)
	{
		data=_data;
		lson=_lson;
		rson=_rson;
		num=_num;
		p=_p;
		v=-1;
	}
}tree[maxn];
int n=0;
void build_tree(int root,int data,int num)
{
	if(data<tree[root].data)
	{
		if(tree[root].lson!=-1) build_tree(tree[root].lson,data,num);
		else 
		{
			tree[root].lson=num;
			tree[num].data=data;
			tree[num].lson=tree[num].rson=-1;
			tree[num].num=num;
			tree[num].p=-1;
		}
	}
	else if(data>tree[root].data)
	{
		if(tree[root].rson!=-1) build_tree(tree[root].rson,data,num);
		else 
		{
			tree[root].rson=num;
			tree[num].data=data;
			tree[num].lson=tree[num].rson=-1;
			tree[num].num=num;
			tree[num].p=-1;
		}
	}
}
int len(int x)
{
	int sum=0;
	if(x==0 ) return 1;
	while(x)
	{
		sum++;
		x/=10;
	}
	return sum;
}
void PT(int root,int L)
{
	if(tree[root].rson!=-1) PT(tree[root].rson,L+len(tree[root].data)+(root==0?2:4)-1); 
	for(int i=0;i<L;i++) str[cnt][i]='.'; 
	tree[root].v=cnt;
	sprintf(str[cnt++]+L,"%s%d%s",(root==0?"":"|-"),tree[root].data,((tree[root].lson==-1&&tree[root].rson==-1)?"":"-|"));
	if(tree[root].lson!=-1 || tree[root].rson!=-1) tree[root].p=L+len(tree[root].data)+(root==0?2:4)-1;
	if(tree[root].lson!=-1) PT(tree[root].lson,L+len(tree[root].data)+(root==0?2:4)-1);
}
void Format(int root)
{
	if(tree[root].lson==-1 && tree[root].rson==-1) return ;
	if(tree[root].rson!=-1) 
	{
		for(int i=tree[tree[root].rson].v+1;i<tree[root].v;i++) str[i][tree[root].p]='|';
		Format(tree[root].rson);
	}
	if(tree[root].lson!=-1) 
	{
		for(int i=tree[root].v+1;i<tree[tree[root].lson].v;i++) str[i][tree[root].p]='|'; 
		Format(tree[root].lson);
	}
}
int main(void)
{
	int data;
	scanf("%d",&data);
	tree[0]=Node(data,-1,-1,n++,-1);
	while(scanf("%d",&data)!=EOF)
	{
		build_tree(0,data,n++);
	}
	PT(0,0);
	Format(0);
	for(int i=1;i<cnt;i++) printf("%s\n",str[i]);
	return 0;
}