问题遇到的现象和发生背景
计算二叉树宽度,我的width函数为什么计算的是错的?
输入:cei#j##f#gk##h##d##
用代码块功能插入代码,请勿粘贴截图
# include <stdio.h>
# include <stdlib.h>
# define MAX 100
# define MaxSize 100
//定义数组的长度为100
//二叉树的结点定义
typedef struct node
{
struct node *lchild, *rchild;
char data;
}BT,*BiTree;
//循环队列的结点定义
typedef struct
{
int head;
//head为头
int rear;
//rear为尾
BT data[MAX];
//data为二叉树类型的数组,能存放二叉树中的元素
}LinkQueue;
BT* CreateBiTree()
{
BT* T;
char ch;
scanf("%c",&ch);
if(ch=='#')
T=NULL;
else
{
T=(BT* )malloc(sizeof(BT));
if(!T)
exit(-1);
(T)->data=ch;
T->lchild=CreateBiTree();
T->rchild=CreateBiTree();
}
return T;
}
//判断队是否为空
//队不为空则返回1,队空则返回0
int EmptyQueue (LinkQueue* Q)
{
if (Q->head == Q->rear)
{
return 0;
}
else
{
return 1;
}
}
//入队
void PushQueue (LinkQueue* Q, BT t)
{
Q->rear = (Q->rear+1)%MAX;
Q->data[Q->rear] = t;
}
//出队
void PopQueue (LinkQueue* Q)
{
Q->head = (Q->head+1)%MAX;
}
//层次遍历二叉树
void Leave (BT* t)
{
LinkQueue Q;
//定义一个循环队列
Q.head = 0;
Q.rear = 0;
//循环队列初始化
//队为空的条件:队头等于队尾
BT* temp;
//定义一个二叉树类型的指针
PushQueue (&Q, *t);
//根节点入队
while (EmptyQueue (&Q))
//当队不为空时,循环
{
*temp = Q.data[Q.head+1];
//将队头元素赋值给变量*temp
printf ("%c", temp->data);
//输出队头元素的值
PopQueue (&Q);
//队头元素出队
if (temp->lchild != NULL)
//如果左孩子不为空,则左子树入队
{
PushQueue (&Q, *temp->lchild);
}
//如果右孩子不为空,则右子树入队
if (temp->rchild != NULL)
{
PushQueue (&Q, *temp->rchild);
}
}
}
int width(BT* t){
BT Q[MaxSize];
BT p;
int front=1,rear=1,last=1,max=0,temp=0;
Q[rear]=*t;
while (front<=last){
p=Q[front++];
temp++;
if(p.lchild!=NULL)
Q[++rear]=*p.lchild;
if(p.rchild!=NULL)
Q[++rear]=*p.rchild;
if(front>last){
last=rear;
if(temp>max)
max=temp;
temp=0;
}
}
return max;
}
int main (void)
{
BT* t;
t=CreateBiTree();
Leave (t);
int w=width(t);
printf("\n宽度 %d",w);
return 0;
}
运行结果及报错内容
cei#j##f#gk##h##d##
cedifjgkh
宽度 1
我想要达到的结果
可以计算二叉树的宽度