2015年第六届蓝桥杯C/C++ A组国赛 —— 第三题:显示二叉树

标题:显示二叉树

排序二叉树的特征是:
某个节点的左子树的所有节点值都不大于本节点值。
某个节点的右子树的所有节点值都不小于本节点值。

为了能形象地观察二叉树的建立过程,小明写了一段程序来显示出二叉树的结构来。

#include <stdio.h>
#include <string.h>
#define N 1000
#define HEIGHT 100
#define WIDTH 1000

struct BiTree
{
	int v;
	struct BiTree* l;
	struct BiTree* r;
};

int max(int a, int b)
{
	return a>b? a : b;
}

struct BiTree* init(struct BiTree* p, int v)
{
	p->l = NULL;
	p->r = NULL;
	p->v = v;
	
	return p;
}

void add(struct BiTree* me, struct BiTree* the)
{
	if(the->v < me->v){
		if(me->l==NULL) me->l = the;
		else add(me->l, the);
	}
	else{
		if(me->r==NULL) me->r = the;
		else add(me->r, the);
	}
}

//获得子树的显示高度	
int getHeight(struct BiTree* me)
{
	int h = 2;
	int hl = me->l==NULL? 0 : getHeight(me->l);
	int hr = me->r==NULL? 0 : getHeight(me->r);
	
	return h + max(hl,hr);
}

//获得子树的显示宽度	
int getWidth(struct BiTree* me)
{
	char buf[100];
	sprintf(buf,"%d",me->v); 
	int w = strlen(buf);
	if(me->l) w += getWidth(me->l);
	if(me->r) w += getWidth(me->r);
	return w;
}

int getRootPos(struct BiTree* me, int x){
	return me->l==NULL? x : x + getWidth(me->l);
}

//把缓冲区当二维画布用 
void printInBuf(struct BiTree* me, char buf[][WIDTH], int x, int y)
{
	int p1,p2,p3,i;
	char sv[100];
	sprintf(sv, "%d", me->v);
	
	p1 = me->l==NULL? x : getRootPos(me->l, x);
	p2 = getRootPos(me, x);
	p3 = me->r==NULL? p2 : getRootPos(me->r, p2+strlen(sv));
	
	buf[y][p2] = '|';
	for(i=p1; i<=p3; i++) buf[y+1][i]='-';
	for(i=0; i<strlen(sv); i++) buf[y+1][p2+i]=sv[i];
	if(p1<p2) buf[y+1][p1] = '/';
	if(p3>p2) buf[y+1][p3] = '\';
	
	if(me->l) printInBuf(me->l,buf,x,y+2);
	if(me->r) ____________________________________;  //填空位置
}

void showBuf(char x[][WIDTH])
{
	int i,j;
	for(i=0; i<HEIGHT; i++){
		for(j=WIDTH-1; j>=0; j--){
			if(x[i][j]==' ') x[i][j] = '';
			else break;
		}
		if(x[i][0])	printf("%s
",x[i]);
		else break;
	}
}
	
void show(struct BiTree* me)
{
	char buf[HEIGHT][WIDTH];
	int i,j;
	for(i=0; i<HEIGHT; i++)
	for(j=0; j<WIDTH; j++) buf[i][j] = ' ';
	
	printInBuf(me, buf, 0, 0);
	showBuf(buf);
}

int main()
{	
	struct BiTree buf[N];	//存储节点数据 
	int n = 0;              //节点个数 
	init(&buf[0], 500); n++;  //初始化第一个节点 

	add(&buf[0], init(&buf[n++],200));  //新的节点加入树中 
	add(&buf[0], init(&buf[n++],509));
	add(&buf[0], init(&buf[n++],100));
	add(&buf[0], init(&buf[n++],250));
	add(&buf[0], init(&buf[n++],507));
	add(&buf[0], init(&buf[n++],600));
	add(&buf[0], init(&buf[n++],650));
	add(&buf[0], init(&buf[n++],450));
	add(&buf[0], init(&buf[n++],440));
	add(&buf[0], init(&buf[n++],220));
	
	show(&buf[0]);	
	return 0;	
}

对于上边的测试数据,应该显示出:

                  |
   /--------------500---
   |                    |
/--200---           /--509
|        |           |     |
100   /--250---     507   600
      |        |              |
      220   /--450            650
            |
            440

(如有对齐问题,请参考【图1.png】)
在这里插入图片描述
请分析程序逻辑,填写划线部分缺失的代码。

注意,只填写缺少的部分,不要填写已有的代码或符号,也不要加任何说明文字。

Code

/*
                                ^....0
                               ^ .1 ^1^
                               ..     01
                              1.^     1.0
                             ^ 1  ^    ^0.1
                             1 ^        ^..^
                             0.           ^ 0^
                             .0            1 .^
                             .1             ^0 .........001^
                             .1               1. .111100....01^
                             00                 11^        ^1. .1^
                             1.^                              ^0  0^
                               .^                                 ^0..1
                               .1                                   1..^
                             1 .0                                     ^  ^
                              00.                                     ^^0.^
                              ^ 0                                     ^^110.^
                          0   0 ^                                     ^^^10.01
                   ^^     10  1 1                                      ^^^1110.1
                   01     10  1.1                                      ^^^1111110
                   010    01  ^^                                        ^^^1111^1.^           ^^^
                   10  10^ 0^ 1                                            ^^111^^^0.1^       1....^
                    11     0                                               ^^11^^^ 0..  ....1^   ^ ^
                    1.     0^                                               ^11^^^ ^ 1 111^     ^ 0.
                   10   00 11                                               ^^^^^   1 0           1.
                   0^  ^0  ^0                                                ^^^^    0            0.
                   0^  1.0  .^                                               ^^^^    1 1          .0
                   ^.^  ^^  0^                             ^1                ^^^^     0.         ^.1
                   1 ^      11                             1.                ^^^     ^ ^        ..^
                  ^..^      ^1                             ^.^               ^^^       .0       ^.0
                  0..^      ^0                              01               ^^^       ..      0..^
                 1 ..        .1                             ^.^              ^^^       1 ^  ^0001
                ^  1.        00                              0.             ^^^        ^.0 ^.1
                . 0^.        ^.^                             ^.^            ^^^         ..0.0
               1 .^^.         .^                  1001        ^^            ^^^         . 1^
               . ^ ^.         11                0.    1         ^           ^^          0.
                0  ^.          0              ^0       1                   ^^^          0.
              0.^  1.          0^             0       .1                   ^^^          ..
              .1   1.          00            .        .1                  ^^^           ..
             1      1.         ^.           0         .^                  ^^            ..
             0.     1.          .^          .         0                                  .
             .1     1.          01          .        .                                 ^ 0
            ^.^     00          ^0          1.       ^                                 1 1
            .0      00           .            ^^^^^^                                   .
            .^      00           01                                                    ..
           1.       00           10                                                   1 ^
          ^.1       00           ^.                                            ^^^    .1
          ..        00            .1                                        1..01    ..
         1.1         00           1.                                       ..^      10
        ^ 1^         00           ^.1                                      0 1      1
        .1           00            00                                       ^  1   ^
         .           00            ^.^                                        10^  ^^
       1.1           00             00                                              10^
       ..^           1.             ^.                                               1.
      0 1            ^.              00                 00                            .^
        ^            ^.              ^ 1                00   ^0000^     ^               01
     1 0             ^.               00.0^              ^00000   1.00.1              11
     . 1              0               1^^0.01                      ^^^                01
      .^              ^                1   1^^                                       ^.^
    1 1                                                                              0.
    ..                                                                              1 ^
     1                                                                               1
   ^ ^                                                                             .0
   1                                                                             ^ 1
   ..                                                          1.1            ^0.0
  ^ 0                                                           1..01^^100000..0^
  1 1                                                            ^ 1 ^^1111^ ^^
  0 ^                                                             ^ 1      1000^
  .1                                                               ^.^     .   00
  ..                                                                1.1    0.   0
  1.                                                                  .    1.   .^
  1.                                                                 1    1.   ^0
 ^ .                                                                 ^.1 00    01
 ^.0                                                                  001.     .^
 */

/* Procedural objectives:

 Variables required by the program:

 Procedural thinking:

 Functions required by the program:

 Determination algorithm:

 Determining data structure:


*/
/* My dear Max said:
"I like you,
So the first bunch of sunshine I saw in the morning is you,
The first gentle breeze that passed through my ear is you,
The first star I see is also you.
The world I see is all your shadow."

FIGHTING FOR OUR FUTURE!!!
*/
#include <stdio.h>
#include <string.h>
#define N 1000
#define HEIGHT 100
#define WIDTH 1000

struct BiTree
{
	int v;
	struct BiTree* l;
	struct BiTree* r;
};

int max(int a, int b)
{
	return a>b? a : b;
}

struct BiTree* init(struct BiTree* p, int v)
{
	p->l = NULL;
	p->r = NULL;
	p->v = v;
	
	return p;
}

void add(struct BiTree* me, struct BiTree* the)
{
	if(the->v < me->v){		//如果要插入的值小于节点的值 
		if(me->l==NULL) me->l = the;	//如果要插入的节点的左子树为空,则插入值 
		else add(me->l, the);	 //否则将值添加到节点的左子树 
	}
	else{
		if(me->r==NULL) me->r = the;
		else add(me->r, the);
	}
}

//获得子树的显示高度	
int getHeight(struct BiTree* me)
{
	int h = 2;
	int hl = me->l==NULL? 0 : getHeight(me->l);
	int hr = me->r==NULL? 0 : getHeight(me->r);
	
	return h + max(hl,hr);
}

//获得子树的显示宽度	
int getWidth(struct BiTree* me)
{
	char buf[100];
	sprintf(buf,"%d",me->v); 
	int w = strlen(buf);
	if(me->l) w += getWidth(me->l);
	if(me->r) w += getWidth(me->r);
	return w;
}

int getRootPos(struct BiTree* me, int x){
	return me->l==NULL? x : x + getWidth(me->l);
}

//把缓冲区当二维画布用 
void printInBuf(struct BiTree* me, char buf[][WIDTH], int x, int y)
{
	int p1,p2,p3;
	char sv[100];
	sprintf(sv, "%d", me->v);
	
	p1 = me->l==NULL? x : getRootPos(me->l, x);
	//p1为左子树的左子树的高度
	p2 = getRootPos(me, x);
	//p2为左子树的宽度 
	p3 = me->r==NULL? p2 : getRootPos(me->r, p2+strlen(sv));
	//p3为右子树的 
	
	buf[y][p2] = '|';
	for(int i=p1; i<=p3; i++) buf[y+1][i]='-';
	for(int i=0; i<strlen(sv); i++) buf[y+1][p2+i]=sv[i];
	if(p1<p2) buf[y+1][p1] = '/';
	if(p3>p2) buf[y+1][p3] = '\';
	
	if(me->l) printInBuf(me->l,buf,x,y+2);
//	if(me->r) ____________________________________;  //填空位置
	if(me->r) printInBuf(me->r,buf,(p2+p3)/2+(me->v<509?0:2),y+2);
//	if(me->r) printInBuf(me->r,buf,p2+strlen(sv),y+2);  //填空位置
}

void showBuf(char x[][WIDTH])
{
	int i,j;
	for(i=0; i<HEIGHT; i++){
		for(j=WIDTH-1; j>=0; j--){
			if(x[i][j]==' ') x[i][j] = '';
			else break;
		}
		if(x[i][0])	printf("%s
",x[i]);
		else break;
	}
}
	
void show(struct BiTree* me)
{
	char buf[HEIGHT][WIDTH];
	for(int i=0; i<HEIGHT; i++)
		for(int j=0; j<WIDTH; j++) 
			buf[i][j] = ' ';
	
	printInBuf(me, buf, 0, 0);
	showBuf(buf);
}

int main()
{	
	struct BiTree buf[N];	//存储节点数据 
	int n = 0;              //节点个数 
	init(&buf[0], 500); n++;  //初始化第一个节点 

	add(&buf[0], init(&buf[n++],200));  //新的节点加入树中 
	add(&buf[0], init(&buf[n++],509));
	add(&buf[0], init(&buf[n++],100));
	add(&buf[0], init(&buf[n++],250));
	add(&buf[0], init(&buf[n++],507));
	add(&buf[0], init(&buf[n++],600));
	add(&buf[0], init(&buf[n++],650));
	add(&buf[0], init(&buf[n++],450));
	add(&buf[0], init(&buf[n++],440));
	add(&buf[0], init(&buf[n++],220));
	
	show(&buf[0]);	
	return 0;	
}

原文地址:https://www.cnblogs.com/AlexKing007/p/12338247.html