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

《设二叉树采用链式存储结构,试设计一个算法计算一棵给定二叉树中叶子结点的数目》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、#include#include#definemax10typedefstructnode{chardata;node*lchild,*rchild;}Bitree;Bitree*B[max];Bitree*Creatree(){//建立二叉树Bitree*T,*S;charch;intfront,rear,sign;sign=0;front=0;rear=-1;T=NULL;printf("建立二叉树:");ch=getchar();while(ch!='#'){if(ch!='@'){//输入结点不是虚结点S=(Bitree*)malloc(s

2、izeof(Bitree));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();}returnT;}intSearchleaf(Bitree*T){//计算叶子数if(T==NUL

3、L)return0;elseif(T->lchild==NULL&&T->rchild==NULL)return1;elsereturn(Searchleaf(T->lchild)+Searchleaf(T->rchild));}voidvisit(Bitree*T){printf("%c",T->data);}voidInorder(Bitree*T){//中序遍历二叉树if(T!=NULL){Inorder(T->lchild);visit(T);Inorder(T->rchild);}}voidmain(){Bitree*T;T=Creatree();printf("中序遍历:

4、n");Inorder(T);printf("叶子数%d",Searchleaf(T));}题目：设二叉树采用链式存储结构，试设计一个算法计算一棵给定二叉树中叶子结点的数目。问题分析：本程序要求在一棵二叉树中实现计算叶子结点数目的功能，为完成上述功能，需要解决的关键问题是建立二叉树过程及查找叶子结点过程。概要设计：①建立一个以二叉链表方式存储的二叉树，输入结点信息时按照完全二叉树的结点顺序输入。②先序遍历二叉树，并判断遍历的根是否是叶子结点，若是并记录叶子结点个数。叶子结点判断条件为：左孩子域和右孩子域都为空。详细设计：①建立二叉树时，按照完全二叉树的结点顺序输入，@表示虚结点，#表示

5、输入结束。若不是虚结点时，则建立一个新结点，并且将其作为左孩子或右孩子结点连接到它的父结点上（第一个结点无父结点）；若是虚结点，则将空结点（NULL）作为左孩子或右孩子结点连接到它的父节点上。②查找叶子结点：利用递归先序遍历二叉树方法来查找叶子结点，当遍历一个根结点时判断其左孩子域和右孩子域是否都为空，若都为空，则该结点是叶子结点并用记录叶子个数，否则不是叶子结点。调试分析及小结：错误及分析：当按照完全二叉树的结点顺序输入ABCD@E@#后，程序无法运行。经测试，发现在建立二叉树时出现问题。当扫描到B时，执行else{if(sign%2==1){B[front]->lchild=S;Sig

6、n++;}if(sign%2==0){B[front]->rchild=S;front++;sign++;}}注：执行上述程序前，sign==1，B[front]指向关键字为A的结点。当一个if语句段执行完后，关键字为A的结点的左孩子为关键字为B的结点，sign==2。此时本应结束else语句段，但由于sign==2，则第二个if语句条件为真，继续执行，因此导致程序执行出错。改正：在if语句外置sign++，改正后代码如下：else{if(sign%2==1)B[front]->lchild=S;if(sign%2==0){B[front]->rchild=S;front++;}sign+

7、+;}}