树状打印二叉树.cpp

树状打印二叉树

/************************************************************************************
*
*文件名：树状形式输出二叉树信息
*
*题目要求：
*	6.3 二叉树采用二叉链表储存，要求建立一个二叉树，并输出要求的树状形式。
*
*************************************************************************************/

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define N 50

typedef struct Node                   /*二叉树的二叉链表结点结构定义*/ 
{
	char data;
	struct Node *Lchild;
	struct Node *Rchild;
}BiTNode,*BiTree;
 
typedef struct Queue1                 /*保存信息的队列的定义*/
{
	BiTree data[N];
    int front,rear;
}LinkQueueNode;

typedef struct Queue2
{
	int nLayer[N];
	int local[N];
	int flag[N];
    int front,rear;
}Location;

//函数声明
void InitQueue1(LinkQueueNode *Q);                   /*初始化Q1队列*/    
void InitQueue2(Location *Q);                        /*初始化Q2队列*/     
int EnterQueue1(LinkQueueNode *Q,BiTree x);          /*入Q1队操作*/
BiTree DeleteQueue(LinkQueueNode *Q,BiTree x);       /*出队操作*/
int EnterQueue2(Location *R,int x,int y,int z);      /*入Q2队操作*/
void CreatBiTree(BiTree *bt);                        /*利用扩展先序遍历序列创建二叉链表*/
int LayerOrder(BiTree bt,Location *R);               /*层次遍历给结点编号*/
void Print(BiTree bt,Location *R,int sum);

int main()
//主函数
{
    BiTNode *root;  
	Location R;
    int sum;
	InitQueue2(&R);

    printf("请输入先序序列的扩展二叉树的数据(空子树用空格表示):\n"); 
    CreatBiTree(&root);


	if(root==NULL)
     	printf("This tree is a air tree!\n");
	else
    {
		sum=LayerOrder(root,&R);
		printf("该树所含的结点总数为：%3d\n",sum);
		printf("树状打印此二叉树：\n\n");
    	Print(root,&R,sum);
	}
    printf("\n");

    return 1;
}


void InitQueue1(LinkQueueNode *Q)
/*初始化队列 参数：队列指针，返回值：空*/ 
{
    Q->front=Q->rear=0;
}

void InitQueue2(Location *Q)
/*初始化队列 参数：队列指针，返回值：空*/ 
{
    Q->front=Q->rear=0;
}

int EnterQueue1(LinkQueueNode *Q,BiTree x)
/*入队 参数：队列指针，二叉树指针，返回值：整型*/
{
	if((Q->rear+1)%N==Q->front)
	   return 0;
	Q->data[Q->rear]=x;
	Q->rear=(Q->rear+1)%N;
	return 1;
}


BiTree DeleteQueue(LinkQueueNode *Q,BiTree x)
/*出队 参数：队列指针，二叉树指针，返回值：二叉树指针*/
{
	if(Q->front==Q->rear)
		return 0;
    x=Q->data[Q->front];
	Q->front=(Q->front+1)%N;
	return x;
}

void CreatBiTree(BiTree *bt)
/*创建二叉链表储存二叉树 参数：根结点指针的指针，返回值：空*/
{
	char ch;
	ch=getchar();
	if(ch==' ') *bt=NULL;
	else
	{
		*bt=(BiTree )malloc(sizeof(BiTNode));
		(*bt)->data=ch;
		CreatBiTree(&((*bt)->Lchild));
		CreatBiTree(&((*bt)->Rchild));
	}
}

int EnterQueue2(Location *R,int nLayer,int parent,int flag)
/*入队 参数：队列指针，二叉树指针，返回值：整型*/
{
	if((R->rear+1)%N==R->front)
	   return 0;
    R->nLayer[R->rear]=nLayer;
	R->local[R->rear]=parent;
	R->flag[R->rear]=flag;
	R->rear=(R->rear+1)%N;
	return 1;
}

int LayerOrder(BiTree bt,Location *R)
/*层次遍历二叉树编号 参数：根结点指针的指针，结点总数，返回值：整型*/
{
	LinkQueueNode Q;
	BiTree p=bt;
    int num[N]={0},layer=0,counter=0,m=0,sum=0,parent=32;
    num[0]=1;
    InitQueue1(&Q);
	EnterQueue1(&Q,bt); 
    EnterQueue2(R,counter,parent,0);
	while(!(Q.front==Q.rear))
	{   
        ++m;
		p=DeleteQueue(&Q,p);  
        if(m==1)  
		{
			++counter;
			R->flag[sum-1]=1;
		}
	    if(m==num[layer]) m=0;
	    if(m==0) layer++;
		if(p->Lchild)
		{
			parent=R->local[sum];
        	EnterQueue1(&Q,p->Lchild);
			++num[counter];
            EnterQueue2(R,counter,parent-64/(int)pow(2,counter+1),0);
		}  
		if(p->Rchild) 
		{  
            parent=R->local[sum];
			EnterQueue1(&Q,p->Rchild);
		    ++num[counter];
            EnterQueue2(R,counter,parent+64/(int)pow(2,counter+1),0);
		}	
		sum++;
	}
	printf("各层对应的结点个数：\n");
	for(int j=0;j<counter;j++)
	printf("%7d\n",num[j]);
	printf("结点的位置纵坐标  换行标志：\n");
    for(int v=0;v<R->rear;v++)
	printf("%7d %7d\n",R->local[v],R->flag[v]);
	return sum;
}

void Print(BiTree bt,Location *R,int s)
{
	LinkQueueNode Q;
	BiTree p=bt;
    int sum=0,n=0;
    InitQueue1(&Q);
	EnterQueue1(&Q,bt); 
	while(!(Q.front==Q.rear))
	{    
		p=DeleteQueue(&Q,p);  
        for(int j=0;j<R->local[sum];j++)
	       printf(" ");
    	printf("%c",p->data);
		if(sum+1<=s)
		{
			if(R->flag[sum]==1)
			{
				printf("\n");
				n=0;
			}
	        if(R->flag[sum]==0)
			{
		     	n++;	
		    	if(n>=1)
				{
					for(int j=0;j<n;j++)
		            	R->local[sum+1]=R->local[sum+1]-R->local[sum-j];
				}
			}
		}
		sum++;
        if(p->Lchild)	
        	EnterQueue1(&Q,p->Lchild);
		if(p->Rchild) 
			EnterQueue1(&Q,p->Rchild);        
	}
}