#include"zzz.h"
void CreateBiTree(BiTree *bt)
{
char ch;
ch = getchar();
if(ch=='.') *bt=NULL;
else
{
*bt=(BiTree)malloc(sizeof(BiTNode)); //生成一个新结点
(*bt)->data=ch;
CreateBiTree(&((*bt)->LChild)); //生成左子树
CreateBiTree(&((*bt)->RChild)); //生成右子树
}
}
int PostTreeDepth(BiTree bt) /* 后序遍历求二叉树的高度递归算法 */
{
int hl,hr,max;
if(bt!=NULL)
{
hl=PostTreeDepth(bt->LChild); /* 求左子树的深度 */
hr=PostTreeDepth(bt->RChild); /* 求右子树的深度 */
max=hl>hr?hl:hr; /* 得到左、右子树深度较大者*/
return(max+1); /* 返回树的深度 */
}
else return(0); /* 如果是空树,则返回0 */
}
//////按层显示
int LayerOrder(BiTree bt)
{
SeqQueue *Q;
Q=(SeqQueue *)malloc(sizeof(SeqQueue));
//////////////////////////////////////////////////////////////////////////////////////////////////
Hard h,HARD;////进出队列时转换数据
int Dlayer=1;///
int i,n,k,NLAYER,j=0;
NLAYER=PostTreeDepth(bt);//计算二叉树的高度
n=pow(2,NLAYER)+2;//2是留出打印树与边界空隙
InitQueue(Q);
if(bt==NULL) return ERROR;
HARD.BT=bt;
HARD.layer=1;
HARD.locate=n;////确定二叉树根节点打印位置
EnterQueue(Q,&HARD);///
while(!IsEmpty(Q))
{
DeleteQueue(Q,&h);
//k=pow(2,NLAYER-Dlayer);//确定每层打印的兄弟左右结点的距离
if(h.layer>Dlayer)
{
printf("\n");
printf("\n");////////
j=1;///////////////
//k=pow(2,NLAYER-Dlayer);/////////////////////////////////////////
Dlayer++;
for(i=1;i<h.locate;i++)
printf(" ");
j=i;//////////////////////////////////记录光标打印位置
printf("%c",h.BT->data);
}
else
{
for(i=j;i<h.locate;i++)
printf(" ");
j=i;////////////////////////////////////记录光标打印位置
printf("%c",h.BT->data);
}///////在同一层上打印结点值
if(h.BT->LChild)////左子树进队列
{
HARD.BT=h.BT->LChild;
HARD.layer=Dlayer+1;
k=pow(2,NLAYER-Dlayer);//确定每层打印的兄弟左右结点的距离
HARD.locate=h.locate-k;///k用来确定左右子树位置间隔
EnterQueue(Q,&HARD);
}
if(h.BT->RChild)//右子树进队列
{
HARD.BT=h.BT->RChild;
HARD.layer=Dlayer+1;
k=pow(2,NLAYER-Dlayer);//确定每层打印的兄弟左右结点的距离
HARD.locate=h.locate+k-1;///k用来确定左右子树位置间隔
EnterQueue(Q,&HARD);
}
}//判空while大括号
return OK;
}//函数大括号
//////////////////////////////////////////////////////////////////////////////////////////////////
void main()
{
BiTree T;
printf("请输入二叉树序列(先序建立):\n");
CreateBiTree(&T);
printf("\n二叉树竖向显示为:\n");
LayerOrder(T);
printf("\n");
}