按层次建立一棵二叉树,从键盘按照二叉树的层次遍历输入结点,空
/*按层次建立一棵二叉树,从键盘按照二叉树的层次遍历输入结点,空结点用‘*’
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
示
如下面这棵二叉树输入序列为’abcde*f**gh******’ A ?
C B ? ?
F D ?E ??
H G ??
*/
#include
#include
#define NULL 0
#define maxlen 100
typedef struct stu{
char data;
struct stu *left,*right;
}sn,*ssn;
typedef struct st{
ssn a[maxlen];
int front,rear;
}que; /*定义一个队列*/
que qt;
void in_que(ssn p) /*进队列*/
{ if (qt.front==(qt.rear+1)%maxlen) printf("overflow");
else {qt.rear=(qt.rear+1)%maxlen;
qt.a[qt.rear]=p;
}
}
ssn out_que() /*出队列*/
{ if (qt.rear==qt.front) printf("underflow");
else {qt.front=(qt.front+1)%maxlen;
return(qt.a[qt.front]);
}
}
ssn create_tree() /*按层次建立二叉树*/
{char ch,ch1,ch2;
ssn t,p,q;
ch=getchar();
if (ch!='*') {p=(ssn)malloc(sizeof(sn));
if (!p) exit(0);
p->data=ch;
in_que(p);
}
else return(NULL);
while (qt.front!=qt.rear) {
t=out_que();
ch1=getchar();
if (ch1!='*') {q=(ssn)malloc(sizeof(sn));
if (!q) exit(0);
q->data=ch1;
t->left=q;
in_que(q);
}
else t->left=NULL;
ch2=getchar();
if(ch2!='*') {q=(ssn)malloc(sizeof(sn));
if (!q) exit(0);
q->data=ch2;
t->right=q;
in_que(q);
}
else t->right=NULL;
}
return(p);
}
int suc(ssn t) /*计算二叉树结点数*/
{ int n1,n2;
if (!t) return(0);
else {n1=suc(t->left);
n2=suc(t->right);
return(1+n1+n2);
}
}
main( )
{ ssn t; int n;
qt.rear=0; qt.front=0; /*初始化队列*/
t=create_tree();
printf("\n");
n=suc(t);
printf("n=%d",n);
getch();
}