设二叉树采用链式存储结构,试设计一个算法计算一棵给定二叉树中叶子结点的数目

#include#include#define max 10typedef struct nodechar data;node *lchild,*rchild;Bitree;Bitree *Bmax;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);S-data=ch;S-lchild=S-rchild=NULL;rear+;Brear=S;if(rear=front)T=S;sign+;elseif(sign%2=1) /寻找父结点Bfront-lchild=S; if(sign%2=0)Bfront-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)return 1;else return(Searchleaf(T-lchild)+Searchleaf(T-rchild);void visit(Bitree *T)printf(%cn,T-data);void Inorder(Bitree *T) /中序遍历二叉树if(T!=NULL)Inorder(T-lchild);visit(T);Inorder(T-rchild);void main()Bitree *T;T=Creatree();printf(中序遍历:n);Inorder(T);printf(叶子数%dn,Searchleaf(T);欢迎下载题目：设二叉树采用链式存储结构，试设计一个算法计算一棵给定二叉树中叶子结点的数目。问题分析：本程序要求在一棵二叉树中实现计算叶子结点数目的功能，为完成上述功能，需要解决的关键问题是建立二叉树过程及查找叶子结点过程。概要设计：建立一个以二叉链表方式存储的二叉树，输入结点信息时按照完全二叉树的结点顺序输入。先序遍历二叉树，并判断遍历的根是否是叶子结点，若是并记录叶子结点个数。叶子结点判断条件为：左孩子域和右孩子域都为空。详细设计：建立二叉树时，按照完全二叉树的结点顺序输入，表示虚结点，#表示输入结束。若不是虚结点时，则建立一个新结点，并且将其作为左孩子或右孩子结点连接到它的父结点上（第一个结点无父结点）；若是虚结点，则将空结点（NULL）作为左孩子或右孩子结点连接到它的父节点上。查找叶子结点：利用递归先序遍历二叉树方法来查找叶子结点，当遍历一个根结点时判断其左孩子域和右孩子域是否都为空，若都为空，则该结点是叶子结点并用记录叶子个数，否则不是叶子结点。调试分析及小结： 错误及分析：当按照完全二叉树的结点顺序输入ABCDE#后，程序无法运行。经测试，发现在建立二叉树时出现问题。 当扫描到B时，执行else if(sign%2=1) Bfront-lchild=S; Sign+; if(sign%2=0) Bfront-rchild=S; front+; sign+; 注：执行上述程序前，sign=1，Bfront指向关键字为A的结点。 当一个if语句段执行完后，关键字为A的结点的左孩子为关键字为B的结点，sign=2。此时本应结束else语句段，但由于sign=2，则第二个if语句条件为真，继续执行，因此导致程序执行出错。 改正：在if语句外置sign+，