调试分析及小结:
错误及分析:当按照完全二叉树的结点顺序输入ABCD@E@#后,程序无法运行。经测试,发现在建立二叉树时出现问题。
当扫描到B时,执行else{
if(sign%2==1) {
B[front]->lchild=S;
Sign++;}
if(sign%2==0){
B[front]->rchild=S;
详细设计:
①建立二叉树时,按照完全二叉树的结点顺序输入,@表示虚结点,#表示输入结束。
若不就是虚结点时,则建立一个新结点,并且将其作为左孩子或右孩子结点连接到它的父结点上(第一个结点无父结点);若就是虚结点,则将空结点(NULL)作为左孩子或右孩子结点连接到它的父节点上。
②查找叶子结点:利用递归先序遍历二叉树方法来查找叶子结点,当遍历一个根结点时判断其左孩子域与右孩子域就是否都为空,若都为空,则该结点就是叶子结点并用记录叶子个数,否则不就是叶子结点。
#include<stdio、h>
#include<stdlib、h>
#define max 10
typedef struct node{
char data;
node *lchild,*rchild;
}Bitree;
Bitree *B[max];
Bitree *Creatree(){ //建立二叉树
Bitree *T,*S;
char ch;
int front,rear,sign;
sign=0;
front=0;
rear=-1;
T=NULL;
printf("建立二叉树:\n");
ch=getchar();
while(ch!='#'){
if(ch!='@'){ //输入结点不就是虚结点
S=(Bitree *)malloc(sizeof(Bitree));
Inorder(T->lchild);
visit(T);
Inorder(T->rchild);
}
}
void main(){
Bitree *T;
T=Creatree();
printf("中序遍历:\n");
Inorder(T);
printf("叶子数%d\n",Searchleaf(T));
}
题目:
设二叉树采用链式存储结构,试设计一个算法计算一棵给定二叉树中叶子结点的数目。
S->data=ch;
S->lchild=S->rchild=NULL;
rear++;
B[rear]=S;
if(rear==front){
T=S;
sign++;
}
else{
if(sign%2==1) //寻找父结点
B[front]->lchild=S;
if(sign%2==0){
B[front]->rchild=S;
front++;
}
sign++;
}
}
else{ //输入结点为虚结点
if(sign%2==0)
front++;
sign++;
}
ch=getchar();
}
return T;
}
int Searchleaf(Bitree *T){ //计算叶子数
if(T==NULL)
return 0;
else if(T->lchild==NULL&&T->rchild==NULL)
问题分析:
本程序要求在一棵二叉树中实现计算叶子结点数目的功能,为完成上述功能,需要解决的关键问题就是建立二叉树过程及查找叶子结点过程。
概要设计:
①建立一个以二叉链表方式存储的二叉树,输入结点信息时按照完全二叉树的结点顺序输入。
②先序遍历二叉树,并判断遍历的根就是否就是叶子结点,若就是并记录叶子结点个数。叶子结点判断条件为:左孩子域与右孩子域都为空。
front++;
sign++;
}
}注:执行上述程序前,sign==1,B[front]指向关键字为A的结点。
当一个if语句段执行完后,关键字为A的结点的左孩子为关键字为B的结点,sign==2。此时本应结束else语句段,但由于sign==2,则第二个if语句条件为真,继续执行,因此导致程序执行出错。
改正:在if语句外置ign++,改正后代码如下:
else{
if(sign%2==1)
B[front]->lchild=S;
if(sign%2==0){
B[front]->rchild=S;
front++;
}
sign++;
}
}
return 1;
else return(Searchleaf(T->lchild)+Searchleaf(T->rchild));
}
void visit(Bitree *T){
printf("%c\n",T->data);
}
void Inorder(Bitree *T){ //中序遍历二叉树
if(T!=NULL){